Heap / Priority Queue

Master this topic with zero to advance depth.

Heap and Priority Queue Mental Models

A Heap is a specialized tree-based data structure that satisfies the heap property. A Priority Queue is an abstract data type that works like a regular queue but where each element has a "priority" associated with it.

1. Types of Heaps

Max-Heap: The value of the root node must be the greatest among all its children. The same property must be recursively true for all subtrees.
Min-Heap: The value of the root node must be the smallest among all its children.

2. Binary Heap Structure (Array Representation)

A binary heap is typically represented as an array. For an index i:

Parent: (i - 1) / 2
Left Child: 2 * i + 1
Right Child: 2 * i + 2

3. Core Operations (Time Complexity)

Operation	Description	Time Complexity
Insert	Add an element and `Sift-Up`	$O(\log N)$
Extract Min/Max	Remove root and `Sift-Down`	$O(\log N)$
Peek	View root value	$O(1)$
Heapify	Create heap from array	$O(N)$

4. Visualizing Sift-Up (Insertion)

Initial Max-Heap: [10, 8, 5]
Insert 15:
1. [10, 8, 5, 15]  (Add at end)
2. [10, 15, 5, 8]  (Swap 15 with 8, 15 > 8)
3. [15, 10, 5, 8]  (Swap 15 with 10, 15 > 10)
Done: Root is 15.

5. Common Use Cases

Top K Elements: Use a heap of size K ( $O(N \log K)$ ).
Merging Sorted Streams: K-way merge ( $O(N \log K)$ ).
Dijkstra's / Prim's Algorithms: Finding shortest paths/MST.

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Visual Representation

nums = [1, 1, 1, 2, 2, 3], k = 2

Frequency Count Buckets:
0: []
1: [3] (val 3 appears 1 time)
2: [2] (val 2 appears 2 times)
3: [1] (val 1 appears 3 times)
4: []
5: []
6: []

Iterate buckets from right to left:
Bucket 3 -> [1]
Bucket 2 -> [2]
Result (k=2): [1, 2]

Medium

Examples

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1, 2]
1 appears 3 times, 2 appears 2 times, 3 appears 1 time. Top 2 are [1, 2].

Input: nums = [1], k = 1
Output: [1]

Approach 1

Level I: Sorting (Naive)

Intuition

Count the frequency of each element and then sort the elements based on their count in descending order. Pick the first k elements.

Thought Process

Use a Hash Map to count occurrences.
Create a list of pairs (element, frequency).
Sort the list by frequency in descending order.
Take the top k elements.

⏱ O(N log N) for sorting💾 O(N) to store frequencies

Detailed Dry Run

nums = [1, 1, 2], k = 1

Map: {1: 2, 2: 1}
Pairs: [(1, 2), (2, 1)]
Sorted: [(1, 2), (2, 1)]
result: [1]

java

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);

        List<Integer> list = new ArrayList<>(count.keySet());
        list.sort((a, b) -> count.get(b) - count.get(a));

        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = list.get(i);
        return res;
    }
}

Approach 2

Level II: Bucket Sort (Optimal)

Intuition

Since frequency is bounded by array length $N$ , we can use buckets where bucket[i] stores elements that appear $i$ times. Iterate from $N$ down to 1.

Thought Process

Count frequencies with a Map.
Create an array of lists buckets of size $N+1$ .
Place each element in its corresponding frequency bucket.
Traverse buckets from right to left to collect top $k$ elements.

⏱ O(N)💾 O(N)

Detailed Dry Run

nums = [1, 1, 1, 2, 2, 3], k = 2

Map: {1:3, 2:2, 3:1}
Buckets: [[], [3], [2], [1], [], [], []]
Bucket 3: adds [1]. Result [1]
Bucket 2: adds [2]. Result [1, 2]. Done.

java

import java.util.*;
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int key : count.keySet()) {
            int freq = count.get(key);
            if (buckets[freq] == null) buckets[freq] = new ArrayList<>();
            buckets[freq].add(key);
        }
        int[] res = new int[k];
        int idx = 0;
        for (int i = buckets.length - 1; i >= 0 && idx < k; i--) {
            if (buckets[i] != null) {
                for (int n : buckets[i]) {
                    res[idx++] = n;
                    if (idx == k) return res;
                }
            }
        }
        return res;
    }
}

Approach 3

Level III: Min-Heap (Optimal)

Intuition

Instead of sorting all elements, we can maintain a Min-Heap of size k. If the size exceeds k, we pop the element with the smallest frequency. At the end, the heap contains the k most frequent elements.

Thought Process

Count frequencies using a Map.
Iterate through unique elements and push them into a Min-Heap based on frequency.
If heap size > k, pop from heap.
The remaining elements in the heap are the result.

⏱ O(N log K)💾 O(N) for frequency map

Detailed Dry Run

nums = [1, 1, 1, 2, 2, 3], k = 2

Map: {1:3, 2:2, 3:1}
Push 1 (freq 3): Heap [(1,3)]
Push 2 (freq 2): Heap [(2,2), (1,3)]
Push 3 (freq 1): Heap [(3,1), (2,2), (1,3)] -> Size 3 > k, Pop (3,1). Final Heap: [(2,2), (1,3)] -> Result [1, 2]

java

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);

        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> count.get(a) - count.get(b));
        for (int n : count.keySet()) {
            heap.add(n);
            if (heap.size() > k) heap.poll();
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = heap.poll();
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
    }
}

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Visual Representation

nums = [3,2,1,5,6,4], k = 2

Min-Heap (size k=2):
[1] -> [1, 2] -> [2, 3] -> [3, 5] -> [5, 6] -> [5, 6] (after 4)
Heap top is 5th largest.

Quickselect (Partitions):
[3, 2, 1, 5, 6, 4] -> pivot 4
[3, 2, 1] | [4] | [5, 6]
Target index is in the right partition.

Medium

Examples

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Approach 1

Level I: Sorting (Naive)

Intuition

The simplest way is to sort the entire array in descending order and return the element at index k-1.

Thought Process

Sort the input array.
Access the element at length - k (for ascending sort) or k - 1 (for descending sort).

⏱ O(N log N)💾 O(1) if sorting in place, or O(N)

Detailed Dry Run

nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4

Sorted: [1, 2, 2, 3, 3, 4, 5, 5, 6]
Index (9 - 4) = 5
nums[5] = 4

java

import java.util.Arrays;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Approach 2

Level II: Quickselect (Average Case Optimal)

Intuition

Based on the Partition logic of Quicksort. We only care about the partition that contains the $k$ th largest element (index $N-k$ ).

Thought Process

Choose a pivot element.
Partition the array around the pivot like in Quicksort.
Compare the pivot's final index with target index $N-k$ .
Recurse into the sub-array containing the target index.

⏱ O(N) Average, O(N^2) Worst Case💾 O(1) excluding recursion stack

Detailed Dry Run

nums = [3, 2, 1, 5, 6, 4], k = 2, target = 6-2 = 4

Partition: [3, 2, 1, 4, 6, 5], 4 is at index 3.
3 < 4: Recurse [6, 5]
Partition: [5, 6], 6 is at index 5.
5 > 4: Recurse [5]
Index 4 is 5. Return 5.

java

import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    int quickSelect(int[] nums, int L, int R, int k) {
        int pivot = nums[R], p = L;
        for (int i = L; i < R; i++) {
            if (nums[i] <= pivot) swap(nums, i, p++);
        }
        swap(nums, p, R);
        if (p == k) return nums[p];
        if (p < k) return quickSelect(nums, p + 1, R, k);
        return quickSelect(nums, L, p - 1, k);
    }
    void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
}

Approach 3

Level III: Min-Heap (Optimal)

Intuition

Maintain a Min-Heap of size k. As we iterate through the array, if we find an element larger than the heap's minimum, we replace the minimum with it. After one pass, the heap contains the k largest elements, and the top is the kth largest.

Thought Process

Initialize a Min-Heap.
For each number in nums:
- Push to heap.
- If heap size > k, pop the smallest element.
The root of the heap is our answer.

⏱ O(N log K)💾 O(K)

Detailed Dry Run

nums = [3, 2, 1, 5, 6, 4], k = 2

Push 3: Heap [3]
Push 2: Heap [2, 3]
Push 1: Heap [1, 2, 3] -> Pop 1. Heap [2, 3]
Push 5: Heap [2, 3, 5] -> Pop 2. Heap [3, 5]
Push 6: Heap [3, 5, 6] -> Pop 3. Heap [5, 6]
Push 4: Heap [4, 5, 6] -> Pop 4. Heap [5, 6] Result: Top is 5

java

import java.util.PriorityQueue;

public class Main {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int n : nums) {
            minHeap.add(n);
            if (minHeap.size() > k) minHeap.poll();
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        System.out.println(findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2)); // 5
    }
}

Task Scheduler

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks can be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of time that the CPU will take to finish all the given tasks.

Visual Representation

tasks = [A, A, A, B, B, B], n = 2

Simulation Steps:
1. A (freq 3->2) | Waitlist: [(A, T=3)]
2. B (freq 3->2) | Waitlist: [(A, T=3), (B, T=4)]
3. IDLE          | Waitlist: [(A, T=3), (B, T=4)]
4. A (freq 2->1) | A returns from waitlist at T=3
...
Result: A B IDLE A B IDLE A B = 8 units

Medium

Examples

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6

Approach 1

Level I: Max-Heap + Cooling Queue (Simulation)

Intuition

We want to process the most frequent tasks first to minimize idle time. Use a Max-Heap to keep track of task frequencies and a Queue to manage tasks in their cooldown period.

Thought Process

Count frequency of each task.
Push frequencies into a Max-Heap.
While heap or cooldown queue is not empty:
- Increment time.
- If heap has tasks, take the most frequent, decrement its count, and if count > 0, add to queue with its 'available time'.
- If queue has a task whose cooldown is over, push it back to the heap.

⏱ O(N * log 26) = O(N)💾 O(1) (only 26 uppercase letters)

Detailed Dry Run

tasks = [A,A,A,B,B,B], n = 2

Heap: [A:3, B:3], Queue: [], Time: 0
Time 1: Process A. Heap [B:3], Queue [(A:2, T=4)]
Time 2: Process B. Heap [], Queue [(A:2, T=4), (B:2, T=5)]
Time 3: Idle. Queue is cool until T=4.
Time 4: Q.pop A. Heap [A:2]... and so on until 8.

java

import java.util.*;
class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : tasks) counts.put(c, counts.getOrDefault(c, 0) + 1);
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(counts.values());
        Queue<int[]> q = new LinkedList<>();
        int time = 0;
        while (!pq.isEmpty() || !q.isEmpty()) {
            time++;
            if (!pq.isEmpty()) {
                int cnt = pq.poll() - 1;
                if (cnt > 0) q.add(new int[]{cnt, time + n});
            }
            if (!q.isEmpty() && q.peek()[1] == time) pq.add(q.poll()[0]);
        }
        return time;
    }
}

Approach 2

Level II: Greedy (Simplified Priority Queue)

Intuition

Always process the task with the highest remaining frequency. We use a single loop to calculate the size of chunks of size $n+1$ .

Thought Process

Count frequencies.
Use a Priority Queue (Max-Heap).
In each chunk of $n+1$ time units, pick tasks from heap.
If heap is empty but we still have tasks to process (temporarily removed), add 'idle' counts.

⏱ O(N)💾 O(1)

Detailed Dry Run

tasks = [A, A, A, B, B, B], n = 2

Frequencies: {A:3, B:3}
Iteration 1: Chunk size 3. Pick A (rem 2), B (rem 2). Total time 2. Remaining tasks exist, so add 1 idle. Time 3.
Iteration 2: Pick A (rem 1), B (rem 1). Time 6.
Iteration 3: Pick A (rem 0), B (rem 0). Time 8. Done.

java

import java.util.*;
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freqs = new int[26];
        for (char c : tasks) freqs[c - 'A']++;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int f : freqs) if (f > 0) pq.add(f);
        int time = 0;
        while (!pq.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int cycle = n + 1;
            while (cycle > 0 && !pq.isEmpty()) {
                temp.add(pq.poll());
                time++; cycle--;
            }
            for (int f : temp) if (--f > 0) pq.add(f);
            if (pq.isEmpty()) break;
            time += cycle; // Idle time
        }
        return time;
    }
}

Approach 3

Level III: Greedy (Mathematical)

Intuition

The total time is determined by the task with the maximum frequency. Let the maximum frequency be maxFreq. There are maxFreq - 1 gaps between these tasks, each of size n. We fill these gaps with other tasks. If the total units required is less than the total number of tasks, the answer is the total tasks.

Formula

partCount = maxFreq - 1 partLength = n - (countOfTasksWithMaxFreq - 1) emptySlots = partCount * partLength availableTasks = tasks.length - maxFreq * countOfTasksWithMaxFreq idles = max(0, emptySlots - availableTasks) Result = tasks.length + idles

⏱ O(N)💾 O(1) (26 tasks)

Detailed Dry Run

tasks = [A,A,A,B,B,B], n = 2

maxFreq = 3 (A and B both have 3).
Max freq task count = 2 (A and B).
Formula: (3-1) * (2+1) + 2 = 8. Total Time = 8.

java

import java.util.Arrays;

public class Main {
    public static int leastInterval(char[] tasks, int n) {
        int[] freqs = new int[26];
        for (char c : tasks) freqs[c - 'A']++;
        Arrays.sort(freqs);
        
        int maxFreq = freqs[25];
        int idleTime = (maxFreq - 1) * n;
        
        for (int i = 24; i >= 0 && freqs[i] > 0; i--) {
            idleTime -= Math.min(maxFreq - 1, freqs[i]);
        }
        
        return idleTime > 0 ? tasks.length + idleTime : tasks.length;
    }

    public static void main(String[] args) {
        System.out.println(leastInterval(new char[]{'A','A','A','B','B','B'}, 2)); // 8
    }
}

K Closest Points to Origin

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$ .

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Visual Representation

points = [[1,3],[-2,2]], k = 1

Distance of [1,3] = sqrt(1^2 + 3^2) = sqrt(10) ≈ 3.16
Distance of [-2,2] = sqrt((-2)^2 + 2^2) = sqrt(8) ≈ 2.83

Closest Point: [-2, 2]

Medium

Examples

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2, 2]]

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]

Approach 1

Level I: Sorting (Naive)

