DSA 450 Notes

Problem Statement

You are given N intervals [L, R] where all numbers from L to R are present. Given Q queries, each asking for the Kth smallest number considering all intervals merged. If K is greater than the total count of numbers, return -1.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^5
1 ≤ L ≤ R ≤ 10^9
1 ≤ K ≤ 10^18

Example:

Input: intervals = [(1, 5), (3, 8), (10, 15)], K = 7
Output: 8
Explanation: After merging: [1, 8] and [10, 15]. The 7th smallest is 7.

Example 2:

Input: intervals = [(1, 3), (5, 7)], K = 5
Output: 6
Explanation: Numbers are 1,2,3,5,6,7. The 5th smallest is 6.

Approach 1: Brute Force (Generate All Numbers)

Intuition

Generate all numbers from the intervals, sort them, remove duplicates, and directly access the Kth element.

Algorithm

Generate all numbers from each interval
Sort and remove duplicates
Return the Kth element (1-indexed)

java

import java.util.*;

public class Solution {
    public long kthSmallest(long[][] intervals, long K) {
        TreeSet<Long> numbers = new TreeSet<>();
        
        for (long[] interval : intervals) {
            for (long i = interval[0]; i <= interval[1]; i++) {
                numbers.add(i);
            }
        }
        
        if (K > numbers.size()) return -1;
        
        List<Long> sorted = new ArrayList<>(numbers);
        return sorted.get((int)(K - 1));
    }
}

Complexity Analysis

Time Complexity: O(n × range) - Generating all numbers
Space Complexity: O(range) - Storing all unique numbers

Approach 2: Merge Intervals + Binary Search (Optimal)

Intuition

Instead of generating all numbers, merge overlapping intervals first. Then for each query, traverse merged intervals to find which interval contains the Kth number.

Key Observations:

After merging, intervals are disjoint and sorted
Each interval contributes (R - L + 1) numbers
Use cumulative count to find which interval contains Kth number

Algorithm

Sort intervals by start point
Merge overlapping intervals
For each query K:
- Traverse merged intervals
- Track cumulative count
- Find interval containing Kth number
- Calculate exact position within that interval

java

import java.util.*;

public class KthSmallest {
    private List<long[]> merged;
    private long[] prefixCount;
    private long totalCount;
    
    public KthSmallest(long[][] intervals) {
        // Sort by start point
        Arrays.sort(intervals, (a, b) -> Long.compare(a[0], b[0]));
        
        // Merge overlapping intervals
        merged = new ArrayList<>();
        for (long[] interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0] - 1) {
                merged.add(new long[]{interval[0], interval[1]});
            } else {
                merged.get(merged.size() - 1)[1] = 
                    Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        
        // Compute prefix counts
        prefixCount = new long[merged.size() + 1];
        for (int i = 0; i < merged.size(); i++) {
            long count = merged.get(i)[1] - merged.get(i)[0] + 1;
            prefixCount[i + 1] = prefixCount[i] + count;
        }
        
        totalCount = prefixCount[merged.size()];
    }
    
    public long query(long K) {
        if (K > totalCount) return -1;
        
        // Binary search to find the interval
        int left = 0, right = merged.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefixCount[mid + 1] >= K) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        // K falls in interval 'left'
        long prevCount = prefixCount[left];
        long offset = K - prevCount - 1;
        
        return merged.get(left)[0] + offset;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long[][] intervals = new long[n][2];
        for (int i = 0; i < n; i++) {
            intervals[i][0] = sc.nextLong();
            intervals[i][1] = sc.nextLong();
        }
        
        KthSmallest ks = new KthSmallest(intervals);
        
        int q = sc.nextInt();
        while (q-- > 0) {
            long K = sc.nextLong();
            System.out.println(ks.query(K));
        }
    }
}

Dry Run Example

intervals = [(1, 5), (3, 8), (10, 15)], K = 7

Step 1: Sort intervals
sorted = [(1, 5), (3, 8), (10, 15)]

Step 2: Merge overlapping intervals
- (1, 5) starts merged = [(1, 5)]
- (3, 8): 3 <= 5+1, merge -> merged = [(1, 8)]
- (10, 15): 10 > 8+1, add -> merged = [(1, 8), (10, 15)]

Step 3: Compute prefix counts
Interval (1, 8): count = 8
Interval (10, 15): count = 6
prefixCount = [0, 8, 14]

Step 4: Query K = 7
Binary search: prefixCount[1] = 8 >= 7, so interval 0
prevCount = 0, offset = 7 - 0 - 1 = 6
Answer = 1 + 6 = 7

Result: 7

Complexity Analysis

Time Complexity: O(n log n + q log n)
- O(n log n) for sorting intervals
- O(n) for merging
- O(log n) per query using binary search
Space Complexity: O(n) - For merged intervals and prefix counts

Alternative: Linear Search Through Merged Intervals

For cases where q is small, we can simply traverse intervals:

This gives O(n) per query but is simpler to implement.

Key Takeaways

Interval Merging: Classic technique to simplify overlapping intervals
Prefix Sums on Intervals: Track cumulative count for efficient lookup
Binary Search: Use prefix sums to binary search the target interval
Avoid Generating All Numbers: Work with ranges instead of individual elements
Edge Cases: K larger than total count, adjacent intervals (L₂ = R₁ + 1)
Problem Reduction: Transform range queries into interval membership queries

Kth smallest number again

Problem Statement

Approach 1: Brute Force (Generate All Numbers)

Intuition

Algorithm

Complexity Analysis

Approach 2: Merge Intervals + Binary Search (Optimal)

Intuition

Algorithm

Dry Run Example

Complexity Analysis

Alternative: Linear Search Through Merged Intervals

Key Takeaways