👉 When Amazon asks for problems involving running medians, balancing data, or minimizing differences,
the Two Heaps Pattern is the go-to approach.
🎯 Core Idea
- Maintain two heaps:
- Max-Heap → stores the smaller half of numbers.
-
Min-Heap → stores the larger half of numbers.
- Balancing ensures:
- Max-Heap size ≥ Min-Heap size
- Difference in size ≤ 1
⚡ This allows quick median or balancing decisions in O(log n).
📝 Problem 1: Find Median from Data Stream
👉 Amazon-style phrasing:
Design a data structure that supports adding numbers and finding the running median.
✅ Java Solution
import java.util.*;
public class MedianFinder {
private PriorityQueue<Integer> maxHeap; // lower half
private PriorityQueue<Integer> minHeap; // higher half
public MedianFinder() {
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
// Balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.offer(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
return maxHeap.peek();
}
}
⚡ Time Complexity: O(log n) for add, O(1) for median.
⚡ Amazon Insight: Extremely frequent — tests streaming + heap balancing.
📝 Problem 2: Sliding Window Median
👉 Amazon-style phrasing:
Given an array and window size k, return the median of each window.
✅ Java Solution
import java.util.*;
public class SlidingWindowMedian {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
public double[] medianSlidingWindow(int[] nums, int k) {
double[] result = new double[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
addNum(nums[i]);
if (i >= k) {
removeNum(nums[i - k]);
}
if (i >= k - 1) {
result[i - k + 1] = findMedian();
}
}
return result;
}
private void addNum(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) maxHeap.offer(num);
else minHeap.offer(num);
balance();
}
private void removeNum(int num) {
if (num <= maxHeap.peek()) maxHeap.remove(num);
else minHeap.remove(num);
balance();
}
private void balance() {
if (maxHeap.size() > minHeap.size() + 1) minHeap.offer(maxHeap.poll());
else if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll());
}
private double findMedian() {
if (maxHeap.size() == minHeap.size())
return ((double) maxHeap.peek() + minHeap.peek()) / 2.0;
return maxHeap.peek();
}
}
⚡ Time Complexity: O(n log k) (due to heap remove cost).
⚡ Amazon Insight: Asked in medium/hard rounds to test heap + sliding window handling.
📝 Problem 3: IPO – Maximize Capital (Amazon Favorite)
👉 Amazon-style phrasing:
You’re given k projects with profits and capital requirements. Start with w capital, and at most k projects can be done.
Return max capital you can achieve.
✅ Java Solution
import java.util.*;
public class IPO {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
PriorityQueue<int[]> minCapital = new PriorityQueue<>((a, b) -> a[0] - b[0]);
PriorityQueue<Integer> maxProfit = new PriorityQueue<>((a, b) -> b - a);
for (int i = 0; i < profits.length; i++) {
minCapital.offer(new int[]{capital[i], profits[i]});
}
for (int i = 0; i < k; i++) {
while (!minCapital.isEmpty() && minCapital.peek()[0] <= w) {
maxProfit.offer(minCapital.poll()[1]);
}
if (maxProfit.isEmpty()) break;
w += maxProfit.poll();
}
return w;
}
}
⚡ Time Complexity: O(n log n)
⚡ Amazon Insight: They love this because it tests greedy + two heaps combo.
📝 Problem 4: Smallest Range Covering K Lists
👉 Amazon-style phrasing:
You are given k sorted lists, find the smallest range that includes at least one number from each list.
✅ Java Solution
import java.util.*;
public class SmallestRange {
static class Node {
int val, row, col;
Node(int v, int r, int c) { val = v; row = r; col = c; }
}
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
int maxVal = Integer.MIN_VALUE;
for (int r = 0; r < nums.size(); r++) {
minHeap.offer(new Node(nums.get(r).get(0), r, 0));
maxVal = Math.max(maxVal, nums.get(r).get(0));
}
int start = 0, end = Integer.MAX_VALUE;
while (minHeap.size() == nums.size()) {
Node node = minHeap.poll();
if (maxVal - node.val < end - start) {
start = node.val; end = maxVal;
}
if (node.col + 1 < nums.get(node.row).size()) {
int nextVal = nums.get(node.row).get(node.col + 1);
minHeap.offer(new Node(nextVal, node.row, node.col + 1));
maxVal = Math.max(maxVal, nextVal);
}
}
return new int[]{start, end};
}
}
⚡ Time Complexity: O(n log k)
⚡ Amazon Insight: This is a hard problem, but appears in Amazon OA & L4+ interviews.
📚 Extended Amazon Two-Heap Problems
- Meeting Rooms II (min heap for end times)
- Trapping Rain Water II (2D heap-based BFS)
- Connect Ropes to Minimize Cost (Greedy + min heap)
- Reorganize String (max heap for char freq)
- Task Scheduler (heap + cooldown queue)
🎯 Key Takeaways
- Use Max-Heap + Min-Heap to balance data (median, sliding window).
- Use Min-Heap + Max-Heap for greedy project/IPO problems.
- Amazon loves when you explain heap balancing invariants in interviews.
📅 Next in the series (Day 14):
👉 Subsets & Backtracking Pattern – Powerset, Combination Sum, Palindrome Partitioning.
Top comments (0)