Intuition

Calculate the squared distance for every point, then sort all points based on these distances. Return the first k points.

Thought Process

Use a custom comparator to compare points $(x_1, y_1)$ and $(x_2, y_2)$ based on $x_1^2 + y_1^2$ vs $x_2^2 + y_2^2$ .
Sort the array using this comparator.
Return the sub-array of size k.

⏱ O(N log N)💾 O(log N) to O(N) depending on sort implementation

Detailed Dry Run

points = [[1,3], [-2,2]], k = 1

Dist sq: [10, 8]
Sorted by dist: [[-2,2], [1,3]]
Take first k=1: [[-2,2]]

java

import java.util.Arrays;
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, (a, b) -> (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]));
        return Arrays.copyOfRange(points, 0, k);
    }
}

Approach 2

Level II: Quickselect (Average Case Optimal)

Intuition

Similar to Kth Largest Element, we can use the Partition logic to find the $k$ closest points in $O(N)$ average time.

Thought Process

Define distance function $D(p) = x^2 + y^2$ .
Partition the points based on $D(p)$ .
If pivot index equals $k$ , all points to the left are the $k$ closest.
Recurse into the necessary partition.

⏱ O(N) Average, O(N^2) Worst Case💾 O(1) excluding recursion stack

Detailed Dry Run

points = [[3,3], [5,-1], [-2,4]], k = 2 Distances: [18, 26, 20]

Partition around pivot 20: [[3,3], [-2,4], [5,-1]]. Pivot 20 is at index 1.
k=2, so we need to ensure index 1 is part of the result. Return points[0...1].

java

import java.util.*;
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        quickSelect(points, 0, points.length - 1, k);
        return Arrays.copyOfRange(points, 0, k);
    }
    void quickSelect(int[][] points, int L, int R, int k) {
        if (L >= R) return;
        int p = partition(points, L, R);
        if (p == k) return;
        if (p < k) quickSelect(points, p + 1, R, k);
        else quickSelect(points, L, p - 1, k);
    }
    int partition(int[][] points, int L, int R) {
        int[] pivot = points[R];
        int dist = dist(pivot), p = L;
        for (int i = L; i < R; i++) {
            if (dist(points[i]) <= dist) swap(points, i, p++);
        }
        swap(points, p, R);
        return p;
    }
    int dist(int[] p) { return p[0]*p[0] + p[1]*p[1]; }
    void swap(int[][] pts, int i, int j) { int[] t = pts[i]; pts[i] = pts[j]; pts[j] = t; }
}

Approach 3

Level III: Max-Heap (Optimal)

Intuition

Maintain a Max-Heap of size k to store the points with the smallest distances. If we find a point with a smaller distance than the maximum in our heap, we replace the maximum with it.

Thought Process

Initialize a Max-Heap based on squared Euclidean distance.
Iterate through all points.
Push the current point into the heap.
If heap size > k, pop the point with the largest distance (the root).
After all points are processed, the heap contains the k closest points.

⏱ O(N log K)💾 O(K)

Detailed Dry Run

points = [[3,3],[5,-1],[-2,4]], k = 2

Point [3,3], Dist 18: Heap [[3,3] (Dist 18)]
Point [5,-1], Dist 26: Heap [[5,-1] (Dist 26), [3,3] (Dist 18)]
Point [-2,4], Dist 20: Heap [[5,-1] (Dist 26), [-2,4], [3,3]] -> Pop [5,-1]. Final Heap: [[-2,4], [3,3]]

java

import java.util.*;

public class Main {
    public static int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1]));
        for (int[] p : points) {
            maxHeap.add(p);
            if (maxHeap.size() > k) maxHeap.poll();
        }
        int[][] res = new int[k][2];
        while (k > 0) res[--k] = maxHeap.poll();
        return res;
    }

    public static void main(String[] args) {
        int[][] res = kClosest(new int[][]{{3,3},{5,-1},{-2,4}}, 2);
        System.out.println(Arrays.deepToString(res));
    }
}

Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Visual Representation

intervals = [[0,30],[5,10],[15,20]]

Timeline:
0  5  10   15   20   30
|--|---|---|----|----|
[0      30]             (Room 1)
   [5 10]               (Room 2)
           [15 20]      (Room 2 - reused)

Max overlapping at any time: 2

Medium

Examples

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Input: intervals = [[7,10],[2,4]]
Output: 1

Approach 1

Level I: Min-Heap (Interval Management)

Intuition

Sort the meetings by start time. Use a Min-Heap to track the end times of meetings currently in progress. If a new meeting starts after the earliest meeting ends (root of the heap), we can reuse that room.

Thought Process

Sort intervals by start time.
Initialize a Min-Heap to store end times.
For each interval:
- If heap is not empty and heap.peek() <= current.start, pop the heap (room becomes free).
- Push current interval's end time to heap.
The final size of the heap is the number of rooms needed.

⏱ O(N log N)💾 O(N)

Detailed Dry Run

intervals = [[0,30],[5,10],[15,20]]

Sorted: [[0,30],[5,10],[15,20]]
Int [0,30]: Heap [30]
Int [5,10]: Heap.peek(30) > 5. Push 10. Heap [10, 30]
Int [15,20]: Heap.peek(10) <= 15. Pop 10. Push 20. Heap [20, 30] Result: Heap size = 2

java

import java.util.*;
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int[] interval : intervals) {
            if (!pq.isEmpty() && pq.peek() <= interval[0]) pq.poll();
            pq.add(interval[1]);
        }
        return pq.size();
    }
}

Approach 2

Level II: Sweep Line (Difference Array Logic)

Intuition

Record all 'start' and 'end' events. A 'start' event increases the room count by 1, and an 'end' event decreases it by 1. The maximum room count at any point is our answer.

Thought Process

For each interval $[s, e]$ , create two points: $(s, +1)$ and $(e, -1)$ .
Sort todos points by time.
If times are equal, process end events $(-1)$ before start events $(+1)$ if the interval is exclusive, OR start before end if inclusive. (LeetCode meetings are inclusive of start, exclusive of end, so end before start at same time).
Traverse through sorted points and maintain a running sum.

⏱ O(N log N)💾 O(N)

Detailed Dry Run

intervals = [[0,30],[5,10],[15,20]]

Events: (0,+1), (30,-1), (5,+1), (10,-1), (15,+1), (20,-1)
Sorted: (0,+1), (5,+1), (10,-1), (15,+1), (20,-1), (30,-1)
Sums: 1 -> 2 -> 1 -> 2 -> 1 -> 0 Max Sum: 2

java

import java.util.*;
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        List<int[]> events = new ArrayList<>();
        for (int[] i : intervals) {
            events.add(new int[]{i[0], 1});
            events.add(new int[]{i[1], -1});
        }
        Collections.sort(events, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int rooms = 0, maxRooms = 0;
        for (int[] e : events) {
            rooms += e[1];
            maxRooms = Math.max(maxRooms, rooms);
        }
        return maxRooms;
    }
}

Approach 3

Level III: Two Pointers (Chronological Ordering)

Intuition

Separate start times and end times and sort both. Iterate through the start times. If a start time is before the earliest end time, we need a room. If not, a room just became free, so we can move the end-time pointer.

Logic Steps

Extract all starts and ends into separate arrays.
Sort both arrays.
Use two pointers s and e.
If starts[s] < ends[e], increment usedRooms and s.
Else (room freed), increment e and s (total rooms stays same).

⏱ O(N log N)💾 O(N) for separate arrays

Detailed Dry Run

starts = [0, 5, 15], ends = [10, 20, 30]

s=0, e=0: starts[0]=0 < ends[0]=10 -> rooms=1, s=1
s=1, e=0: starts[1]=5 < ends[0]=10 -> rooms=2, s=2
s=2, e=0: starts[2]=15 >= ends[0]=10 -> rooms=2, e=1, s=3 Result: 2 rooms.

java

import java.util.Arrays;

public class Main {
    public static int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] start = new int[n];
        int[] end = new int[n];
        for (int i = 0; i < n; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        
        int rooms = 0, e = 0;
        for (int s = 0; s < n; s++) {
            if (start[s] < end[e]) rooms++;
            else e++;
        }
        return rooms;
    }

    public static void main(String[] args) {
        System.out.println(minMeetingRooms(new int[][]{{0,30},{5,10},{15,20}})); // 2
    }
}

Rearrange String k Distance Apart

Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string "".

Visual Representation

s = "aabbcc", k = 3

Frequency Count:
a: 2, b: 2, c: 2

Step-by-Step Selection (k=3):
Pos 0: Use 'a' (freq 2->1) | Wait: {a: wait 2}
Pos 1: Use 'b' (freq 2->1) | Wait: {a: wait 1, b: wait 2}
Pos 2: Use 'c' (freq 2->1) | Wait: {a: wait 0, b: wait 1, c: wait 2}
Pos 3: 'a' is free! Use 'a'| Wait: {b: wait 0, c: wait 1, a: wait 2}
...
Result: "abcabc"

Hard

Examples

Input: s = "aabbcc", k = 3
Output: "abcabc"

Input: s = "aaadbbcc", k = 2
Output: "abacabcd"

Input: s = "aaabc", k = 3
Output: ""

Approach 1

Level I: Greedy with Max-Heap (Standard)

Intuition

We should always try to place the most frequent characters as early as possible. However, once a character is used, it cannot be used again for the next k-1 positions. Use a Max-Heap to track frequencies and a queue to manage the 'waitlist'.

Thought Process

Count frequency of each character.
Push char-frequency pairs into a Max-Heap.
While heap is not empty:
- Extract the character with the max frequency.
- Append it to the result.
- Decrement its frequency.
- Add it to a 'waitlist' queue.
- If the waitlist queue size reaches k, pop the character from the front and push it back into the heap (if its freq > 0).

⏱ O(N log A) where A is the alphabet size (26)💾 O(A)

Detailed Dry Run

s = "aaabc", k = 3

Map: {a:3, b:1, c:1}, Heap: [a:3, b:1, c:1], Wait: []
Step 1: Use 'a'. Result: "a", Heap: [b:1, c:1], Wait: [(a, 2)]
Step 2: Use 'b'. Result: "ab", Heap: [c:1], Wait: [(a, 2), (b, 0)]
Step 3: Use 'c'. Result: "abc", Heap: [], Wait: [(a, 2), (b, 0), (c, 0)]
Wait size 3: Push 'a' back to heap. Heap: [a:2]
Continue... (If result length != s length, return "")

java

import java.util.*;

public class Main {
    public static String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.put(c, counts.getOrDefault(c, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        maxHeap.addAll(counts.entrySet());

        StringBuilder res = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> waitlist = new LinkedList<>();

        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> current = maxHeap.poll();
            res.append(current.getKey());
            current.setValue(current.getValue() - 1);
            waitlist.offer(current);

            if (waitlist.size() < k) continue;
            
            Map.Entry<Character, Integer> front = waitlist.poll();
            if (front.getValue() > 0) maxHeap.offer(front);
        }

        return res.length() == s.length() ? res.toString() : "";
    }

    public static void main(String[] args) {
        System.out.println(rearrangeString("aabbcc", 3));
    }
}

Approach 2

Level II: Greedy with Alphabet Array (O(N * 26))

Intuition

Instead of a Max-Heap, we can directly use a frequency array of size 26. At each position in the result string, we scan all 26 characters to find the one that: 1. Is allowed to be placed (distance since last use >= k). 2. Has the maximum remaining frequency.

⏱ O(N * A) where A = 26💾 O(A)

Detailed Dry Run

s = "aabbcc", k = 3

Freqs: {a:2, b:2, c:2}, LastPos: {a:-inf, b:-inf, c:-inf}
Pos 0: 'a' is valid and max freq. Res: "a", Freqs: {a:1...}, LastPos: {a:0}
Pos 1: 'a' invalid (1 < 3), 'b' is valid and max freq. Res: "ab"...
Pos 3: 'a' becomes valid again (3-0 >= 3).

java

public class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        int[] count = new int[26];
        int[] nextValid = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            int nextChar = findNextChar(count, nextValid, i);
            if (nextChar == -1) return "";
            count[nextChar]--;
            nextValid[nextChar] = i + k;
            sb.append((char)('a' + nextChar));
        }
        return sb.toString();
    }

    private int findNextChar(int[] count, int[] nextValid, int index) {
        int max = -1, res = -1;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0 && count[i] > max && index >= nextValid[i]) {
                max = count[i];
                res = i;
            }
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Modified Greedy with Max-Freq Limit Check)

Intuition

This approach uses a Max-Heap but adds a check to see if it's mathematically possible to rearrange. If the most frequent character appears more times than the available slots given distance k, it's impossible. We use a waitlist (cooling queue) to manage the distance k requirement.

⏱ O(N log A) where A = 26💾 O(A)

Detailed Dry Run

s = "aaabc", k = 3

Freqs: {a:3, b:1, c:1}. Heap: [a:3, b:1, c:1]. Wait: []
Pop 'a'. Res: "a". Freq: a:2. Wait: [a:2].
Wait size < 3. Continue.
If heap empty and res.length < s.length, return "".

java

import java.util.*;

public class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.put(c, counts.getOrDefault(c, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        maxHeap.addAll(counts.entrySet());

        StringBuilder res = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> waitlist = new LinkedList<>();

        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> current = maxHeap.poll();
            res.append(current.getKey());
            current.setValue(current.getValue() - 1);
            waitlist.offer(current);

            if (waitlist.size() < k) continue;
            
            Map.Entry<Character, Integer> front = waitlist.poll();
            if (front.getValue() > 0) maxHeap.offer(front);
        }

        return res.length() == s.length() ? res.toString() : "";
    }
}

Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from nums1 and one element from nums2.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Visual Representation

nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3

Possible Pairs:
(1,2) sum=3
(1,4) sum=5
(1,6) sum=7
(7,2) sum=9 ...

Smallest 3 pairs: [[1,2], [1,4], [1,6]]

Medium

Examples

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]

Approach 1

Level I: Brute Force + Sorting

Intuition

Generate all possible pairs from the two arrays, calculate their sums, and sort them. Return the first k pairs.

Thought Process

Nest two loops to iterate over nums1 and nums2.
Store each pair and its sum in a list.
Sort the list by sum.
Take the first k elements.

⏱ O(M * N log(M * N))💾 O(M * N)

Detailed Dry Run

nums1 = [1,2], nums2 = [3], k = 1

Pairs: [[1,3] sum:4, [2,3] sum:5]
Sorted: [[1,3], [2,3]]
Result: [[1,3]]

java

import java.util.*;
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                res.add(Arrays.asList(nums1[i], nums2[j]));
            }
        }
        res.sort((a, b) -> (a.get(0)+a.get(1)) - (b.get(0)+b.get(1)));
        return res.size() > k ? res.subList(0, k) : res;
    }
}

Approach 2

Level II: Max-Heap of size K (Better Brute Force)

Intuition

Instead of storing all pairs and sorting, we can maintain a Max-Heap of size $k$ . If we find a pair smaller than the root of our Max-Heap, we replace the root. This reduces space complexity for large $M, N$ if $k$ is small.

Thought Process

Use a Max-Heap to store [u, v] pairs based on their sum.
Iterate through nums1 and nums2 (limit to $k$ to avoid unnecessary checks).
Push each pair to the heap.
If heap size exceeds $k$ , pop the largest (root).
Return all pairs in the heap.

⏱ O(k^2 log k)💾 O(k)

Detailed Dry Run

nums1 = [1, 2], nums2 = [3], k = 1

Pair [1,3], sum 4. Heap: [[1,3]]
Pair [2,3], sum 5. Heap: [[2,3], [1,3]] -> Pop [2,3]. Heap: [[1,3]] Result: [[1,3]]

java

import java.util.*;
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[0]+b[1]) - (a[0]+a[1]));
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                pq.offer(new int[]{nums1[i], nums2[j]});
                if (pq.size() > k) pq.poll();
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            res.add(0, Arrays.asList(p[0], p[1]));
        }
        return res;
    }
}

Approach 3

Level III: Min-Heap (Optimal)

Intuition

Since arrays are sorted, the smallest pair is (nums1[0], nums2[0]). The next candidates are (nums1[1], nums2[0]) or (nums1[0], nums2[1]). We can use a Min-Heap to explore pairs efficiently.

Thought Process

Push (nums1[i], nums2[0], 0) for all i (or just i=0 and expand both ways) into a Min-Heap.
In each step, pop the smallest pair (nums1[i], nums2[j]).
Add it to result.
Push the next potential pair (nums1[i], nums2[j+1]) into the heap.
Repeat k times.

⏱ O(K log K)💾 O(K)

Detailed Dry Run

nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3

Heap: [(1,2,idx_in_nums2=0)]
Pop (1,2). Result: [[1,2]]. Push next in nums2: (1,4,1). Heap: [(1,4,1)]
Pop (1,4). Result: [[1,2],[1,4]]. Push next: (1,6,2). Heap: [(1,6,2), (7,2,0)] (Note: 7,2 is pushed later or initialized) Actually simpler: Push all nums1[i] + nums2[0].
Heap: [(1+2, 0,0), (7+2, 1,0), (11+2, 2,0)]
Pop (3, 0,0). Result [[1,2]]. Push (1+4, 0,1).
Pop (5, 0,1). Result [[1,2], [1,4]]. Push (1+6, 0,2).
Pop (7, 0,2). Result [[1,2], [1,4], [1,6]]. Done.

java

import java.util.*;

public class Main {
    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] + a[1]) - (b[0] + b[1]));
        List<List<Integer>> res = new ArrayList<>();
        if (nums1.length == 0 || nums2.length == 0 || k == 0) return res;
        
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            pq.offer(new int[]{nums1[i], nums2[0], 0});
        }
        
        while (k-- > 0 && !pq.isEmpty()) {
            int[] curr = pq.poll();
            res.add(Arrays.asList(curr[0], curr[1]));
            if (curr[2] == nums2.length - 1) continue;
            pq.offer(new int[]{curr[0], nums2[curr[2] + 1], curr[2] + 1});
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(kSmallestPairs(new int[]{1, 7, 11}, new int[]{2, 4, 6}, 3));
    }
}

Sort Characters By Frequency

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Visual Representation

s = "tree"

Frequency Count:
'e': 2
't': 1
'r': 1

Sorted by frequency: 'e' -> 't' -> 'r'
Result: "eetr" or "eert"

Medium

Examples

Input: s = "tree"
Output: "eert"

Input: s = "cccaaa"
Output: "aaaccc"

Approach 1

Level I: Max-Heap (Standard)

Intuition

Count the frequency of each character. Then, construct a Max-Heap where the key is the frequency. Repeatedly pop the character with the highest frequency and append it to our result string the required number of times.

Thought Process

Use a hash map to count character frequencies.
Add all (frequency, character) pairs to a Max-Heap.
Poll characters from the heap and append each to a StringBuilder frequency times.
Return the constructed string.

⏱ O(N log k) where k is the number of unique characters💾 O(N)

Detailed Dry Run

s = "tree"

Map: {'t':1, 'r':1, 'e':2}
Max-Heap: [('e',2), ('t',1), ('r',1)]
Pop ('e',2). Appended 2 times -> "ee"
Pop ('t',1). Appended 1 time -> "eet"
Pop ('r',1). Appended 1 time -> "eetr" Result: "eetr"

java

import java.util.*;
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
        PriorityQueue<Character> pq = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        pq.addAll(map.keySet());
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            char c = pq.poll();
            for (int i = 0; i < map.get(c); i++) sb.append(c);
        }
        return sb.toString();
    }
}

Approach 2

Level II: Sorting Map Entries

Intuition

Collect character frequencies in a map, convert the map entries to a list, and sort the list by frequency in descending order. Then build the string based on the sorted list.

⏱ O(N + K log K)💾 O(K)

Detailed Dry Run

s = "tree"

Map: {'t':1, 'r':1, 'e':2}
List of entries: [('t',1), ('r',1), ('e',2)]
Sorted List: [('e',2), ('t',1), ('r',1)]
Result: "eetr"

java

import java.util.*;
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort((a, b) -> b.getValue() - a.getValue());
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            for (int i = 0; i < entry.getValue(); i++) sb.append(entry.getKey());
        }
        return sb.toString();
    }
}

Approach 3

Level III: Bucket Sort (Optimal)

Intuition

Since the maximum frequency a character can have is the length of the string N, we can use an array of lists as buckets. bucket[i] stores characters that appear exactly i times.

⏱ O(N)💾 O(N)

Detailed Dry Run

s = "tree", N=4

Map: {'t':1, 'r':1, 'e':2}
Buckets array of size 5: [0:[], 1:['t','r'], 2:['e'], 3:[], 4:[]]
Iterate from 4 down to 1.
i=2: bucket contains 'e'. Append 'e' 2 times -> "ee"
i=1: bucket contains 't','r'. Append 't' 1 time, 'r' 1 time -> "eetr"

java

import java.util.*;
public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.put(c, counts.getOrDefault(c, 0) + 1);
        List<Character>[] buckets = new List[s.length() + 1];
        for (Character key : counts.keySet()) {
            int freq = counts.get(key);
            if (buckets[freq] == null) buckets[freq] = new ArrayList<>();
            buckets[freq].add(key);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = buckets.length - 1; i > 0; i--) {
            if (buckets[i] != null) {
                for (char c : buckets[i]) {
                    for (int j = 0; j < i; j++) sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}

Minimum Cost to Connect Sticks

You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.

You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect until there is only one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Visual Representation

sticks = [2,4,3]

Options:
1. Connect 2 and 3: cost = 5, sticks = [4, 5]
   Connect 4 and 5: cost = 9, sticks = [9]
   Total cost: 5 + 9 = 14 (Optimal)

2. Connect 4 and 3: cost = 7, sticks = [2, 7]
   Connect 2 and 7: cost = 9, sticks = [9]
   Total cost: 7 + 9 = 16 (Not Optimal)

Medium

Examples

Input: sticks = [2,4,3]
Output: 14

Input: sticks = [1,8,3,5]
Output: 30

Input: sticks = [5]
Output: 0

Approach 1

Level I: Sorting Repeatedly (Simulation)

Intuition

To minimize the total cost, we intuitively always want to connect the two currently smallest sticks. We can simulate this by sorting the array, removing the two smallest, adding their sum to the cost, putting the new stick back, and re-sorting.

Thought Process

If sticks.length <= 1, cost is 0.
Loop while we have more than 1 stick.
Sort the array/list.
Take the first two elements and add them to get currentCost.
Add currentCost to totalCost.
Remove the first two elements and insert currentCost.
Repeat until 1 stick remains.

⏱ O(N^2 log N)💾 O(N)

Detailed Dry Run

sticks = [1,8,3,5]

Sort: [1, 3, 5, 8]
Take 1, 3. Sum = 4. Cost = 4. Array [4, 5, 8]
Sort: [4, 5, 8]
Take 4, 5. Sum = 9. Cost = 4 + 9 = 13. Array [9, 8]
Sort: [8, 9]
Take 8, 9. Sum = 17. Cost = 13 + 17 = 30. Total = 30.

java

import java.util.*;
class Solution {
    public int connectSticks(int[] sticks) {
        List<Integer> list = new ArrayList<>();
        for (int s : sticks) list.add(s);
        int total = 0;
        while (list.size() > 1) {
            Collections.sort(list);
            int s = list.remove(0) + list.remove(0);
            total += s;
            list.add(s);
        }
        return total;
    }
}

Approach 2

Level II: Binary Search Insertion (Optimized Simulation)

Intuition

Maintain the list in sorted order by using binary search to find the insertion point for each new combined stick.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

sticks = [1,8,3,5]

Sort: [1, 3, 5, 8]
1+3=4. Binary search 4 in [5, 8] -> index 0. List: [4, 5, 8].
4+5=9. Binary search 9 in [8] -> index 1. List: [8, 9].
8+9=17. Total: 4+9+17=30.

java

import java.util.*;
class Solution {
    public int connectSticks(int[] sticks) {
        LinkedList<Integer> list = new LinkedList<>();
        Arrays.sort(sticks);
        for (int s : sticks) list.add(s);
        int total = 0;
        while (list.size() > 1) {
            int sum = list.removeFirst() + list.removeFirst();
            total += sum;
            int idx = Collections.binarySearch(list, sum);
            if (idx < 0) idx = -(idx + 1);
            list.add(idx, sum);
        }
        return total;
    }
}

Approach 3

Level III: Min-Heap (Optimal)

Intuition

To minimize the cost, we should always combine the two smallest sticks available. A Min-Heap is the perfect data structure for this, as it allows us to efficiently extract the two smallest elements and insert their sum.

Thought Process

Push all stick lengths into a Min-Heap.
While the heap contains more than one stick:
- Extract the two smallest sticks (s1, s2).
- Calculate their sum (cost = s1 + s2).
- Add cost to the totalCost.
- Push the new combined stick (cost) back into the heap.
Once only one stick remains in the heap, return totalCost.

⏱ O(N log N) since we perform `HeapPop` and `HeapPush` N-1 times💾 O(N) for storing elements in the heap

Detailed Dry Run

sticks = [1,8,3,5]

Heap: [1, 3, 5, 8], Cost: 0
Pop 1, 3. Sum = 4. Cost = 4. Push 4. Heap: [4, 5, 8]
Pop 4, 5. Sum = 9. Cost = 4 + 9 = 13. Push 9. Heap: [8, 9]
Pop 8, 9. Sum = 17. Cost = 13 + 17 = 30. Push 17. Heap: [17]
One element left. Return 30.

java

import java.util.*;

public class Main {
    public static int connectSticks(int[] sticks) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int stick : sticks) minHeap.add(stick);
        
        int totalCost = 0;
        while (minHeap.size() > 1) {
            int stick1 = minHeap.poll();
            int stick2 = minHeap.poll();
            int cost = stick1 + stick2;
            totalCost += cost;
            minHeap.add(cost);
        }
        return totalCost;
    }

    public static void main(String[] args) {
        System.out.println(connectSticks(new int[]{1, 8, 3, 5})); // 30
    }
}

Find Median from Data Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

Visual Representation

Stream: [2, 3, 4]

addNum(2) -> [2] (Median = 2.0)
addNum(3) -> [2, 3] (Median = (2+3)/2 = 2.5)
addNum(4) -> [2, 3, 4] (Median = 3.0)

Two Heaps State:
Lower (Max-Heap) | Upper (Min-Heap)
[2]              | []
[2]              | [3]           
[2, 3](pop->[2]) | [3, 4](push 3)
[2, 3]           | [4]

Hard

Examples

Input: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output: [null, null, null, 1.5, null, 2.0]

Approach 1

Level I: Array and Insertion Sort

Intuition

Maintain a dynamically growing array. Every time a new number is added, keep the array sorted by placing the new number in its correct position. When calculating the median, simply access the middle element(s).

Thought Process

Store numbers in a standard list or array.
On addNum(n):
- Find the correct position to insert n so the collection remains sorted.
- Insert n.
On findMedian():
- If the size is odd, return list[size / 2].
- If the size is even, return (list[size / 2 - 1] + list[size / 2]) / 2.0.

⏱ O(N) for `addNum` (to shift elements during insertion), O(1) for `findMedian`💾 O(N) to store the stream

Detailed Dry Run

Calls: add(1), add(2), find(), add(3), find()

add(1): Array = [1]
add(2): Insert 2. Array = [1, 2]
find(): Even size 2. Return (1+2)/2.0 = 1.5
add(3): Insert 3. Array = [1, 2, 3]
find(): Odd size 3. Middle is index 1. Return 2.0

java

import java.util.*;

class MedianFinder {
    List<Integer> list;

    public MedianFinder() {
        list = new ArrayList<>();
    }
    
    public void addNum(int num) {
        // Uses Binary Search to find insertion index, then shifts elements O(N)
        int pos = Collections.binarySearch(list, num);
        if (pos < 0) pos = -(pos + 1);
        list.add(pos, num);
    }
    
    public double findMedian() {
        int n = list.size();
        if (n % 2 == 1) return list.get(n / 2);
        return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
    }
}

public class Main {
    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();
        mf.addNum(1);
        mf.addNum(2);
        System.out.println(mf.findMedian()); // 1.5
        mf.addNum(3);
        System.out.println(mf.findMedian()); // 2.0
    }
}

Approach 2

Level II: TreeMap of Counts

Intuition

Use a sorted map (TreeMap in Java, SortedDict in Python) to store the frequency of each number. To find the median, we iterate through the map to find the middle element(s) based on the total count.

⏱ O(log N) for `addNum`, O(N) for `findMedian` (worst case if we iterate the whole map)💾 O(K) where K is the number of unique elements

Detailed Dry Run

Calls: add(1), add(2), find(), add(3), find()

add(1): map={1:1}, total=1
add(2): map={1:1, 2:1}, total=2
find(): total=2. Median is at pos 1, 2. Summing counts: at 1, count=1(pos 0-0), at 2, count=1(pos 1-1). Avg of 1 and 2 is 1.5.
add(3): map={1:1, 2:1, 3:1}, total=3
find(): total=3. Median is at pos 1. Summing: pos 1 is val 2. Return 2.0

java

import java.util.*;

class MedianFinder {
    TreeMap<Integer, Integer> counts;
    int totalCount;

    public MedianFinder() {
        counts = new TreeMap<>();
        totalCount = 0;
    }
    
    public void addNum(int num) {
        counts.put(num, counts.getOrDefault(num, 0) + 1);
        totalCount++;
    }
    
    public double findMedian() {
        int midLeft = (totalCount + 1) / 2;
        int midRight = totalCount / 2 + 1;
        int currentPos = 0;
        Integer leftVal = null, rightVal = null;

        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            currentPos += entry.getValue();
            if (leftVal == null && currentPos >= midLeft) leftVal = entry.getKey();
            if (rightVal == null && currentPos >= midRight) rightVal = entry.getKey();
            if (leftVal != null && rightVal != null) break;
        }
        return (leftVal + rightVal) / 2.0;
    }
}

Approach 3

Level III: Two Heaps (Optimal)

Intuition

To find the median instantly, we only need access to the middle one or two values. We can split the stream into a lower half (stored in a Max-Heap) and an upper half (stored in a Min-Heap). The Max-Heap holds the maximum of the lower values, while the Min-Heap holds the minimum of the upper values.

Thought Process

low: A Max-Heap to store the smaller half of the numbers.
high: A Min-Heap to store the larger half of the numbers.
When adding num:
- Always push to low, then pop the largest from low and push it to high (to ensure every element in low is smaller than elements in high).
- Balance the heaps: If high has more elements than low, pop high and push to low.
When finding median:
- If sizes are unequal, the extra element is in low, so return the top of low.
- If equal, return (low.top() + high.top()) / 2.0.

⏱ O(log N) for `addNum`, O(1) for `findMedian`💾 O(N) to store the elements in two heaps

Detailed Dry Run

add(1): low pulls 1, pushes to high; high size > low, wait, step-by-step:

Add 1: Push to low -> low=[1]. Pop low (1) -> Push to high. high=[1]. high size(1) > low size(0) -> Pop high(1) -> push to low. low=[1], high=[].
Add 2: Push to low -> low=[2,1]. Pop low(2) -> push to high. high=[2], low=[1]. Sizes equal.
Median: (1 + 2)/2.0 = 1.5
Add 3: Push to low -> low=[3,1]. Pop low(3) -> push to high. high=[2,3], low=[1]. high size(2) > low size(1) -> Pop high(2) -> push to low. low=[2,1], high=[3].
Median: low has extra. Return 2.0.

java

import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> low;
    private PriorityQueue<Integer> high;

    public MedianFinder() {
        low = new PriorityQueue<>(Collections.reverseOrder()); // Max-Heap
        high = new PriorityQueue<>(); // Min-Heap
    }
    
    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        
        if (low.size() < high.size()) {
            low.offer(high.poll());
        }
    }
    
    public double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return (low.peek() + high.peek()) / 2.0;
    }
}

public class Main {
    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();
        mf.addNum(1);
        mf.addNum(2);
        System.out.println(mf.findMedian()); // 1.5
        mf.addNum(3);
        System.out.println(mf.findMedian()); // 2.0
    }
}

Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Visual Representation

nums = [1,3,-1,-3,5,3,6,7], k = 3

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Hard

Examples

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Input: nums = [1], k = 1
Output: [1]

Approach 1

Level I: Max-Heap (Lazy Removal)

Intuition

A Max-Heap easily gives us the maximum element. However, when the window slides, removing the element that left the window from the middle of the heap is O(N). Instead, we can use lazy removal: we store (value, index) in the heap. We only remove elements from the top of the heap if their index is outside the current window's bounds.

Thought Process

Use a Max-Heap storing pairs of (nums[i], i).
Initialize the heap with the first k elements.
The max of the first window is the top of the heap.
Slide the window from i = k to N - 1:
- Push (nums[i], i) into the heap.
- Check the top of the heap. If its index is <= i - k, it means it's outside the window. Pop it.
- Keep popping until the top is inside the window.
- Record the top's value as the max for the current window.

⏱ O(N log N) because we might insert N elements, and each insertion/extraction is logarithmic💾 O(N) in the worst case if elements are continuously increasing (they are never lazily removed until the end)

Detailed Dry Run

nums = [1,3,-1,-3,5,3], k = 3

Init k=3: Heap = [(3,1), (1,0), (-1,2)]. Max = 3.
i=3 (val=-3): Push (-3,3). Heap = [(3,1), (1,0), (-1,2), (-3,3)]. Top idx=1 is inside window (3-3=0, 1>0). Max = 3.
i=4 (val=5): Push (5,4). Heap = [(5,4), (3,1),...]. Top idx=4 is inside. Max = 5.
i=5 (val=3): Push (3,5). Heap = [(5,4), ...]. Top idx=4 is inside. Max = 5.

java

import java.util.*;

public class Main {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < k; i++) {
            maxHeap.offer(new int[]{nums[i], i});
        }
        
        int[] res = new int[nums.length - k + 1];
        res[0] = maxHeap.peek()[0];
        
        for (int i = k; i < nums.length; i++) {
            maxHeap.offer(new int[]{nums[i], i});
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            res[i - k + 1] = maxHeap.peek()[0];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res)); // [3, 3, 5, 5, 6, 7]
    }
}

Approach 2

Level II: Balanced BST / Sorted List

Intuition

Maintain a sorted collection of the elements currently in the sliding window. As the window slides, remove the element that is falling out and insert the new element. The maximum is always the last element in the sorted collection.

⏱ O(N log k) where k is the window size💾 O(k) to store the window elements

Detailed Dry Run

nums = [1,3,-1], k = 3

Initial window [1, 3, -1]. Sorted: [-1, 1, 3]. Max = 3.
Slide to [3, -1, -3]: Remove 1, Insert -3. Sorted: [-3, -1, 3]. Max = 3.
Slide to [-1, -3, 5]: Remove 3, Insert 5. Sorted: [-3, -1, 5]. Max = 5.

java

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        TreeMap<Integer, Integer> window = new TreeMap<>();
        int[] res = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            // Add current number
            window.put(nums[i], window.getOrDefault(nums[i], 0) + 1);
            
            // Remove old number if window is full
            if (i >= k) {
                int old = nums[i - k];
                if (window.get(old) == 1) window.remove(old);
                else window.put(old, window.get(old) - 1);
            }
            
            // Record max
            if (i >= k - 1) {
                res[i - k + 1] = window.lastKey();
            }
        }
        return res;
    }
}

Approach 3

Level III: Monotonic Deque (Optimal)

Intuition

If we have a descending sequence in the window, say [5, 4, 2], the maximum is 5. If we add a new number 6, then 5, 4, 2 are completely useless because they are smaller than 6 and will leave the window before 6 does! Thus, a monotonically decreasing deque can perfectly track the useful candidates for being the window's max.

Thought Process

Maintain a deque (double-ended queue) of indices.
The elements represented by indices in the deque are kept in strictly descending order.
Loop over nums[i] from 0 to N-1:
- Maintain Window Bound: If the index at the front of the deque is out of the current window (< i - k + 1), remove it from the front.
- Maintain Descending Order: While the deque is not empty and the element at the back is < nums[i], remove it from the back. (They are useless now).
- Add current index i to the back.
- Once i >= k - 1, the window is fully formed. The maximum is always at the front of the deque, so append nums[deque.front()] to the result.

⏱ O(N) because each element is pushed to and popped from the deque at most once💾 O(k) to store elements in the deque at any given time

Detailed Dry Run

nums = [1,3,-1,-3,5,3], k = 3

i=0, v=1: dq=[0 (val:1)]
i=1, v=3: 1 < 3, pop 0. dq=[1 (val:3)]
i=2, v=-1: -1 < 3, keep. dq=[1, 2]. Window full, max=nums[1]=3
i=3, v=-3: -3 < -1, keep. dq=[1, 2, 3]. max=nums[1]=3
i=4, v=5: front 1 out of bounds (1 <= 4-3). pop 1. val 5 > -1, -3. pop 2, 3. push 4. dq=[4 (val:5)]. max=5

java

import java.util.*;

public class Main {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) return new int[0];
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        
        for (int i = 0; i < nums.length; i++) {
            // Remove indices that are out of bounds
            while (!q.isEmpty() && q.peekFirst() < i - k + 1) {
                q.pollFirst();
            }
            // Remove smaller elements in k range
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
                q.pollLast();
            }
            
            q.offerLast(i);
            // Add to result when window reaches size k
            if (i >= k - 1) {
                res[i - k + 1] = nums[q.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res)); // [3, 3, 5, 5, 6, 7]
    }
}

Trapping Rain Water II

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Visual Representation

heightMap =
[1, 4, 3, 1, 3, 2]
[3, 2, 1, 3, 2, 4]
[2, 3, 3, 2, 3, 1]

Water trapped at (1,1) (height 2): bounded by 3, 4, 3, 3. Can hold 1 unit.
Water trapped at (1,2) (height 1): bounded by 3, 2, 3, 3. Can hold 2 units.
Total trapped = 14 units.

Min-Heap expanding from boundaries:
Push all boundary cells to Min-Heap.
Always pop the lowest boundary (weakest link) to see if water can flow into its neighbors.

Hard

Examples

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 14

Input: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output: 10

Approach 1

Level I: Iterative Water Level Updates

Intuition

The water level at any cell (r, c) is determined by the maximum of its own height and the minimum water level of its neighbors. We can start by assuming every inner cell can hold infinite water, and boundary cells hold exactly their height. Then, we iteratively relax (update) the inner cells until the water levels stabilize (no more changes occur), similar to the Bellman-Ford algorithm.

⏱ O((M*N)^2) in the worst-case because we might need to iterate through the entire matrix M*N times until convergence💾 O(M*N) to store the current water levels

Detailed Dry Run

Grid 3x3 (Heights): 3 3 3 3 1 3 3 3 3

Init Water: 3 3 3 3 INF 3 3 3 3

Iter 1: Water[1,1] = max(H[1,1]=1, min(W[0,1]=3, W[2,1]=3, W[1,0]=3, W[1,2]=3)) = max(1, min(3,3,3,3)) = 3 Changes = True. Next loop Changes = False. Trapped at (1,1) = Water[1,1] - H[1,1] = 3 - 1 = 2.

java

public class Main {
    public static int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0) return 0;
        int m = heightMap.length, n = heightMap[0].length;
        int[][] water = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    water[i][j] = heightMap[i][j];
                } else {
                    water[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        int[] dirs = {-1, 0, 1, 0, -1};
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int r = 1; r < m - 1; r++) {
                for (int c = 1; c < n - 1; c++) {
                    int minNeighbor = Integer.MAX_VALUE;
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dirs[d], nc = c + dirs[d + 1];
                        minNeighbor = Math.min(minNeighbor, water[nr][nc]);
                    }
                    int newWater = Math.max(heightMap[r][c], minNeighbor);
                    if (newWater < water[r][c]) {
                        water[r][c] = newWater;
                        changed = true;
                    }
                }
            }
        }
        
        int trapped = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                trapped += water[i][j] - heightMap[i][j];
            }
        }
        return trapped;
    }

    public static void main(String[] args) {
        int[][] grid = {{3,3,3},{3,1,3},{3,3,3}};
        System.out.println(trapRainWater(grid)); // 2
    }
}

Approach 2

Level II: 4-Way Boundary Scanning (Upper Bound Heuristic)

Intuition

In the 1D version, the water level at any index is min(maxLeft, maxRight). We can extend this logic to 2D by calculating the maximum height seen from all four cardinal directions (Left, Right, Top, Bottom) for each cell. The water level at (r, c) can be at most the minimum of these four peaks. While this ignores diagonal leaks, it provides an $O(MN)$ heuristic that is faster than iterative relaxation.

⏱ O(M * N) to compute the prefix/suffix maximums in four directions💾 O(M * N) to store the max peaks

Detailed Dry Run

Grid 3x3: 3 3 3 3 1 3 3 3 3 For cell (1,1):

MaxLeft = 3, MaxRight = 3, MaxUp = 3, MaxDown = 3
Level = min(3,3,3,3) = 3
Trapped = 3 - 1 = 2 (Correct in this case).

java

public class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length <= 2) return 0;
        int m = heightMap.length, n = heightMap[0].length;
        int[][] L = new int[m][n], R = new int[m][n], U = new int[m][n], D = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            L[i][0] = heightMap[i][0];
            for (int j = 1; j < n; j++) L[i][j] = Math.max(L[i][j-1], heightMap[i][j]);
            R[i][n-1] = heightMap[i][n-1];
            for (int j = n-2; j >= 0; j--) R[i][j] = Math.max(R[i][j+1], heightMap[i][j]);
        }
        for (int j = 0; j < n; j++) {
            U[0][j] = heightMap[0][j];
            for (int i = 1; i < m; i++) U[i][j] = Math.max(U[i-1][j], heightMap[i][j]);
            D[m-1][j] = heightMap[m-1][j];
            for (int i = m-2; i >= 0; i--) D[i][j] = Math.max(D[i+1][j], heightMap[i][j]);
        }
        
        int ans = 0;
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                int minPeak = Math.min(Math.min(L[i][j], R[i][j]), Math.min(U[i][j], D[i][j]));
                ans += Math.max(0, minPeak - heightMap[i][j]);
            }
        }
        return ans;
    }
}

Approach 3

Level III: Min-Heap + BFS (Optimal)

Intuition

Water flows from high places to low places, but its maximum volume is gated by the weakest link (lowest boundary) surrounding it. If we start from the outer boundaries and always process the lowest boundary segment inwards (using a Min-Heap), we simulate how water would spill over. If the neighbor is lower than our current boundary, it fills up with water to meet our boundary height.

⏱ O(MN log MN) because every cell is pushed into and popped out of the Min-Heap once💾 O(MN) for the Min-Heap and visited matrix

Detailed Dry Run

Grid: 3 3 3 3 1 3 3 3 3

Push all boundaries to Min-Heap: (3,0,0),(3,0,1)... Visited boundary.
Pop (3,0,1). Check neighbor (1,1). It's unvisited. Height is 1.
Inner height 1 < Boundary height 3. Trapped = 3 - 1 = 2.
Push neighbor (1,1) into Heap with updated height max(1, 3) = 3, mark visited.
Continue popping. Other neighbors of (1,1) are boundaries and visited. Return total trapped = 2.

java

import java.util.*;

public class Main {
    public static int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0) return 0;
        int m = heightMap.length, n = heightMap[0].length;
        
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[][] visited = new boolean[m][n];
        
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                    minHeap.offer(new int[]{heightMap[r][c], r, c});
                    visited[r][c] = true;
                }
            }
        }
        
        int[] dirs = {-1, 0, 1, 0, -1};
        int trapped = 0, currentMax = Integer.MIN_VALUE;
        
        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int height = curr[0], r = curr[1], c = curr[2];
            currentMax = Math.max(currentMax, height);
            
            for (int d = 0; d < 4; d++) {
                int nr = r + dirs[d], nc = c + dirs[d + 1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    if (heightMap[nr][nc] < currentMax) {
                        trapped += currentMax - heightMap[nr][nc];
                    }
                    minHeap.offer(new int[]{heightMap[nr][nc], nr, nc});
                }
            }
        }
        return trapped;
    }

    public static void main(String[] args) {
        int[][] grid = {{3,3,3},{3,1,3},{3,3,3}};
        System.out.println(trapRainWater(grid)); // 2
    }
}

Minimum Cost to Hire K Workers

There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.

We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.

Visual Representation

quality = [10, 20, 5], wage = [70, 50, 30], k = 2

Ratios (wage/quality):
Worker 0: 70/10 = 7.0
Worker 1: 50/20 = 2.5
Worker 2: 30/5 = 6.0

Sorted by ratio:
[W1(2.5, q:20), W2(6.0, q:5), W0(7.0, q:10)]

To hire W2 and W1, base ratio is 6.0.
Cost = 6.0 * (20 + 5) = 150.0

To hire W0 and W2, base ratio is 7.0.
Cost = 7.0 * (10 + 5) = 105.0
Min cost = 105.0

Hard

Examples

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667

Approach 1

Level I: Sort by Ratio and Brute Force K-Smallest

Intuition

The total pay for K workers is determined by the highest wage / quality ratio among the chosen K workers. If we sort workers by this ratio, when we consider the i-th worker in the sorted list as having the maximum ratio, any K-1 workers before i can be hired at this ratio. To minimize cost, we should simply pick the K-1 workers with the smallest qualities from 0 to i-1.

Thought Process

Pair each worker's quality with their wage/quality ratio.
Sort all workers by their ratio in ascending order.
Iterate i from k - 1 to n - 1 (a valid window to pick k workers).
For each i, the ratio is worker[i].ratio.
We need to pick k qualities from index 0 to i (including worker[i].quality) that are the smallest. Since worker[i] must be included, we pick worker[i].quality + k-1 smallest qualities from 0 to i-1.
For a brute force approach, extract all qualities from 0 to i, sort them, sum the first k, and multiply by the ratio.
Keep track of the minimum cost.

⏱ O(N^2 log N) because for each of the N elements, we sort an array of size up to N💾 O(N) to store the workers and temporary arrays

Detailed Dry Run

quality = [10,20,5], wage = [70,50,30], k = 2 Ratios sorted: [(2.5,20), (6.0,5), (7.0,10)]

i=1 (ratio=6.0, q=5). We need 2 qualities from idx 0 to 1. Qualities: [20, 5]. Sorted: [5, 20]. Sum = 25. Cost = 6.0 * 25 = 150.0. Min = 150.0
i=2 (ratio=7.0, q=10). We need 2 qualities from idx 0 to 2. Qualities: [20, 5, 10]. Sorted: [5, 10, 20]. Sum = 5 + 10 = 15. Cost = 7.0 * 15 = 105.0. Min = 105.0

java

import java.util.*;

public class Main {
    static class Worker {
        double ratio;
        int quality;
        public Worker(double r, int q) { ratio = r; quality = q; }
    }
    
    public static double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Worker[] workers = new Worker[n];
        for (int i = 0; i < n; i++) {
            workers[i] = new Worker((double) wage[i] / quality[i], quality[i]);
        }
        Arrays.sort(workers, (a, b) -> Double.compare(a.ratio, b.ratio));
        
        double minCost = Double.MAX_VALUE;
        for (int i = k - 1; i < n; i++) {
            double currentRatio = workers[i].ratio;
            List<Integer> qualities = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                qualities.add(workers[j].quality);
            }
            Collections.sort(qualities);
            
            int sumQ = 0;
            for (int j = 0; j < k; j++) {
                sumQ += qualities.get(j);
            }
            minCost = Math.min(minCost, sumQ * currentRatio);
        }
        return minCost;
    }

    public static void main(String[] args) {
        int[] quality = {10, 20, 5}, wage = {70, 50, 30};
        System.out.println(mincostToHireWorkers(quality, wage, 2));
    }
}

Approach 2

Level II: Sort by Ratio + BST/TreeMap for Qualities

Intuition

As we iterate through workers sorted by ratio, we just need the $K$ smallest qualities we've seen so far. Instead of sorting all qualities at every step, we can maintain them in a sorted data structure (TreeMap in Java, multiset in C++, SortedList in Python). This reduces the cost of finding the sum of the $K$ smallest qualities to $O(K \log N)$ or better per step.

⏱ O(N^2) or O(N K log N) depending on the BST traversal for sum💾 O(N) to store the workers and the BST

Detailed Dry Run

quality = [10,20,5], wage = [70,50,30], k = 2 Ratios sorted: [(2.5,20), (6.0,5), (7.0,10)]

i=1 (ratio=6.0, q=5): BST = {5, 20}. Sum of 2 smallest = 25. Cost = 6.0 * 25 = 150.0.
i=2 (ratio=7.0, q=10): BST = {5, 10, 20}. Sum of 2 smallest = 15. Cost = 7.0 * 15 = 105.0.

java

import java.util.*;

public class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        double[][] workers = new double[n][2];
        for (int i = 0; i < n; i++) {
            workers[i][0] = (double) wage[i] / quality[i];
            workers[i][1] = (double) quality[i];
        }
        Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));
        
        TreeMap<Integer, Integer> bst = new TreeMap<>();
        double minCost = Double.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int q = (int) workers[i][1];
            bst.put(q, bst.getOrDefault(q, 0) + 1);
            
            if (i >= k - 1) {
                int sumQ = 0, count = 0;
                for (Map.Entry<Integer, Integer> entry : bst.entrySet()) {
                    int qVal = entry.getKey(), qCount = entry.getValue();
                    int take = Math.min(qCount, k - count);
                    sumQ += take * qVal;
                    count += take;
                    if (count == k) break;
                }
                minCost = Math.min(minCost, sumQ * workers[i][0]);
            }
        }
        return minCost;
    }
}

Approach 3

Level III: Max-Heap (Optimal)

Intuition

Why sort qualities again and again? We just need the K smallest qualities seen so far. As we iterate through the workers sorted by ratio, we can maintain a Max-Heap of size K. If we add a new quality and the heap size exceeds K, we pop the maximum quality out. This seamlessly keeps track of the sum of the K smallest qualities in O(log K) time per worker.

⏱ O(N log N) dominated by sorting the workers. Max-Heap operations take O(N log K)💾 O(N) to store the workers array, O(K) for the Max-Heap

Detailed Dry Run

quality = [10,20,5], wage = [70,50,30], k = 2 Workers sorted: [(2.5, q:20), (6.0, q:5), (7.0, q:10)] Wait, k=2. Max-Heap pq, quality_sum = 0

i=0, (2.5, 20): push 20. pq=[20], sum=20. size 1 < 2. Cost: ignore.
i=1, (6.0, 5): push 5. pq=[20,5], sum=25. size 2 == 2. Cost = 25 * 6.0 = 150.0. Min = 150.0
i=2, (7.0, 10): push 10. sum=35. pq=[20,10,5]. size 3 > 2 -> pop max (20). sum = 35 - 20 = 15. Size is now 2. Cost = 15 * 7.0 = 105.0. Min = min(150, 105) = 105.0. Return 105.0

java

import java.util.*;

public class Main {
    static class Worker {
        double ratio;
        int quality;
        public Worker(double r, int q) { ratio = r; quality = q; }
    }
    
    public static double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Worker[] workers = new Worker[n];
        for (int i = 0; i < n; i++) {
            workers[i] = new Worker((double) wage[i] / quality[i], quality[i]);
        }
        Arrays.sort(workers, (a, b) -> Double.compare(a.ratio, b.ratio));
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        double minCost = Double.MAX_VALUE;
        int qualitySum = 0;
        
        for (Worker worker : workers) {
            maxHeap.offer(worker.quality);
            qualitySum += worker.quality;
            
            if (maxHeap.size() > k) {
                qualitySum -= maxHeap.poll();
            }
            
            if (maxHeap.size() == k) {
                minCost = Math.min(minCost, qualitySum * worker.ratio);
            }
        }
        return minCost;
    }

    public static void main(String[] args) {
        int[] quality = {10, 20, 5}, wage = {70, 50, 30};
        System.out.println(mincostToHireWorkers(quality, wage, 2));
    }
}

IPO

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital. Return the maximized final capital.

Visual Representation

k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]

Initial Capital w = 0
Available Projects (capital <= 0): Project 0 (profit 1)

Do Project 0 -> w = 0 + 1 = 1
Projects left: 1 (cap:1, prof:2), 2 (cap:1, prof:3)
Available Projects (capital <= 1): Project 1, Project 2
Pick max profit: Project 2 (profit 3)

Do Project 2 -> w = 1 + 3 = 4
Max Capital = 4

Hard

Examples

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6

Approach 1

Level I: Brute Force Greedy Selection

Intuition

To maximize our final capital, we should always greedily choose the project that we can afford (capital <= current w) and that yields the maximum profit. Once we finish it, our w increases, potentially unlocking new jobs. We can simply scan the list of projects up to k times, picking the best affordable project each time.

⏱ O(K * N) where N is the number of projects. For each of the K projects we want to complete, we might scan the entire array of N projects.💾 O(N) to keep track of which projects have been completed

Detailed Dry Run

k=2, w=0, prof=[1,2,3], cap=[0,1,1]

k=1: Scan all. P0(0<=0, prof 1), P1(1>0), P2(1>0). Best is P0. w=0+1=1. Mark P0 used.
k=2: Scan all. P0(used), P1(1<=1, prof 2), P2(1<=1, prof 3). Best is P2. w=1+3=4. Mark P2 used. Return w=4.

java

public class Main {
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        boolean[] used = new boolean[n];
        
        for (int i = 0; i < k; i++) {
            int maxProfit = -1;
            int bestIndex = -1;
            
            for (int j = 0; j < n; j++) {
                if (!used[j] && capital[j] <= w && profits[j] > maxProfit) {
                    maxProfit = profits[j];
                    bestIndex = j;
                }
            }
            
            if (bestIndex == -1) break; // Cannot afford any more projects
            used[bestIndex] = true;
            w += maxProfit;
        }
        
        return w;
    }

    public static void main(String[] args) {
        int[] profits = {1, 2, 3};
        int[] capital = {0, 1, 1};
        System.out.println(findMaximizedCapital(2, 0, profits, capital)); // 4
    }
}

Approach 2

Level II: Sort Projects by Profit and Scan

Intuition

To improve our search for the maximum profit, we can sort all projects by their profit in descending order. Then, for each selection, we scan this sorted list from the beginning and pick the first project that we can afford (capital <= w). Once picked, we mark it used and repeat.

⏱ O(N log N + K * N) where N is the number of projects. Sorting takes N log N, and each of the K steps might scan up to N elements.💾 O(N) for the sorted list of projects and the used tracker

Detailed Dry Run

k=2, w=0, prof=[1,2,3], cap=[0,1,1] Sorted by Profit (desc): [(3,1), (2,1), (1,0)]

k=1: Scan. (3, cap:1 > 0) skip. (2, cap:1 > 0) skip. (1, cap:0 <= 0) PICK. w = 0 + 1 = 1.
k=2: Scan. (3, cap:1 <= 1) PICK. w = 1 + 3 = 4. Return w = 4.

java

import java.util.*;

public class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = profits[i];
            projects[i][1] = capital[i];
        }
        
        // Sort by profit descending
        Arrays.sort(projects, (a, b) -> Integer.compare(b[0], a[0]));
        
        boolean[] used = new boolean[n];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < n; j++) {
                if (!used[j] && projects[j][1] <= w) {
                    w += projects[j][0];
                    used[j] = true;
                    break;
                }
            }
        }
        return w;
    }
}

Approach 3

Level III: Two Heaps (Optimal)

Intuition

Instead of scanning the whole array every time, we can maintain two collections: one for projects we CAN'T afford yet (sorted by capital required), and one for projects we CAN afford (sorted by profit). As our capital w grows, we transfer projects from the "can't afford" group to the "can afford" group. This perfectly maps to using a Min-Heap for capital and a Max-Heap for profits.

⏱ O(N log N) to sort projects and insert/remove from heaps. Extracting up to K items takes O(K log N).💾 O(N) for holding the projects and the priority queues.

Detailed Dry Run

k=2, w=0, prof=[1,2,3], cap=[0,1,1]

Pair & Sort by Capital: [(0,1), (1,2), (1,3)] -> Min-Heap equivalent.
w=0. Move affordable to Max-Heap (profits). Max-Heap gets (profit=1) from (0,1). Max-Heap = [1].
Can't move (1,2) or (1,3) since 1 > 0.
Do job 1 (k=1): pop Max-Heap (1). w = 0 + 1 = 1.
New w=1. Check Min-Heap. Both (1,2) and (1,3) are now affordable. Push their profits (2, 3) to Max-Heap. Max-Heap = [3, 2].
Do job 2 (k=2): pop Max-Heap (3). w = 1 + 3 = 4.
k=2 reached. Return w=4.

java

import java.util.*;

public class Main {
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        
        // Sort projects by capital required
        Arrays.sort(projects, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Max-Heap to store affordable profits
        PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        int ptr = 0;
        for (int i = 0; i < k; i++) {
            // Push all currently affordable projects to the max heap
            while (ptr < n && projects[ptr][0] <= w) {
                maxProfitHeap.offer(projects[ptr][1]);
                ptr++;
            }
            
            if (maxProfitHeap.isEmpty()) break;
            
            w += maxProfitHeap.poll();
        }
        
        return w;
    }

    public static void main(String[] args) {
        int[] profits = {1, 2, 3};
        int[] capital = {0, 1, 1};
        System.out.println(findMaximizedCapital(2, 0, profits, capital)); // 4
    }
}

Kth Smallest Element in Sorted Matrix

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Visual Representation

matrix =
[  1,  5,  9 ]
[ 10, 11, 13 ]
[ 12, 13, 15 ]
k = 8

All elements sorted: [1, 5, 9, 10, 11, 12, 13, 13, 15]
The 8th smallest is 13.

Min-Heap approach (similar to Merge K sorted lists):
Initial heap: [(1,0,0)] <- (val, row, col)
Expand smallest, add right neighbor and maybe down

Medium

Examples

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13

Input: matrix = [[-5]], k = 1
Output: -5

Approach 1

Level I: Flatten and Sort

Intuition

The simplest approach is to collect all elements from the matrix into a flat list, sort them, and return the element at index k - 1. While not leveraging the sorted property of the matrix, this is intuitive and correct.

⏱ O(N^2 log N) where N is the matrix dimension, for sorting all N^2 elements💾 O(N^2) to store all elements in a flat array

Detailed Dry Run

matrix = [[1,5,9],[10,11,13],[12,13,15]], k=8

Flatten: [1, 5, 9, 10, 11, 13, 12, 13, 15]
Sort: [1, 5, 9, 10, 11, 12, 13, 13, 15]
Return sorted[k-1] = sorted[7] = 13

java

import java.util.*;

public class Main {
    public static int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int[] flat = new int[n * n];
        int idx = 0;
        for (int[] row : matrix) {
            for (int val : row) {
                flat[idx++] = val;
            }
        }
        Arrays.sort(flat);
        return flat[k - 1];
    }

    public static void main(String[] args) {
        int[][] m = {{1,5,9},{10,11,13},{12,13,15}};
        System.out.println(kthSmallest(m, 8)); // 13
    }
}

Approach 2

Level II: Binary Search on Value Range

Intuition

Since the matrix is sorted, any element X has a predictable number of elements smaller than or equal to it. We can binary search for the value X in the range [matrix[0][0], matrix[n-1][n-1]]. For each middle value, we count how many elements are <= mid in $O(N)$ time using the sorted property.

⏱ O(N log(Max - Min)) where Max and Min are the matrix extremes💾 O(1)

Detailed Dry Run

matrix = [[1,5,9],[10,11,13],[12,13,15]], k=8 Range: [1, 15], Mid = 8 Count <= 8: (1, 5) from row 0, none from others. Count = 2. 2 < 8, search [9, 15]. Mid = 12. Count <= 12: (1,5,9), (10,11), (12). Count = 6. 6 < 8, search [13, 15]. Mid = 14. Count <= 14: All but 15. Count = 8. 8 == 8, result could be 14, search [13, 13]. Finally converge to 13.

java

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int low = matrix[0][0], high = matrix[n - 1][n - 1];
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countLessEqual(matrix, mid) < k) low = mid + 1;
            else high = mid;
        }
        return low;
    }
    
    private int countLessEqual(int[][] matrix, int target) {
        int n = matrix.length, count = 0;
        int row = n - 1, col = 0;
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= target) {
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        return count;
    }
}

Approach 3

Level III: Min-Heap (K Merged Sorted Lists)

Intuition

The matrix is essentially N sorted rows that we want to merge. We can use the same technique as "Merge K Sorted Lists": start a Min-Heap with the first element of each row. Pop the minimum, push its right neighbor. After k pops, the last popped element is the answer. Optimized: we only need to start with the first column (N elements) and expand row by row.

⏱ O(K log N) where N is the matrix dimension. We pop K times and each heap operation is O(log N).💾 O(N) for the Min-Heap which holds at most N elements.

Detailed Dry Run

matrix = [[1,5,9],[10,11,13],[12,13,15]], k=8 Heap = [(1,r:0,c:0), (10,r:1,c:0), (12,r:2,c:0)]

Pop (1). Push right (5,0,1). Heap=[(5,0,1),(10,1,0),(12,2,0)]. Count=1.
Pop (5). Push (9,0,2). Count=2.
Pop (9). No right (col 3 out of range). Count=3.
Pop (10). Push (11,1,1). Count=4.
Pop (11). Push (13,1,2). Count=5.
Pop (12). Push (13,2,1). Count=6.
Pop (13). Push (13,1,3) - out of range. Count=7.
Pop (13). Count=8. Return 13.

java

import java.util.*;

public class Main {
    public static int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        // Min-Heap: {value, row, col}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        for (int r = 0; r < n; r++) {
            minHeap.offer(new int[]{matrix[r][0], r, 0});
        }
        
        int result = 0;
        for (int i = 0; i < k; i++) {
            int[] curr = minHeap.poll();
            result = curr[0];
            int row = curr[1], col = curr[2];
            if (col + 1 < n) {
                minHeap.offer(new int[]{matrix[row][col + 1], row, col + 1});
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] m = {{1,5,9},{10,11,13},{12,13,15}};
        System.out.println(kthSmallest(m, 8)); // 13
    }
}

Maximum Performance of a Team

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of their speeds multiplied by the minimum efficiency among their engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 10^9 + 7.

Visual Representation

n=6, k=2, speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2]

Key Insight: Sort by efficiency descending.
For each engineer i as the "min efficiency" of the group,
pick the k fastest engineers from 0..i (including i).

Sorted by eff desc: (9,1),(7,5),(5,2),(4,10),(3,3),(2,8)

- Min eff = 9: Team = [(1,9)]. Perf = 1*9 = 9
- Min eff = 7: Team = [(1,9),(5,7)]. Sum speeds=6. Perf=6*7=42
- Min eff = 5: Team = [(2,5),(5,7),(1,9)]. Speeds=[1,5,2]. Sum k=2 fastest=5+2=7. Perf=7*5=35
- Min eff = 4: Team picks (10,4) as one, need 2 fastest. Max perf = (10+5)*4 = 60

Hard

Examples

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68

Approach 1

Level I: Brute Force - Check All Subsets

Intuition

Try all possible subsets of at most k engineers from the n engineers. For each subset, compute performance = (sum of speeds) * (minimum efficiency). Return the maximum. This is correct but exponential in complexity.

⏱ O(2^N * N) — exponential, infeasible for large N💾 O(N) for recursion stack

Detailed Dry Run

n=4, k=2, speed=[2,10,3,1], efficiency=[5,4,3,9] Subsets of size 1: {0}->25=10, {1}->104=40, {2}->33=9, {3}->19=9 Subsets of size 2: {0,1}->12min(5,4)=48, {0,2}->5min(5,3)=15, {0,3}->3min(5,9)=15, {1,2}->13min(4,3)=39, {1,3}->11min(4,9)=44, {2,3}->4min(3,9)=12 Max = 48

java

public class Main {
    static final int MOD = 1_000_000_007;
    static int n, k;
    static int[] speed, efficiency;
    static long maxPerf = 0;
    
    static void dfs(int idx, int count, long sumSpeed, int minEff) {
        if (count > 0) {
            maxPerf = Math.max(maxPerf, sumSpeed * minEff);
        }
        if (count == k || idx == n) return;
        
        for (int i = idx; i < n; i++) {
            dfs(i + 1, count + 1, sumSpeed + speed[i], Math.min(minEff, efficiency[i]));
        }
    }
    
    public static int maxPerformance(int n_, int[] sp, int[] eff, int k_) {
        n = n_; k = k_; speed = sp; efficiency = eff;
        maxPerf = 0;
        dfs(0, 0, 0, Integer.MAX_VALUE);
        return (int)(maxPerf % MOD);
    }

    public static void main(String[] args) {
        System.out.println(maxPerformance(6, new int[]{2,10,3,1,5,8}, new int[]{5,4,3,9,7,2}, 2)); // 60
    }
}

Approach 2

Level II: Sort by Efficiency and Search K-Fastest

Intuition

To improve on brute force, we can sort the engineers by their efficiency in descending order. By doing so, for each engineer i, if we consider them as the minimum efficiency in the team, we only need to look at engineers from 0 to i (who all have efficiency >= eff[i]) and pick the k fastest ones.

⏱ O(N^2 log N) because for each of the N engineers, we sort the prefix of speeds to find the k fastest💾 O(N) to store the engineers and prefix speeds

Detailed Dry Run

n=4, k=2, speed=[2,10,3,1], efficiency=[5,4,3,9] Sorted: (9,1), (5,2), (4,10), (3,3)

i=0, Eff=9: prefix=[1]. Sum k=2 fastest = 1. Perf = 1*9=9.
i=1, Eff=5: prefix=[1,2]. Sum k=2 fastest = 3. Perf = 3*5=15.
i=2, Eff=4: prefix=[1,2,10]. Sum k=2 fastest = 12. Perf = 12*4=48.
i=3, Eff=3: prefix=[1,2,10,3]. Sum k=2 fastest = 13. Perf = 13*3=39. Max = 48.

java

import java.util.*;

public class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        long MOD = 1_000_000_007L;
        int[][] engineers = new int[n][2];
        for (int i = 0; i < n; i++) {
            engineers[i][0] = efficiency[i];
            engineers[i][1] = speed[i];
        }
        Arrays.sort(engineers, (a, b) -> b[0] - a[0]);

        long maxPerf = 0;
        List<Integer> prefixSpeeds = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            prefixSpeeds.add(engineers[i][1]);
            Collections.sort(prefixSpeeds, Collections.reverseOrder());
            
            long sumSpeed = 0;
            for (int j = 0; j < Math.min(k, prefixSpeeds.size()); j++) {
                sumSpeed += prefixSpeeds.get(j);
            }
            maxPerf = Math.max(maxPerf, sumSpeed * engineers[i][0]);
        }
        return (int) (maxPerf % MOD);
    }
}

Approach 3

Level III: Sort by Efficiency + Min-Heap (Optimal)

Intuition

Key Insight: When we pick any subset of engineers, the performance is bottlenecked by the minimum efficiency. If we fix the minimum efficiency to be efficiency[i], then we should include engineer i in the team AND pick the k-1 fastest engineers from all engineers who have efficiency >= efficiency[i].

If we sort engineers by efficiency in descending order, as we iterate through them, the current engineer i has the minimum efficiency seen so far. We need the maximum sum of speeds from engineer 0 to i. We maintain a Min-Heap of size k storing speeds — when the heap exceeds k, we pop the smallest speed. This ensures our heap always holds the k largest speeds.

⏱ O(N log N) for sorting and O(N log K) for heap operations💾 O(K) for the Min-Heap

Detailed Dry Run

n=6, k=2, sp=[2,10,3,1,5,8], eff=[5,4,3,9,7,2] Sort by eff desc: [(9,1),(7,5),(5,2),(4,10),(3,3),(2,8)] min_heap=[], speed_sum=0, best=0

(9,sp=1): push 1. sum=1. size=1<=2. perf=1*9=9. best=9.
(7,sp=5): push 5. sum=6. size=2<=2. perf=6*7=42. best=42.
(5,sp=2): push 2. sum=8. size=3>2. pop min(1). sum=7. perf=7*5=35. best=42.
(4,sp=10): push 10. sum=17. size=3>2. pop min(2). sum=15. perf=15*4=60. best=60.
(3,sp=3): push 3. sum=18. size=3>2. pop min(3). sum=15. perf=15*3=45. best=60. Return 60 % MOD = 60

java

import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;
    
    public static int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> efficiency[b] - efficiency[a]);
        
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        long speedSum = 0, best = 0;
        
        for (int idx : indices) {
            minHeap.offer(speed[idx]);
            speedSum += speed[idx];
            
            if (minHeap.size() > k) {
                speedSum -= minHeap.poll();
            }
            
            best = Math.max(best, speedSum * efficiency[idx]);
        }
        
        return (int)(best % MOD);
    }

    public static void main(String[] args) {
        System.out.println(maxPerformance(6, new int[]{2,10,3,1,5,8}, new int[]{5,4,3,9,7,2}, 2)); // 60
    }
}

Minimum Interval to Include Each Query

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] represents an inclusive interval [left_i, right_i]. You are also given an integer array queries.

The answer to the jth query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. The size of an interval is equal to right_i - left_i + 1.

Return an array containing the answers to the queries.

Visual Representation

intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]

Query 2: Intervals covering 2 -> [1,4](size 4), [2,4](size 3). Min = 3
Query 3: Intervals covering 3 -> [1,4](size 4), [2,4](size 3), [3,6](size 4). Min = 3
Query 4: Intervals covering 4 -> [1,4](size 4), [2,4](size 3), [3,6](size 4), [4,4](size 1). Min = 1
Query 5: Intervals covering 5 -> [3,6](size 4). Min = 4

Hard

Examples

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]

Approach 1

Level I: Brute Force - Check Every Interval Per Query

Intuition

For each query, scan all intervals to find which ones contain the query point. Among all covering intervals, choose the one with the minimum size. If no interval covers the query, return -1.

⏱ O(N * Q) where N is the number of intervals and Q is the number of queries💾 O(1) extra besides the output array

Detailed Dry Run

intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] Query 2: [1,4] covers 2? Yes. Size = 4 [2,4] covers 2? Yes. Size = 3 [3,6] covers 2? No. [4,4] covers 2? No. Min = 3 Query 4: All 4 cover 4. Min = [4,4].size = 1

java

public class Main {
    public static int[] minInterval(int[][] intervals, int[] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        
        for (int j = 0; j < n; j++) {
            int q = queries[j];
            int minSize = Integer.MAX_VALUE;
            for (int[] interval : intervals) {
                if (interval[0] <= q && q <= interval[1]) {
                    int size = interval[1] - interval[0] + 1;
                    minSize = Math.min(minSize, size);
                }
            }
            ans[j] = minSize == Integer.MAX_VALUE ? -1 : minSize;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] iv = {{1,4},{2,4},{3,6},{4,4}};
        int[] q = {2,3,4,5};
        int[] res = minInterval(iv, q);
        System.out.println(java.util.Arrays.toString(res)); // [3, 3, 1, 4]
    }
}

Approach 2

Level II: Sort Intervals by Size and Scan

Intuition

To optimize the search for the smallest interval, we can pre-sort all intervals by their size (right - left + 1). For each query, we then scan the sorted intervals and return the first one that contains the query point. Since the intervals are sorted by size, the first valid interval we find is guaranteed to be the smallest.

⏱ O(N log N + Q * N) where N is the number of intervals and Q is the number of queries💾 O(N) to store the sorted intervals

Detailed Dry Run

intervals = [[1,4],[2,4],[3,6],[4,4]], q = 2 Sizes: [1,4]->4, [2,4]->3, [3,6]->4, [4,4]->1 Sorted by Size: [[4,4], [2,4], [1,4], [3,6]] Query 2: [4,4] covers 2? No. [2,4] covers 2? Yes. STOP. ans = 3. Query 4: [4,4] covers 4? Yes. STOP. ans = 1.

java

import java.util.*;

public class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int n = queries.length;
        int[][] sortedIv = new int[intervals.length][3];
        for (int i = 0; i < intervals.length; i++) {
            sortedIv[i][0] = intervals[i][0];
            sortedIv[i][1] = intervals[i][1];
            sortedIv[i][2] = intervals[i][1] - intervals[i][0] + 1;
        }
        
        Arrays.sort(sortedIv, (a, b) -> Integer.compare(a[2], b[2]));
        
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int q = queries[i];
            ans[i] = -1;
            for (int[] iv : sortedIv) {
                if (iv[0] <= q && q <= iv[1]) {
                    ans[i] = iv[2];
                    break;
                }
            }
        }
        return ans;
    }
}

Approach 3

Level III: Sort + Min-Heap (Sweep Line Approach)

Intuition

Sort both the intervals (by start) and the queries (by value). Use a pointer on intervals and a Min-Heap ordered by interval size.

Process each sorted query:

Add all intervals whose start <= current query to the Min-Heap (they might cover this query).
Remove all intervals from the top of the heap whose end < current query (they expired).
The top of the heap (if any) is the smallest valid interval covering the query.

We must store results keyed by the original query index to return answers in the right order.

⏱ O(N log N + Q log Q + (N+Q) log N) — dominated by sorting and heap operations💾 O(N + Q) for the heap and result map

Detailed Dry Run

iv = [[1,4],[2,4],[3,6],[4,4]], q = [2,3,4,5] Sort intervals by start: [[1,4],[2,4],[3,6],[4,4]] Sort queries with orig idx: [(2,0),(3,1),(4,2),(5,3)] MinHeap sorted by size (right-left+1) ptr=0

q=2: Add 1,4, 2,4. Heap=[(3,[2,4]),(4,[1,4])]. Top=3. ans[0]=3. q=3: Add 3,6. Heap=tops. Remove [2,4] as 4>=3. Top=1,4. ans[1]=3? Let's re-check. Actually heap=[(3,[2,4]),(4,[1,4]),(4,[3,6])]. 2,4 still covers 3. ans[1]=3. q=4: Add 4,4. Heap=[(1,[4,4]),...]. Remove expired: checks 2,4 (4>=4, valid), 1,4 (4>=4, valid), 3,6 (6>=4, valid). Top=4,4. ans[2]=1. q=5: No new. Remove [2,4](4<5 expired). Remove [1,4](4<5 expired). [3,6](6>=5 ok), [4,4](4<5 expired). Heap=[(4,[3,6])]. ans[3]=4.

java

import java.util.*;

public class Main {
    public static int[] minInterval(int[][] intervals, int[] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        
        // Sort intervals by start
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // Sort queries but keep original indices
        Integer[] qIdx = new Integer[n];
        for (int i = 0; i < n; i++) qIdx[i] = i;
        Arrays.sort(qIdx, (a, b) -> queries[a] - queries[b]);
        
        // Min-Heap: {size, end}
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int ptr = 0;
        
        for (int i : qIdx) {
            int q = queries[i];
            
            // Add all intervals starting <= q
            while (ptr < intervals.length && intervals[ptr][0] <= q) {
                int size = intervals[ptr][1] - intervals[ptr][0] + 1;
                heap.offer(new int[]{size, intervals[ptr][1]});
                ptr++;
            }
            
            // Remove intervals that ended before q
            while (!heap.isEmpty() && heap.peek()[1] < q) {
                heap.poll();
            }
            
            ans[i] = heap.isEmpty() ? -1 : heap.peek()[0];
        }
        
        return ans;
    }

    public static void main(String[] args) {
        int[][] iv = {{1,4},{2,4},{3,6},{4,4}};
        int[] q = {2,3,4,5};
        System.out.println(Arrays.toString(minInterval(iv, q))); // [3, 3, 1, 4]
    }
}

Maximum Number of Events

You are given an array of events where events[i] = [startDay_i, endDay_i]. Every event i starts at startDay_i and ends at endDay_i.

You can attend an event i at any day d where startDay_i <= d <= endDay_i. You can only attend one event per day.

Return the maximum number of events you can attend.

Visual Representation

events = [[1,2],[2,3],[3,4]]

Day 1: [1,2] available. Attend it.
Day 2: [2,3] available. Attend it.
Day 3: [3,4] available. Attend it.
Total = 3

Key insight: Each day, attend the event that ends SOONEST (greedy).
This leaves later-ending events available for future days.

Medium

Examples

Input: events = [[1,2],[2,3],[3,4]]
Output: 3

Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4

Approach 1

Level I: Greedy - Sort by Start, Attend First Available

Intuition

Sort events by start day. On each day from 1 to maxDay, try to attend the first available event (one that hasn't been attended and whose start day <= current day). This is a greedy approach that ensures we don't miss starting opportunities.

⏱ O(maxDay * N) where maxDay is the maximum end day and N is the number of events💾 O(N) for the used set

Detailed Dry Run

events = [[1,2],[2,3],[3,4]] sorted by start Day 1: Available (not attended, start<=1, end>=1): [1,2]. Attend [1,2]. Count=1. Day 2: Available: [2,3]. Attend [2,3]. Count=2. Day 3: Available: [3,4]. Attend [3,4]. Count=3. Return 3.

java

import java.util.*;

public class Main {
    public static int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int maxDay = 0;
        for (int[] e : events) maxDay = Math.max(maxDay, e[1]);
        
        boolean[] attended = new boolean[events.length];
        int count = 0;
        
        for (int day = 1; day <= maxDay; day++) {
            // Find the event with smallest end day that starts on or before today
            int bestIdx = -1;
            for (int i = 0; i < events.length; i++) {
                if (!attended[i] && events[i][0] <= day && events[i][1] >= day) {
                    if (bestIdx == -1 || events[i][1] < events[bestIdx][1]) {
                        bestIdx = i;
                    }
                }
            }
            if (bestIdx != -1) {
                attended[bestIdx] = true;
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(maxEvents(new int[][]{{1,2},{2,3},{3,4}})); // 3
    }
}

Approach 2

Level II: Sort by Start + Daily Min-End Search

Intuition

To improve on the basic search, we sort events by their start day. Each day, we identify all events that have already started and haven't been attended. Among these available events, we pick the one that ends the soonest (earliest end day). This ensures we use up events that would expire early, leaving more flexibility for the future.

⏱ O(maxDay * N) where maxDay is the duration of events and N is number of events💾 O(N) for the used tracker

Detailed Dry Run

events = [[1,4],[1,1],[2,2]] sorted. Day 1: Available: [1,4], [1,1]. Ends are 4, 1. Min end is 1. Attend [1,1]. Count=1. Day 2: Available: [1,4], [2,2]. Ends are 4, 2. Min end is 2. Attend [2,2]. Count=2. Day 3: Available: [1,4]. Attend [1,4]. Count=3. Max = 3.

java

import java.util.*;

public class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int maxDay = 0;
        for (int[] e : events) maxDay = Math.max(maxDay, e[1]);
        
        boolean[] used = new boolean[events.length];
        int count = 0;
        for (int day = 1; day <= maxDay; day++) {
            int bestIdx = -1, minEnd = Integer.MAX_VALUE;
            for (int i = 0; i < events.length; i++) {
                if (events[i][0] > day) break; // Optimization from sorting
                if (!used[i] && events[i][1] >= day) {
                    if (events[i][1] < minEnd) {
                        minEnd = events[i][1];
                        bestIdx = i;
                    }
                }
            }
            if (bestIdx != -1) {
                used[bestIdx] = true;
                count++;
            }
        }
        return count;
    }
}

Approach 3

Level III: Sort by Start + Min-Heap of End Days (Optimal)

Intuition

Greedy insight: on each day, among all available events (those that have already started), we should attend the one that ends the soonest. If we sort events by start day and use a Min-Heap of end days, we can efficiently:

Iterate over each day from 1 to maxDay.
Add all events that start on this day to the Min-Heap.
Remove all expired events (heap top end < today).
If the heap isn't empty, attend the event ending soonest (pop from heap), increment count.

⏱ O(N log N) for sorting and heap operations. Each event is pushed and popped at most once.💾 O(N) for the Min-Heap

Detailed Dry Run

events = [[1,2],[2,3],[3,4]] sorted by start ptr=0

Day 1: Add events starting on 1: push end=2. Heap=[2]. Pop 2 (attend). Count=1. Day 2: Add events starting on 2: push end=3. Heap=[3]. Pop 3 (attend). Count=2. Day 3: Add events starting on 3: push end=4. Heap=[4]. Pop 4 (attend). Count=3. Return 3.

java

import java.util.*;

public class Main {
    public static int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // stores end days
        int ptr = 0, n = events.length;
        int maxDay = events[n - 1][1];
        // Not exactly - maxDay needs re-scan
        int maxEndDay = 0;
        for (int[] e : events) maxEndDay = Math.max(maxEndDay, e[1]);
        
        int count = 0;
        for (int day = 1; day <= maxEndDay; day++) {
            // Add all events starting today
            while (ptr < n && events[ptr][0] == day) {
                minHeap.offer(events[ptr][1]);
                ptr++;
            }
            // Remove expired
            while (!minHeap.isEmpty() && minHeap.peek() < day) {
                minHeap.poll();
            }
            // Attend soonest-ending event
            if (!minHeap.isEmpty()) {
                minHeap.poll();
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(maxEvents(new int[][]{{1,2},{2,3},{3,4}})); // 3
    }
}

Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

SummaryRanges() Initializes the object with an empty stream.
void addNum(int value) Adds the integer value to the stream.
int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [start_i, end_i]. The answer should be sorted by start_i.

Visual Representation

addNum(1):   [1,1]
addNum(3):   [1,1], [3,3]
addNum(7):   [1,1], [3,3], [7,7]
addNum(2):   [1,3], [7,7]      <-- 2 merges [1,1] and [3,3]
addNum(6):   [1,3], [6,7]      <-- 6 merges with [7,7]

Key: When adding N, find and merge with adjacent intervals.
[L, N-1] + N + [N+1, R] => [L, R]

Hard

Examples

Input: ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output: [null, null, [[1,1]], null, [[1,1],[3,3]], null, [[1,1],[3,3],[7,7]], null, [[1,3],[7,7]], null, [[1,3],[6,7]]]

Approach 1

Level I: Brute Force - Rebuild on Every getIntervals

Intuition

Simply store all seen numbers in a sorted list. On every getIntervals() call, rebuild the disjoint intervals from scratch by scanning through the sorted list and merging consecutive numbers.

⏱ O(N log N) for `addNum` (insert into sorted structure), O(N) for `getIntervals`💾 O(N) for storing all numbers

Detailed Dry Run

addNum(1), addNum(3), addNum(7), addNum(2) nums = {1, 2, 3, 7} getIntervals(): sorted = [1, 2, 3, 7] Scan: 1->next is 2 (consecutive), 2->next is 3 (consecutive), 3->next is 7 (gap) Intervals: [1,3], [7,7]

java

import java.util.*;

class SummaryRanges {
    private TreeSet<Integer> set;

    public SummaryRanges() {
        set = new TreeSet<>();
    }
    
    public void addNum(int value) {
        set.add(value);
    }
    
    public int[][] getIntervals() {
        List<int[]> result = new ArrayList<>();
        Integer start = null, end = null;
        
        for (int num : set) {
            if (start == null) {
                start = end = num;
            } else if (num == end + 1) {
                end = num;
            } else {
                result.add(new int[]{start, end});
                start = end = num;
            }
        }
        if (start != null) result.add(new int[]{start, end});
        return result.toArray(new int[0][]);
    }
}

public class Main {
    public static void main(String[] args) {
        SummaryRanges sr = new SummaryRanges();
        sr.addNum(1); sr.addNum(3); sr.addNum(7); sr.addNum(2); sr.addNum(6);
        System.out.println(java.util.Arrays.deepToString(sr.getIntervals())); // [[1,3],[6,7]]
    }
}

Approach 2

Level II: Maintenance of Sorted Intervals

Intuition

Instead of rebuilding the intervals every time, we can maintain a sorted list of disjoint intervals. When adding a new number, we use binary search to find where it would fit among existing intervals, then check if it can be merged with its left or right neighbors. This significantly speeds up getIntervals at the cost of $O(N)$ for addNum due to array shifts.

⏱ O(N) for `addNum` (binary search + possible array insertion/deletion), O(1) for `getIntervals` (if returning the internal list)💾 O(N) for storing the intervals

Detailed Dry Run

addNum(1): [[1,1]] addNum(3): [[1,1], [3,3]] addNum(2): 2 is between [1,1] and [3,3]. Merges both -> [[1,3]] addNum(7): [[1,3], [7,7]]

java

import java.util.*;

class SummaryRanges {
    private List<int[]> intervals;

    public SummaryRanges() {
        intervals = new ArrayList<>();
    }
    
    public void addNum(int value) {
        int n = intervals.size();
        int left = 0, right = n - 1;
        // Binary search for insertion point
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int[] iv = intervals.get(mid);
            if (iv[0] <= value && value <= iv[1]) return;
            if (iv[0] > value) right = mid - 1;
            else left = mid + 1;
        }
        
        int pos = left;
        boolean mergeLeft = pos > 0 && intervals.get(pos - 1)[1] + 1 == value;
        boolean mergeRight = pos < n && intervals.get(pos)[0] - 1 == value;
        
        if (mergeLeft && mergeRight) {
            intervals.get(pos - 1)[1] = intervals.get(pos)[1];
            intervals.remove(pos);
        } else if (mergeLeft) {
            intervals.get(pos - 1)[1] = value;
        } else if (mergeRight) {
            intervals.get(pos)[0] = value;
        } else {
            intervals.add(pos, new int[]{value, value});
        }
    }
    
    public int[][] getIntervals() {
        return intervals.toArray(new int[0][]);
    }
}

Approach 3

Level III: TreeMap / Sorted Map for O(log N) addNum

Intuition

Instead of re-sorting each time, maintain intervals in a sorted map (TreeMap in Java, SortedDict in Python, etc.) keyed by start. When adding a new number val:

Find the interval that might start right after val+1 (right neighbor).
Find the interval whose start <= val (left neighbor), and check if it ends at val-1.
Based on overlapping/adjacency with left and right neighbors, merge intervals accordingly.

This gives O(log N) per addNum and O(N) per getIntervals.

⏱ O(log N) for `addNum`, O(N) for `getIntervals`💾 O(N) for storing the intervals in the sorted map

Detailed Dry Run

addNum(1): map = {1:[1,1]} addNum(3): map = {1:[1,1], 3:[3,3]} addNum(7): map = {1:[1,1], 3:[3,3], 7:[7,7]} addNum(2): val=2. Right neighbor start=3 (3 == 2+1). Left neighbor: key=1, [1,1]. end=1 == 2-1. Merge both: [min(1,2)=1, max(1,3)=3] = [1,3]. Remove key 3. map = {1:[1,3], 7:[7,7]} addNum(6): val=6. Right neighbor start=7 (7 == 6+1). Check left: key=1, [1,3]. end=3 != 5. Only merge with right: [6, 7]. Remove key 7. map = {1:[1,3], 6:[6,7]} getIntervals: [[1,3],[6,7]]

java

import java.util.*;

class SummaryRanges {
    private TreeMap<Integer, Integer> map; // start -> end

    public SummaryRanges() {
        map = new TreeMap<>();
    }
    
    public void addNum(int val) {
        if (map.containsKey(val)) return;

        Integer lo = map.lowerKey(val);   // start of potential left interval
        Integer hi = map.higherKey(val);  // start of potential right interval
        
        boolean mergeLeft = lo != null && map.get(lo) + 1 >= val;  // [lo, lo.end] adjacent or covering
        boolean mergeRight = hi != null && hi == val + 1;           // [val+1, ...] is right adjacent
        
        if (mergeLeft && mergeRight) {
            // Merge val into [lo, hi.end]
            map.put(lo, map.get(hi));
            map.remove(hi);
        } else if (mergeLeft) {
            // Extend left interval
            map.put(lo, Math.max(map.get(lo), val));
        } else if (mergeRight) {
            // Extend right interval leftward
            int end = map.get(hi);
            map.remove(hi);
            map.put(val, end);
        } else {
            map.put(val, val);
        }
    }
    
    public int[][] getIntervals() {
        int[][] result = new int[map.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            result[i][0] = e.getKey();
            result[i][1] = e.getValue();
            i++;
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        SummaryRanges sr = new SummaryRanges();
        for (int n : new int[]{1, 3, 7, 2, 6}) sr.addNum(n);
        System.out.println(java.util.Arrays.deepToString(sr.getIntervals())); // [[1,3],[6,7]]
    }
}

Smallest Range Covering Elements from K Lists

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c, or a < c if b - a == d - c.

Visual Representation

nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

Initial elements from each list: {4, 0, 5}
Range: [0, 5], Size: 5

To find a smaller range, we must increase the minimum (0).
Next element from List 1 (was 0): 9
Set: {4, 9, 5}
Range: [4, 9], Size: 5 (same size, but 4 > 0, so not 'smaller' by definition)

Next element from List 0 (was 4): 10
Set: {10, 9, 5}
Range: [5, 10], Size: 5
...
Eventually we find [20, 24], Size: 4.

Hard

Examples

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Approach 1

Level I: Brute Force - Check All Pairs

Intuition

Pick every possible number from the lists as a potential 'start' and every other number as a potential 'end'. For each range [start, end], check if it contains at least one number from each of the k lists. Keep track of the smallest such range.

⏱ O(N^3) where N is the total number of elements. O(N^2) pairs * O(N) check.💾 O(1) extra space

Detailed Dry Run

nums = [[4,10],[0,9],[5,18]] Pairs: [0,4], [0,5], [0,9], [0,10], [4,5], [4,9]... Range [0,5]: Contains 4(L0), 0(L1), 5(L2). Valid. Size 5. Range [4,9]: Contains 4(L0), 9(L1), 5(L2). Valid. Size 5. ...

java

import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> all = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (int val : nums.get(i)) all.add(new int[]{val, i});
        }
        
        int[] best = { -1000000, 1000000 };
        for (int i = 0; i < all.size(); i++) {
            for (int j = i; j < all.size(); j++) {
                int minVal = Math.min(all.get(i)[0], all.get(j)[0]);
                int maxVal = Math.max(all.get(i)[0], all.get(j)[0]);
                
                if (isValid(nums, minVal, maxVal)) {
                    if (maxVal - minVal < best[1] - best[0]) {
                        best[0] = minVal; best[1] = maxVal;
                    }
                }
            }
        }
        return best;
    }
    
    private boolean isValid(List<List<Integer>> nums, int start, int end) {
        for (List<Integer> list : nums) {
            boolean found = false;
            for (int val : list) {
                if (val >= start && val <= end) {
                    found = true; break;
                }
            }
            if (!found) return false;
        }
        return true;
    }
}

Approach 2

Level II: Sliding Window on All Elements

Intuition

Merge all numbers into a single sorted list, keeping track of which list each number came from. Now the problem becomes: find the shortest subarray in this merged list that contains at least one number from every original list. This is a classic sliding window problem (similar to 'Smallest Window Containing All Characters').

⏱ O(N log N) to sort the merged list, and O(N) for the sliding window.💾 O(N) to store the merged list.

Detailed Dry Run

nums = [[4,10],[0,9],[5,18]] Merged: [(0,L1), (4,L0), (5,L2), (9,L1), (10,L0), (18,L2)] Window [0, 5]: L1, L0, L2 present. Size 5-0=5. Window [4, 9]: L0, L2, L1 present. Size 9-4=5. Window [5, 10]: L2, L1, L0 present. Size 10-5=5. Window [9, 18]: L1, L0, L2 present. Size 18-9=9.

java

import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> all = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (int val : nums.get(i)) all.add(new int[]{val, i});
        }
        all.sort((a,b) -> a[0] - b[0]);
        
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, k = nums.size();
        int[] res = {-1000000, 1000000};
        
        for (int right = 0; right < all.size(); right++) {
            int listIdx = all.get(right)[1];
            count.put(listIdx, count.getOrDefault(listIdx, 0) + 1);
            
            while (count.size() == k) {
                int curRange = all.get(right)[0] - all.get(left)[0];
                if (curRange < res[1] - res[0]) {
                    res[0] = all.get(left)[0]; res[1] = all.get(right)[0];
                }
                int lIdx = all.get(left)[1];
                count.put(lIdx, count.get(lIdx) - 1);
                if (count.get(lIdx) == 0) count.remove(lIdx);
                left++;
            }
        }
        return res;
    }
}

Approach 3

Level III: K-Way Min-Heap Search (Optimal)

Intuition

To find the smallest range, we need to track one element from each list. We maintain these k elements in a Min-Heap. The current range is defined by [min_in_heap, max_in_heap]. To try and find a smaller range, we must increase the minimum element by popping it and replacing it with the next element from that same list. As we go, we keep track of the maximum value currently in our set to update the range.

⏱ O(N log K) where N is the total number of elements and K is the number of lists.💾 O(K) for the Min-Heap.

Detailed Dry Run

nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] Heap = [(0,L1,idx0), (4,L0,idx0), (5,L2,idx0)]. MaxVal = 5. Range = [0, 5], Size 5.

Pop 0. Next L1 is 9. Heap=[(4,0,0), (5,2,0), (9,1,1)]. MaxVal = 9. Range=[4,9], Size 5.
Pop 4. Next L0 is 10. Heap=[(5,2,0), (9,1,1), (10,0,1)]. MaxVal = 10. Range=[5,10], Size 5.
Pop 5. Next L2 is 18. Heap=[(9,1,1), (10,0,1), (18,2,1)]. MaxVal = 18. Range=[9,18], Size 9. ... Eventually we hit [20, 24].

java

import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // {value, row, col}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int maxVal = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i).get(0);
            minHeap.offer(new int[]{val, i, 0});
            maxVal = Math.max(maxVal, val);
        }
        
        int[] res = { -1000000, 1000000 };
        while (minHeap.size() == nums.size()) {
            int[] curr = minHeap.poll();
            int minVal = curr[0], row = curr[1], col = curr[2];
            
            if (maxVal - minVal < res[1] - res[0]) {
                res[0] = minVal; res[1] = maxVal;
            }
            
            if (col + 1 < nums.get(row).size()) {
                int nextVal = nums.get(row).get(col + 1);
                minHeap.offer(new int[]{nextVal, row, col + 1});
                maxVal = Math.max(maxVal, nextVal);
            }
        }
        return res;
    }
}

Kth Smallest Prime Fraction

You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.

For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].

Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] = arr[i] and answer[1] = arr[j].

Visual Representation

arr = [1, 2, 3, 5], k = 3

All fractions: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
Sorted: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3
3rd smallest: 2/5

Heap strategy: Start with 1/5, 1/3, 1/2.
Pop smallest (1/5), push next numerator: 2/5.
Pop smallest (1/3), push next: 2/3.
Pop smallest (2/5). This is the 3rd pop -> Result [2, 5].

Medium

Examples

Input: arr = [1, 2, 3, 5], k = 3
Output: [2,5]

Input: arr = [1, 7], k = 1
Output: [1,7]

Approach 1

Level I: Brute Force - Generate and Sort

Intuition

Generate all possible fractions arr[i] / arr[j] where i < j. Store them in a list, sort the list by fraction value, and return the kth element. Simple but slow for large arrays.

⏱ O(N^2 log N) where N is the length of the array. We generate N^2 fractions and sort them.💾 O(N^2) to store all fractions

Detailed Dry Run

arr = [1, 2, 3, 5], k = 3 Fractions: 1/2, 1/3, 1/5, 2/3, 2/5, 3/5 Values: 0.5, 0.33, 0.2, 0.66, 0.4, 0.6 Sorted values: 0.2(1/5), 0.33(1/3), 0.4(2/5), 0.5(1/2), 0.6(3/5), 0.66(2/3) 3rd smallest: [2, 5].

java

import java.util.*;

public class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        List<int[]> fractions = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                fractions.add(new int[]{arr[i], arr[j]});
            }
        }
        
        Collections.sort(fractions, (a, b) -> Double.compare((double)a[0]/a[1], (double)b[0]/b[1]));
        return fractions.get(k - 1);
    }
}

Approach 2

Level II: Binary Search on Value Range

Intuition

The value of any fraction is between 0 and 1. We can binary search for a value X such that there are exactly k fractions smaller than or equal to X. For a given X, we can count how many fractions satisfy arr[i] / arr[j] <= X (or arr[i] <= X * arr[j]) in $O(N)$ time using two pointers.

⏱ O(N log(1/ε)) where ε is the precision. Each count step is O(N).💾 O(1) extra space

Detailed Dry Run

arr = [1, 2, 3, 5], k = 3 Low=0, High=1, Mid=0.5. Count <= 0.5: 1/2, 1/3, 1/5, 2/5 (4 fractions). Count=4 > 3, High=0.5. Mid=0.25. Count <= 0.25: 1/5 (1 fraction). Count=1 < 3, Low=0.25. Converges to a value where count=3 and max fraction seen is 2/5.

java

public class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        double low = 0, high = 1.0;
        int[] res = new int[2];
        
        while (high - low > 1e-9) {
            double mid = (low + high) / 2;
            int count = 0;
            double maxF = 0.0;
            int p = 0, q = 0;
            
            for (int i = 0, j = 1; i < arr.length - 1; i++) {
                while (j < arr.length && arr[i] > mid * arr[j]) j++;
                count += arr.length - j;
                if (j < arr.length && (double)arr[i] / arr[j] > maxF) {
                    maxF = (double)arr[i] / arr[j];
                    p = arr[i]; q = arr[j];
                }
            }
            
            if (count == k) return new int[]{p, q};
            if (count > k) high = mid;
            else low = mid;
        }
        return res;
    }
}

Approach 3

Level III: Min-Heap (Sorted Pointers)

Intuition

This problem is similar to 'Merging K Sorted Lists'. For each denominator arr[j], the possible numerators arr[0], arr[1], ..., arr[j-1] create a sorted sequence of fractions. We can use a Min-Heap to store the smallest fraction for each possible denominator arr[j]. We pop the overall smallest and replace it with the next numerator from that same denominator's list.

⏱ O((K + N) log N) where N is the length of arr. We start with N elements in the heap and pop K times.💾 O(N) for the Min-Heap.

Detailed Dry Run

arr = [1, 2, 3, 5], k = 3 Initial Heap: {1/5, 1/3, 1/2}

Pop 1/5. Next num for denom 5 is 2. Heap: {1/3, 1/2, 2/5}. Pop count = 1.
Pop 1/3. Next num for denom 3 is 2. Heap: {1/2, 2/5, 2/3}. Pop count = 2.
Pop 2/5. Pop count = 3. Done. Result [2, 5].

java

import java.util.*;

public class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        // {numeratorIdx, denominatorIdx}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> Double.compare((double)arr[a[0]]/arr[a[1]], (double)arr[b[0]]/arr[b[1]])
        );
        
        for (int j = 1; j < arr.length; j++) {
            minHeap.offer(new int[]{0, j});
        }
        
        for (int i = 0; i < k - 1; i++) {
            int[] curr = minHeap.poll();
            if (curr[0] + 1 < curr[1]) {
                minHeap.offer(new int[]{curr[0] + 1, curr[1]});
            }
        }
        
        int[] result = minHeap.poll();
        return new int[]{arr[result[0]], arr[result[1]]};
    }
}

← Previous TopicTrees

Next Topic →Stack

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.