Greedy

Master this topic with zero to advance depth.

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Visual Representation

Index: 0  1  2  3  4
Value: 2  3  1  1  4

Step 1: At index 0 (val 2). Can jump to 1 or 2.
Step 2: From index 1 (val 3). Can jump to 4 (Goal!).
Total Jumps: 2

Medium

Examples

Input: nums = [2,3,1,1,4]
Output: 2
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Approach 1

Level I: Dynamic Programming (Bottom-Up)

Intuition

Define dp[i] as the minimum jumps to reach the end starting from index i. To find dp[i], we 'look ahead' at all reachable indices j and pick the best one.

Thought Process

dp[i] is the min jumps from index i to n-1.
Base case: dp[n-1] = 0.
Recurrence: dp[i] = 1 + min(dp[j]) for all i < j <= i + nums[i].
Initialize dp with infinity.

Pattern: DAG Shortest Path

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

Detailed Dry Run

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

i	Range	Best Next	dp[i]
4	-	-	0
3	[4]	idx 4 (0)	1
2	[3]	idx 3 (1)	2
1	[2,3,4]	idx 4 (0)	1
0	[1,2]	idx 1 (1)	2

java

public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 10001);
        dp[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j <= Math.min(i + nums[i], n - 1); j++) {
                dp[i] = Math.min(dp[i], 1 + dp[j]);
            }
        }
        return dp[0];
    }
}

Approach 2

Level II: Breadth-First Search (Queue-Based)

Intuition

Each jump can be seen as a 'level' in BFS. Indices reachable in 1 jump are Level 1, indices reachable in 2 jumps are Level 2, etc. Use a queue to traverse until $n-1$ is reached.

Thought Process

Queue stores (index, levels).
Use visited set to avoid cycles/redundancy.
For each popped index, push all unvisited neighbors $i+1 \dots i+nums[i]$ .

Pattern: Level-Order Traversal

⏱ O(N^2) worst case, $O(N)$ with optimization.💾 O(N)

Detailed Dry Run

nums = [2, 3, 1, 1, 4] q: [(0,0)]. Pop (0,0). Push (1,1), (2,1). Vis={0,1,2}. Pop (1,1). Push (3,2), (4,2). Reach end! Return 2.

java

public class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1) return 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        boolean[] vis = new boolean[nums.length];
        vis[0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int j = 1; j <= nums[cur[0]]; j++) {
                int next = cur[0] + j;
                if (next >= nums.length - 1) return cur[1] + 1;
                if (!vis[next]) { vis[next] = true; q.offer(new int[]{next, cur[1] + 1}); }
            }
        }
        return 0;
    }
}

Approach 3

Level III: Optimal Greedy (Window-Based BFS)

Intuition

Maintain a 'window' of reachable indices for the current number of jumps. When we reach the end of the current window, we increment jump count and move to the farthest point reachable from that window.

Thought Process

jumps, curEnd, farthest variables.
Iterate through array (excluding last index).
Update farthest = max(farthest, i + nums[i]).
If i == curEnd, update curEnd = farthest, jumps++.

Pattern: Greedy Reachability

⏱ O(N)💾 O(1)

Detailed Dry Run

[2,3,1,1,4] i=0: f=2. i==curEnd(0). end=2, jumps=1. i=1: f=4. OK. i=2: f=4. i==curEnd(2). end=4, jumps=2. Result: 2.

java

public class Solution {
    public int jump(int[] nums) {
        int jumps = 0, curEnd = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = farthest;
            }
        }
        return jumps;
    }
}

Gas Station

There are n gas stations along a circular route, where the amount of gas at the $i^{th}$ station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the $i^{th}$ station to its next $(i + 1)^{th}$ station.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Circular Logic

If you start at index $i$ , you must be able to visit $i+1, i+2, ..., n-1, 0, 1, ..., i-1$ .

Medium

Examples

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Start at station 3 (index 3). Fill 4 units of gas. Your tank = 4. Cost to next = 1. Remaining = 3. Final tank check covers the loop.

Approach 1

Level I: Brute Force (Simulation)

Intuition

Try starting from every single gas station and simulate the journey. If you can complete the circle without the tank becoming negative, that's your starting station.

Visual Representation

Stations: [S0, S1, S2]

Try S0: S0 -> S1 -> S2 -> S0 (Check tank >= 0 at each step)
Try S1: S1 -> S2 -> S0 -> S1
Try S2: S2 -> S0 -> S1 -> S2

Thought Process

Iterate start from $0$ to $n-1$ .
For each start, initialize tank = 0.
Iterate i from $0$ to $n-1$ to visit all stations using (start + i) % n.
If tank < 0 at any point, stop and try next start.

Pattern: Circular Simulation

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

Detailed Dry Run

gas=[1,2], cost=[2,1] S0: tank=1-2=-1. FAIL. S1: tank=2-1=1. Next: tank=1+(1-2)=0. SUCCESS!

java

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int tank = 0, count = 0, j = i;
            while (count < n) {
                tank += gas[j] - cost[j];
                if (tank < 0) break;
                j = (j + 1) % n; count++;
            }
            if (count == n) return i;
        }
        return -1;
    }
}

Approach 2

Level II: Greedy with Total Sum Check

Intuition

Before attempting a simulation, check if a solution even exists. If $\sum gas < \sum cost$ , it is mathematically impossible to complete the circuit regardless of where you start.

Thought Process

Calculate totalGas and totalCost.
If totalGas < totalCost, return -1.
Otherwise, use the greedy property: if you fail to reach station $B$ starting from $A$ , any station between $A$ and $B$ will also fail to reach $B$ .

Pattern: Pruning / Feasibility Check

⏱ O(N)💾 O(1)

Detailed Dry Run

gas=[1,2,3], cost=[2,2,2]. Total gas=6, cost=6. Possible. Start S0: tank=1-2=-1. FAIL. Reset start to S1. Start S1: tank=2-2=0. OK. Start S2: tank=0+(3-2)=1. OK. Return S1.

java

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sumG = 0, sumC = 0;
        for (int i = 0; i < gas.length; i++) { sumG += gas[i]; sumC += cost[i]; }
        if (sumG < sumC) return -1;
        int start = 0, tank = 0;
        for (int i = 0; i < gas.length; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) { start = i + 1; tank = 0; }
        }
        return start;
    }
}

Approach 3

Level III: Optimal Greedy (One-Pass)

Intuition

We can combine the total sum check into the main loop. Track totalDiff as we go. If totalDiff is negative at the end, return -1. Otherwise, the last valid start candidate is guaranteed to work.

Visual Representation

Indices: [ 0,  1,  2,  3,  4]
Diffs:   [-2, -2, -2,  3,  3]

Loop:
i=0: tank=-2. Fail. start=1, tank=0.
i=1: tank=-2. Fail. start=2, tank=0.
i=2: tank=-2. Fail. start=3, tank=0.
i=3: tank=3.  OK.
i=4: tank=6.  OK.
TotalDiff = 0 >= 0. Result: start index 3.

Thought Process

Use totalTank to keep running sum of all (gas[i] - cost[i]).
Use currentTank to track gas from current start candidate.
If currentTank drops below 0, the current start (and all stations between it and i) is invalid. Reset currentTank and set start = i + 1.
Final answer: totalTank >= 0 ? start : -1.

Pattern: Candidate Elimination

⏱ O(N)💾 O(1)

Detailed Dry Run

gas=[1,2,3,4,5], cost=[3,4,5,1,2]

i	diff	curTank	totalTank	start
0	-2	-2 (Reset)	-2	1
1	-2	-2 (Reset)	-4	2
2	-2	-2 (Reset)	-6	3
3	3	3	-3	3
4	3	6	0	3
totalTank=0. Return 3.

java

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalTank = 0, currentTank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            totalTank += diff;
            currentTank += diff;
            if (currentTank < 0) {
                start = i + 1;
                currentTank = 0;
            }
        }
        return totalTank >= 0 ? start : -1;
    }
}

Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Return a list of integers representing the size of these parts.

Visual Representation

s = "ababcbacadefegdehijhklij"

Letter 'a' appears at indices [0, 2, 6, 8]
If we take 'a', we MUST take everything up to index 8.
Inside [0, 8], we have 'b' (ends at 5), 'c' (ends at 7).
Max end index for characters in [0, 8] is index 8.
Partition 1: "ababcbaca" (Size 9)

Medium

Examples

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
The partition is "ababcbaca", "defegde", "hijhklij".

Approach 1

Level I: Dynamic Search

Intuition

For every partition starting at i, we find the last occurrence of s[i]. This is our initial end. Then, for every character between i and end, we update end if that character's last occurrence is even further.

Thought Process

Iterate i from 0 to $N-1$ .
Start a new partition: start = i, end = lastOccurrence(s[i]).
Loop j from i to end:
- end = max(end, lastOccurrence(s[j])).
When j reaches end, the partition is complete. Add end - start + 1 to result.
Move i to end + 1.

Pattern: Window Expansion

⏱ O(N^2) - If we call `lastIndexOf` inside the loop for each character.💾 O(1) - Just pointers.

Detailed Dry Run

s = "abaccb"

i=0 ('a'), end=2 ('a' at index 2). Partition: [0, 2]
Check inner: j=1 ('b'), last 'b' is 5. Update end=5.
Check inner: j=3 ('c'), last 'c' is 4. end stays 5.
j reaches 5. Partition size = 5-0+1 = 6.

java

import java.util.*;

public class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        int i = 0, n = s.length();
        while (i < n) {
            int start = i;
            int end = s.lastIndexOf(s.charAt(i));
            for (int j = start; j < end; j++) {
                end = Math.max(end, s.lastIndexOf(s.charAt(j)));
            }
            res.add(end - start + 1);
            i = end + 1;
        }
        return res;
    }
}

Approach 2

Level II: Merge Intervals

Intuition

Treat each character as an interval from its first occurrence to its last occurrence. Any overlapping intervals MUST be merged into a single partition. This reduces the problem to a standard interval merging task.

Thought Process

Find first and last occurrence for each character 'a'-'z'.
Create a list of intervals [first, last] for characters that appear in the string.
Sort intervals by start time.
Merge overlapping intervals.
The size of each merged interval is a partition length.

Pattern: Interval Merging

⏱ O(N + A log A) where A is alphabet size (26). Effectively O(N).💾 O(A) - Storage for 26 intervals.

Detailed Dry Run

s = "abaccb" Intervals: a[0,2], b[1,5], c[3,4]

Sorted: [0,2], [1,5], [3,4]
Merge [0,2] and [1,5] -> [0,5] (overlaps)
Merge [0,5] and [3,4] -> [0,5] (overlaps) Result: [6]

java

import java.util.*;

public class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] intervals = new int[26][2];
        for(int[] sub : intervals) Arrays.fill(sub, -1);
        for(int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if(intervals[c][0] == -1) intervals[c][0] = i;
            intervals[c][1] = i;
        }
        List<int[]> list = new ArrayList<>();
        for(int[] interval : intervals) if(interval[0] != -1) list.add(interval);
        list.sort((a, b) -> a[0] - b[0]);
        List<Integer> res = new ArrayList<>();
        if(list.isEmpty()) return res;
        int start = list.get(0)[0], end = list.get(0)[1];
        for(int i = 1; i < list.size(); i++) {
            if(list.get(i)[0] <= end) end = Math.max(end, list.get(i)[1]);
            else {
                res.add(end - start + 1);
                start = list.get(i)[0]; end = list.get(i)[1];
            }
        }
        res.add(end - start + 1);
        return res;
    }
}

Approach 3

Level III: Optimal Greedy (One-Pass)

Intuition

As we scan the string, we keep track of the maximum last index seen so far for characters in the current partition. When our current index i catches up to this last index, we've found a valid partition.

Thought Process

Store the lastIndex for every character in a map/array.
Maintain start and end pointers.
Iterate i from 0 to $N-1$ $N - 1$ :
- end = max(end, lastIndex[s[i]]).
- If i == end:
  - Found partition! Size = i - start + 1.
  - Update start = i + 1.

Pattern: Greedy Boundary Tracking

⏱ O(N) - One pass to build the map, one pass to partition.💾 O(1) - Map size is constant (26 characters).

Detailed Dry Run

s = "ababcbaca..."

i	char	lastIndex[char]	end	Action
0	a	8	8	-
1	b	5	8	-
...	...	...	8	-
8	a	8	8	i == end! Size = 8-0+1 = 9. start = 9.

java

import java.util.*;

public class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
        
        List<Integer> res = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}

Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. There is no limit to the number of arrows that can be shot.

Return the minimum number of arrows that must be shot to burst all balloons.

Visual Representation

Points: [[10,16], [2,8], [1,6], [7,12]]

Sort by end points:
[1, 6], [2, 8], [7, 12], [10, 16]

Arrow 1: Shoot at x=6. Bursts [1,6] and [2,8].
Arrow 2: Shoot at x=12. Bursts [7,12] and [10,16].
Total: 2 arrows.

Medium

Examples

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
One arrow at 6 bursts [1,6] and [2,8]. Another arrow at 12 bursts [7,12] and [10,16].

Approach 1

Level I: Greedy Simulation (Brute Force)

Intuition

If we don't know the optimal sorting trick, a natural brute-force thought is: 'Let's find the coordinate that bursts the maximum number of balloons right now, shoot an arrow there, remove the burst balloons, and repeat until no balloons are left.' The candidate coordinates to shoot at are simply the start and end points of the remaining balloons.

Thought Process

Maintain a list of remaining balloons.
While the list is not empty, iterate through all start and end points of the remaining balloons.
For each point, count how many balloons it intersects. Find the point that yields the maximum count.
Increment arrows, filter out the burst balloons, and repeat.

⏱ O(N^3)💾 O(N)

Detailed Dry Run

points = [[1,6],[2,8],[7,12]]

Points: 1,6,2,8,7,12. Count 6: bursts [1,6],[2,8] (2).
Max burst is 2 at x=6. arrows=1. Remaining: [[7,12]]
Repeat for [[7,12]]: best point 12. arrows=2. Empty.

java

import java.util.*;

public class Main {
    public static int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        List<int[]> remaining = new ArrayList<>(Arrays.asList(points));
        int arrows = 0;
        
        while (!remaining.isEmpty()) {
            long bestPoint = 0;
            int maxBurst = 0;
            
            for (int[] p : remaining) {
                long[] candidates = {p[0], p[1]};
                for (long cand : candidates) {
                    int count = 0;
                    for (int[] b : remaining) {
                        if (cand >= b[0] && cand <= b[1]) count++;
                    }
                    if (count > maxBurst) {
                        maxBurst = count;
                        bestPoint = cand;
                    }
                }
            }
            
            arrows++;
            List<int[]> nextRound = new ArrayList<>();
            for (int[] b : remaining) {
                if (bestPoint < b[0] || bestPoint > b[1]) {
                    nextRound.add(b);
                }
            }
            remaining = nextRound;
        }
        return arrows;
    }
}

Approach 2

Level II: Greedy (Sort by Start & Find Overlap)

Intuition

If we sort by start point, we can maintain a 'current intersection' range. Every new balloon must overlap with this intersection. If it doesn't, we shoot an arrow and start a new intersection range.

Thought Process

Sort by start point.
Pick the first balloon as the initial intersection [currentStart, currentEnd].
For each subsequent balloon [bStart, bEnd]:
- If bStart <= currentEnd (they overlap):
  - Narrow the intersection: currentEnd = min(currentEnd, bEnd).
- Else (no overlap with current intersection):
  - Shoot an arrow!
  - Update currentEnd = bEnd and increment arrows.

Pattern: Intersection Tracking

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

Detailed Dry Run

pointsSorted = [[1,6],[2,8],[7,12]]

p[0]=[1,6]. currEnd=6, arrows=1.
p[1]=[2,8]. 2 <= 6 (overlap). currEnd = min(6, 8) = 6.
p[2]=[7,12]. 7 > 6 (no overlap). arrows=2, currEnd=12.

java

import java.util.Arrays;

public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        
        int arrows = 1;
        int currentEnd = points[0][1];
        
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= currentEnd) {
                currentEnd = Math.min(currentEnd, points[i][1]);
            } else {
                arrows++;
                currentEnd = points[i][1];
            }
        }
        return arrows;
    }
}

Approach 3

Level III: Optimal Greedy (Sort by End)

Intuition

To minimize arrows, we want each arrow to burst as many balloons as possible. By sorting by the end point, we fix the rightmost boundary for an arrow. If a balloon's start point is within the current arrow's range (i.e., start <= current_arrow_pos), it is burst. Otherwise, we need a new arrow at the new balloon's end point.

Why Sort by End?

Sorting by the end point ensures that the current balloon we are considering is the one that 'expires' soonest. Putting an arrow at its end point is the best greedy choice because it covers this balloon AND has the maximum chance of covering future balloons that start before this end point.

Pattern: Interval Overlap

⏱ O(N log N) due to sorting.💾 O(log N) or O(N) depending on the sorting implementation's recursion stack.

Detailed Dry Run

points = [[10,16], [2,8], [1,6], [7,12]] After Sort: [[1,6], [2,8], [7,12], [10,16]]

Step	Balloon	Range	lastArrowAt	arrows	Action
1	[1, 6]	[1, 6]	6	1	Shoot at 6 (end of first)
2	[2, 8]	[2, 8]	6	1	2 <= 6? YES (Burst!)
3	[7, 12]	[7, 12]	12	2	7 > 6? YES. Shoot at 12 (end)
4	[10, 16]	[10, 16]	12	2	10 <= 12? YES (Burst!)

Visualization:

(1)-------(6)                <- Arrow 1 at 6
   (2)-----------(8)
              (7)-------(12) <- Arrow 2 at 12
                   (10)--------(16)

java

import java.util.Arrays;

public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        
        // Sort by end points to greedily pick the best shooting position
        // Using Integer.compare to avoid overflow during subtraction
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1;
        int currentEnd = points[0][1];

        for (int i = 1; i < points.length; i++) {
            // If current balloon starts AFTER our last arrow,
            // we MUST shoot a new arrow.
            if (points[i][0] > currentEnd) {
                arrows++;
                currentEnd = points[i][1];
            }
        }
        return arrows;
    }
}

Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Visual Representation

Intervals: [[1,2], [2,3], [3,4], [1,3]]

1--2
   2--3
      3--4
1-----3

To keep most intervals (3), we must remove [1,3].
Result: 1

Medium

Examples

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
[1,3] can be removed and the rest of intervals are non-overlapping.

Approach 1

Level I: Recursive Selection (Brute Force)

Intuition

The problem asks for the minimum removals to remove all overlaps. This is equivalent to finding the maximum number of non-overlapping intervals. We can generate all combinations of intervals (take it or leave it) and find the maximum valid set.

Thought Process

Sort the intervals by start time so we can easily check for overlaps sequentially.
For each interval at currIndex, we have two choices:
- Include it: Only possible if it doesn't overlap with the last included interval prevIndex (i.e., intervals[prevIndex].end <= intervals[currIndex].start). We add 1 to our count and move to currIndex + 1.
- Exclude it: We move to currIndex + 1 without adding to our count.
Return the maximum of these two choices for all steps.

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

Detailed Dry Run

intervalsSorted = [[1,2], [1,3], [2,3]]

solve(-1, 0):
- Take [1,2]: 1 + solve(0, 1) -> 1 + 1 (takes [2,3]) = 2
- Leave [1,2]: solve(-1, 1) -> max(take[1,3], leave[1,3]) = 1 Max kept = 2. Removals = 3 - 2 = 1.

java

import java.util.Arrays;

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        return intervals.length - solve(intervals, -1, 0);
    }
    
    private int solve(int[][] intervals, int prevIndex, int currIndex) {
        if (currIndex == intervals.length) return 0;
        
        int taken = 0;
        if (prevIndex == -1 || intervals[prevIndex][1] <= intervals[currIndex][0]) {
            taken = 1 + solve(intervals, currIndex, currIndex + 1);
        }
        int notTaken = solve(intervals, prevIndex, currIndex + 1);
        
        return Math.max(taken, notTaken);
    }
}

Approach 2

Level II: Dynamic Programming (LIS Variation)

Intuition

This problem is equivalent to finding the Longest Chain of Pairs or the Longest Increasing Subsequence. We want to find the maximum number of intervals k that can be kept. Then the result is N - k.

Thought Process

Sort the intervals by start time.
Create a dp array where dp[i] is the maximum number of non-overlapping intervals ending at index i.
For each i, look at all j < i. If intervals[j].end <= intervals[i].start, then we can extend the chain: dp[i] = max(dp[i], dp[j] + 1).

Pattern: Dynamic Programming / LIS

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

Detailed Dry Run

intervalsSorted = [[1,2], [1,3], [2,3]], dp=[1,1,1]

i=1 [1,3]: j=0 [1,2] overlaps. dp[1]=1.
i=2 [2,3]: j=0 [1,2] no overlap. dp[2]=max(1, dp[0]+1)=2.
i=2 [2,3]: j=1 [1,3] overlaps. dp[2]=2. Max kept = 2. Removals = 3 - 2 = 1.

java

import java.util.Arrays;

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        int n = intervals.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        int maxKept = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxKept = Math.max(maxKept, dp[i]);
        }
        return n - maxKept;
    }
}

Approach 3

Level III: Optimal Greedy (Sort by End)

Intuition

To keep the maximum number of intervals, we should always pick the interval that ends the earliest. This is the classic Interval Scheduling problem. Why? Because an earlier end time leaves the most possible room for subsequent intervals.

Thought Process

Sort by end point.
Keep track of the lastEnd time of the last accepted interval.
For each interval:
- If start >= lastEnd, accept it and update lastEnd.
- Else, it overlaps; increment removals count.

Pattern: Interval Scheduling

⏱ O(N log N) for sorting.💾 O(log N) or O(N) for sorting stack.

Detailed Dry Run

intervals = [[1,2], [2,3], [3,4], [1,3]] After Sort: [[1,2], [2,3], [1,3], [3,4]]

Step	Interval	Range	lastEnd	Action
1	[1, 2]	[1, 2]	2	Keep [1,2]. lastEnd = 2
2	[2, 3]	[2, 3]	3	2 >= 2? YES. Keep [2,3]. lastEnd = 3
3	[1, 3]	[1, 3]	3	1 < 3? NO. Remove [1,3].
4	[3, 4]	[3, 4]	4	3 >= 3? YES. Keep [3,4]. lastEnd = 4

Result: 1 removal.

java

import java.util.Arrays;

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        
        // Sort by end points to maximize room for future intervals
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 1; // Count of non-overlapping intervals kept
        int lastEnd = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= lastEnd) {
                count++;
                lastEnd = intervals[i][1];
            }
        }
        return intervals.length - count;
    }
}

Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [h_i, k_i] represents the i-th person of height h_i who has exactly k_i other people in front of them with a height greater than or equal to h_i.

Reconstruct and return the queue that is represented by the input array people.

Visual Representation

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Step 1: Sort by height DESC, then k index ASC.
[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

Step 2: Insert into list at index k.
Insert [7,0] at 0: [[7,0]]
Insert [7,1] at 1: [[7,0], [7,1]]
Insert [6,1] at 1: [[7,0], [6,1], [7,1]]
Insert [5,0] at 0: [[5,0], [7,0], [6,1], [7,1]]
...

Medium

Examples

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Result matches the height/k-index constraints.

Approach 1

Level I: Brute Force Simulation (Find Empty Slots)

Intuition

If we sort people by height ascending, we can process each person and find their relative position by counting 'empty slots' in the final array. Each empty slot is reserved for someone taller (or same height) than the current person.

Thought Process

Sort by height ASC, then $k$ DESC for same height.
Create an empty result array of size $N$ .
For each person [h, k]:
- We need $k$ people in front of us who are $\ge h$ .
- Find the $(k+1)$ -th empty slot in the result array and place the person there.

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

Detailed Dry Run

people = [[7,0], [4,4], [7,1], [5,0], [5,2], [6,1]] Sorted (H asc, K desc): [[4,4], [5,2], [5,0], [6,1], [7,1], [7,0]]

[4,4]: Put in 5th empty slot (idx 4). res=[_ _ _ _ [4,4] _]
[5,2]: Put in 3rd empty slot (idx 2). res=[_ _ [5,2] _ [4,4] _]
[5,0]: Put in 1st empty slot (idx 0). res=[[5,0] _ [5,2] _ [4,4] _]
[6,1]: Put in 2nd empty slot (idx 3). res=[[5,0] _ [5,2] [6,1] [4,4] _]

java

import java.util.Arrays;

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int n = people.length;
        int[][] res = new int[n][2];
        for (int[] r : res) Arrays.fill(r, -1);

        for (int[] p : people) {
            int count = p[1];
            for (int i = 0; i < n; i++) {
                if (res[i][0] == -1) { // Empty slot
                    if (count == 0) {
                        res[i] = p;
                        break;
                    }
                    count--;
                }
            }
        }
        return res;
    }
}

Approach 2

Level II: Optimal Greedy (Sort and Insert)

Intuition

Taller people don't care about shorter people behind them. If we process taller people first, their relative k index in the final queue will be exactly equal to their index in the list.

Thought Process

Sort DESC by height, then ASC by k.
Insert each person into a dynamic list at index k.
Shorter people inserted later won't change the count of taller people in front of existing elements.

Pattern: Greedy Insertion

⏱ O(N^2) - List insertion takes $O(N)$.💾 O(N) for the list.

Detailed Dry Run

people = [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

Step	Person	Action	Queue
1	[7,0]	Insert at 0	[[7,0]]
2	[7,1]	Insert at 1	[[7,0], [7,1]]
3	[6,1]	Insert at 1	[[7,0], [6,1], [7,1]]
4	[5,0]	Insert at 0	[[5,0], [7,0], [6,1], [7,1]]
5	[5,2]	Insert at 2	[[5,0], [7,0], [5,2], [6,1], [7,1]]
6	[4,4]	Insert at 4	[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

java

import java.util.*;

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> list = new LinkedList<>();
        for (int[] p : people) list.add(p[1], p);
        return list.toArray(new int[people.length][2]);
    }
}

Approach 3

Level III: Logarithmic Optimal (Binary Indexed Tree)

Intuition

Finding the $(k+1)$ -th empty slot in $O(N)$ is the bottleneck in the simulation. We can speed this up to $O(\log N)$ using a Binary Indexed Tree (BIT) or Segment Tree by tracking the number of available slots.

Thought Process

Use the height ASC sort from Level I.
Imagine an array where 1 means 'empty' and 0 means 'filled'.
We want a position $idx$ where $prefixSum(idx) = k+1$ .
We can find this using Binary Search over the BIT in $O(\log^2 N)$ or walking the Segment Tree in $O(\log N)$ .

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

Detailed Dry Run

Sorted: [[4,4], [5,2], [5,0], [6,1], [7,1], [7,0]] BIT tracks empty slots (initially all 1s).

[4,4]: Find k=4. BIT query/search gives pos 5. res[4]=[4,4]. BIT update(5, -1).
[5,2]: Find k=2. BIT query search gives pos 3. res[2]=[5,2]. BIT update(3, -1).

java

import java.util.*;

public class Solution {
    int[] bit;
    public int[][] reconstructQueue(int[][] people) {
        int n = people.length;
        bit = new int[n + 1];
        for (int i = 1; i <= n; i++) update(i, 1, n);
        
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        
        int[][] res = new int[n][2];
        for (int[] p : people) {
            int target = p[1] + 1;
            int l = 1, r = n, pos = n;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(mid) >= target) {
                    pos = mid;
                    r = mid - 1;
                } else l = mid + 1;
            }
            res[pos - 1] = p;
            update(pos, -1, n);
        }
        return res;
    }
    private void update(int i, int v, int n) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    private int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
}

Task Scheduler

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. For each unit of time, the CPU could complete either one task or stay idle.

There is a cooldown period n between two same tasks, meaning at least n units of time must pass between any two executions of the same task.

Return the least number of units of time to finish all tasks.

Visual Representation

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

Timeline:
A -> B -> idle -> A -> B -> idle -> A -> B
1    2    3       4    5    6       7    8

Total Time: 8

Medium

Examples

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
A possible sequence: A -> B -> idle -> A -> B -> idle -> A -> B.

Approach 1

Level I: Simple Simulation

Intuition

At each unit of time, we want to pick the most frequent task that is currently available (not in cooldown). We can simulate this step-by-step.

Thought Process

Count frequencies of all tasks.
Maintain an array nextAvailableTime for each task.
At each time t, pick the available task with the highest remaining frequency.
If no task is available, stay idle and increment time.

⏱ O(TotalTime * 26)💾 O(1)

Detailed Dry Run

tasks=[A,A,B], n=2 t=0: best=A (count 2). nextAvail[A]=3, rem=2. t=1: best=B (count 1). nextAvail[B]=4, rem=1. t=2: no one avail (A needs t=3). idle. t=3: best=A (count 1). nextAvail[A]=6, rem=0. Total: 4 units.

java

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] counts = new int[26];
        for (char t : tasks) counts[t - 'A']++;
        int[] nextAvailable = new int[26];
        int remaining = tasks.length, time = 0;
        while (remaining > 0) {
            int best = -1;
            for (int i = 0; i < 26; i++) {
                if (counts[i] > 0 && nextAvailable[i] <= time) {
                    if (best == -1 || counts[i] > counts[best]) best = i;
                }
            }
            if (best != -1) {
                counts[best]--;
                nextAvailable[best] = time + n + 1;
                remaining--;
            }
            time++;
        }
        return time;
    }
}

Approach 2

Level II: Greedy with Max-Heap

Intuition

Instead of scanning all tasks every time, we use a Max-Heap to always pick the highest frequency task. Tasks in cooldown are stored in a temporary wait-queue and added back to the heap once their cooldown expires.

Thought Process

Push all task frequencies into a Max-Heap.
Use a Queue to store {remaining_freq, release_time} for tasks in cooldown.
At each unit of time:
- Check the Queue: If a task's release_time <= current_time, push it back to the Heap.
- Pop the highest frequency task from the Heap, decrement its frequency, and if it's still > 0, add it to the wait-queue with release_time = current_time + n + 1.

Pattern: Priority Queue Simulation

⏱ O(N log 26)💾 O(1) - Heap and Queue size are capped at 26.

Detailed Dry Run

tasks=[A,A,A,B,B,B], n=2 Heap: [(A,3), (B,3)] t=0: Pop (A,3). Add to waitQueue: (A,2) at t=3. time=1. t=1: Pop (B,3). Add to waitQueue: (B,2) at t=4. time=2. t=2: Heap empty. Wait till t=3... time=3. t=3: WaitQueue release (A,2). Heap: [(A,2)]...

java

import java.util.*;

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] counts = new int[26];
        for (char t : tasks) counts[t - 'A']++;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int c : counts) if (c > 0) maxHeap.add(c);

        Queue<int[]> waitQueue = new LinkedList<>();
        int time = 0;
        while (!maxHeap.isEmpty() || !waitQueue.isEmpty()) {
            time++;
            if (!waitQueue.isEmpty() && waitQueue.peek()[1] == time) {
                maxHeap.add(waitQueue.poll()[0]);
            }
            if (!maxHeap.isEmpty()) {
                int cnt = maxHeap.poll() - 1;
                if (cnt > 0) waitQueue.add(new int[]{cnt, time + n + 1});
            }
        }
        return time;
    }
}

Approach 3

Level III: Optimal Frequency Analysis (Math)

Intuition

The total time is bounded by the most frequent task. If 'A' is the most frequent (frequency $f$ ), we have $f$ blocks. Each of the first $f-1$ blocks must be followed by $n$ slots (either other tasks or idle).

Thought Process

Let max_f be the maximum frequency.
The base structure is (max_f - 1) * (n + 1) slots.
Any other tasks with the same max_f frequency will fill one extra slot at the very end.
Total time = (max_f - 1) * (n + 1) + num_tasks_with_max_f.
If this result is smaller than the total number of tasks, it means no idle slots are needed, so the answer is tasks.length.

Pattern: Math / Frequency Analysis

⏱ O(N) - Single pass to count frequencies.💾 O(1) - Constant space for 26 frequencies.

Detailed Dry Run

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

Variable	Value	Explanation
maxFreq	3	'A' and 'B' both appear 3 times
countMax	2	Two tasks (A, B) have max frequency
Formula	(3-1)*(2+1) + 2	2 * 3 + 2 = 8
Final	max(8, 6)	8

Visualization:

[A, B, _] [A, B, _] [A, B] -> Total 8 slots.

java

import java.util.Arrays;

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freqs = new int[26];
        for (char t : tasks) freqs[t - 'A']++;
        Arrays.sort(freqs);
        
        int maxFreq = freqs[25];
        int countMax = 0;
        for (int f : freqs) if (f == maxFreq) countMax++;

        return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countMax);
    }
}

Minimum Number of Taps to Water Garden

There is a one-dimensional garden from 0 to n. There are n + 1 taps at points [0, 1, ..., n]. Tap i can water the area [i - ranges[i], i + ranges[i]].

Return the minimum number of taps to water the entire garden [0, n]. If impossible, return -1.

Visual Representation

n = 5, ranges = [3, 4, 1, 1, 0, 0]

Tap 0: [0, 3]
Tap 1: [0, 5] <--- Covers everything alone!
Tap 2: [1, 3]
...

Optimal: 1 (Tap 1)

Hard

Examples

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Tap at index 1 covers [0,5], which is the entire garden.

Approach 1

Level I: Brute Force (Recursive Backtracking)

Intuition

Try every subset of taps and check if they together cover the garden [0, n]. This can be implemented using recursion by deciding for each tap whether to include it or not.

Thought Process

solve(tapIdx, currentCoverage)
At each step, either take the current tap or skip it.
Base case: If tapIdx == n + 1, check if currentCoverage >= n.
This approach is extremely slow due to $2^N$ combinations.

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

Detailed Dry Run

n=3, taps=[[0,2], [1,3]]

solve(0, 0): Take [0,2] -> solve(1, 2) -> Take [1,3] -> solve(2, 3) -> SUCCESS (2 taps)
solve(0, 0): Skip [0,2] -> solve(1, 0) -> Take [1,3] -> FAIL (Gap at [0,1])

java

public class Solution {
    int min = 10001;
    public int minTaps(int n, int[] ranges) {
        solve(0, n, ranges, 0, 0);
        return min > 1000 ? -1 : min;
    }
    void solve(int idx, int n, int[] rs, int count, int reach) {
        if (reach >= n) { min = Math.min(min, count); return; }
        if (idx > n) return;
        int l = Math.max(0, idx - rs[idx]), r = Math.min(n, idx + rs[idx]);
        if (l <= reach) solve(idx+1, n, rs, count+1, Math.max(reach, r));
        solve(idx+1, n, rs, count, reach);
    }
}

Approach 2

Level II: Dynamic Programming

Intuition

Define dp[i] as the minimum number of taps needed to water the garden from index $0$ to $i$ . For each tap, we update all indices it covers.

Thought Process

Initialize dp array of size n+1 with a large value (infinity).
dp[0] = 0 (no taps needed to cover index 0).
For each tap i with range [left, right]:
- For every j such that left <= j <= right:
  - dp[right] = min(dp[right], dp[j] + 1).

Pattern: Interval DP / Shortest Path in DAG

⏱ O(N * MaxRange)💾 O(N)

Detailed Dry Run

n=5, ranges=[3,4,1,1,0,0], dp=[0, inf, inf, inf, inf, inf]

Tap 0: [0,3]. dp[1..3] = min(inf, dp[0]+1) = 1. dp=[0, 1, 1, 1, inf, inf]
Tap 1: [0,5]. dp[1..5] = min(cur, dp[0..1]+1) = 1. dp=[0, 1, 1, 1, 1, 1]

java

public class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] dp = new int[n + 1];
        java.util.Arrays.fill(dp, n + 2);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
            int l = Math.max(0, i - ranges[i]);
            int r = Math.min(n, i + ranges[i]);
            for (int j = l; j <= r; j++) {
                dp[r] = Math.min(dp[r], dp[j] + 1);
            }
        }
        return dp[n] > n ? -1 : dp[n];
    }
}

Approach 3

Level III: Optimal Greedy (Jump Game II Variation)

Intuition

This is equivalent to finding the minimum jumps to reach n. We transform each tap into a 'jump' from its left boundary to its right boundary.

Thought Process

Preprocess: For each start point $i$ , find the maximum end point it can reach: maxReach[left] = max(maxReach[left], right).
Now it's Jump Game II: Iterate from $0$ to $n-1$ , keeping track of the current coverage end and the farthest reach possible.

Pattern: Interval Coverage / Jump Game II

⏱ O(N) - One pass for preprocessing, one for greedy.💾 O(N) for maxReach array.

Detailed Dry Run

n=5, ranges=[3,4,1,1,0,0] MaxReach: [5, 0, 3, 0, 4, 5] (Index 0 can reach 5 via Tap 1)

i	farthest	end	taps	Action
0	5	0	1	i == end, taps++, end = 5
1-4	5	5	1	farthest doesn't change
Result: 1

java

public class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] maxReach = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int l = Math.max(0, i - ranges[i]);
            int r = Math.min(n, i + ranges[i]);
            maxReach[l] = Math.max(maxReach[l], r);
        }
        int taps = 0, currEnd = 0, farthest = 0;
        for (int i = 0; i < n; i++) {
            farthest = Math.max(farthest, maxReach[i]);
            if (farthest <= i) return -1; // Gap
            if (i == currEnd) {
                taps++;
                currEnd = farthest;
            }
        }
        return taps;
    }
}

Maximum Length of Pair Chain

You are given an array of n pairs pairs where pairs[i] = [left_i, right_i] and left_i < right_i.

A pair p2 follows p1 if p1[1] < p2[0]. Return the length of the longest chain.

Visual Representation

Pairs: [[1,2], [7,8], [4,5]]

1. Sort by end points: [1,2], [4,5], [7,8]
2. Chain: [1,2] -> [4,5] -> [7,8]
Length: 3

Medium

Examples

Input: pairs = [[1,2], [2,3], [3,4]]
Output: 2
Longest chain: [1,2] -> [3,4]. Note: [2,3] cannot follow [1,2] because 2 is not < 2.

Approach 1

Level I: Brute Force (Recursive Backtracking)

Intuition

Try all possible subsequences of pairs and check if they form a valid chain. To optimize slightly, we can first sort by start time and use recursion with a 'pick or skip' strategy.

Thought Process

solve(idx, prevEnd)
For each pair idx:
- If pairs[idx].start > prevEnd, we can pick it: 1 + solve(idx + 1, pairs[idx].end).
- We can always skip it: solve(idx + 1, prevEnd).
Return the maximum of both.

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

Detailed Dry Run

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

solve(0, -inf): Pick [1,2] -> solve(1, 2) -> Pick [3,4] -> SUCCESS (2 pairs)
solve(0, -inf): Skip [1,2] -> solve(1, -inf) -> Pick [2,3] -> solve(2, 3) -> Pick [3,4] (FAIL: 3 not > 3)

java

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        return solve(0, Integer.MIN_VALUE, pairs);
    }
    private int solve(int idx, int prevEnd, int[][] pairs) {
        if (idx == pairs.length) return 0;
        int taken = 0;
        if (pairs[idx][0] > prevEnd) taken = 1 + solve(idx + 1, pairs[idx][1], pairs);
        int notTaken = solve(idx + 1, prevEnd, pairs);
        return Math.max(taken, notTaken);
    }
}

Approach 2

Level II: Dynamic Programming (LIS Variation)

Intuition

This problem is perfectly analogous to Longest Increasing Subsequence (LIS). We want to find the longest chain where each pair follows the previous one.

Thought Process

Sort the pairs by their start element.
Initialize a dp array where dp[i] is the length of the longest chain ending at index i (initially all 1).
For each i, check all j < i: if pairs[j].end < pairs[i].start, then dp[i] = max(dp[i], dp[j] + 1).

Pattern: Dynamic Programming / LIS

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

Detailed Dry Run

pairs = [[1,2], [2,3], [3,4]], dp=[1, 1, 1]

i=1 ([2,3]): j=0 ([1,2]). 2 is not > 2. dp[1]=1.
i=2 ([3,4]): j=0 ([1,2]). 3 > 2. dp[2]=max(1, dp[0]+1)=2.
i=2 ([3,4]): j=1 ([2,3]). 3 is not > 3. dp[2]=2. Max dp = 2.

java

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int n = pairs.length, max = 0;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

Approach 3

Level III: Optimal Greedy (Interval Scheduling-Style)

Intuition

To fit the maximum number of intervals into a chain, we should always pick the pair that ends the earliest. This leaves the maximum room for subsequent pairs.

Thought Process

Sort pairs by their end element pair[1].
Maintain currEnd of the chain.
For each pair, if its start > currEnd, add it to the chain and update currEnd.

Pattern: Interval Selection / Activity Selection

⏱ O(N log N) for sorting.💾 O(1) excluding sort space.

Detailed Dry Run

pairs = [[1,2], [7,8], [4,5]] Sorted by end: [[1,2], [4,5], [7,8]]

Pair	currEnd	Action
[1,2]	2	Pick [1,2], count=1
[4,5]	5	4 > 2? YES. Pick [4,5], count=2
[7,8]	8	7 > 5? YES. Pick [7,8], count=3

java

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        int count = 0, currEnd = Integer.MIN_VALUE;
        for (int[] p : pairs) {
            if (p[0] > currEnd) {
                count++;
                currEnd = p[1];
            }
        }
        return count;
    }
}

Meeting Rooms II

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

Visual Representation

Intervals: [[0, 30], [5, 10], [15, 20]]

Room 1: [0--------------------------30]
Room 2:    [5---10]   [15---20]

Max overlapping at any time: 2
Result: 2

Medium

Examples

Input: intervals = [[0,30], [5,10], [15,20]]
Output: 2
We need two rooms; one for [0, 30] and another for [5, 10] and [15, 20] sequentially.

Approach 1

Level I: Brute Force (Iterate All Time Points)

Intuition

Count the number of overlapping meetings at every possible time point. The maximum count across all time points is the minimum number of rooms needed.

Thought Process

Find the minStart and maxEnd across all intervals.
For every time $t$ $t$ from minStart to maxEnd:
- Count how many meetings are active at time $t$ (i.e., start <= t < end).
Return the maximum count found.

⏱ O(N * T) where T is the time range.💾 O(1)

Detailed Dry Run

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

t=0: active=[[0,30]]. Count=1.
t=5: active=[[0,30], [5,10]]. Count=2.
t=15: active=[[0,30], [15,20]]. Count=2. Max count = 2.

java

public class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int[] i : intervals) {
            min = Math.min(min, i[0]);
            max = Math.max(max, i[1]);
        }
        int maxRooms = 0;
        for (int t = min; t < max; t++) {
            int count = 0;
            for (int[] i : intervals) {
                if (t >= i[0] && t < i[1]) count++;
            }
            maxRooms = Math.max(maxRooms, count);
        }
        return maxRooms;
    }
}

Approach 2

Level II: Chronological Sorting (Sweep Line)

Intuition

When a meeting starts, we need a room; when it ends, we free a room. If we process all start and end points in chronological order, the max number of overlapping meetings at any point is our answer.

Thought Process

Separate starts and ends into two sorted arrays.
Use two pointers to iterate through them.
If startTime < endTime, a new meeting starts before an old one ends: increment rooms and startPtr.
Else, a meeting ends: decrement rooms and endPtr.

Pattern: Sweep Line / Two Pointers

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

Detailed Dry Run

Starts: [0, 5, 15], Ends: [10, 20, 30]

t=0: Start [0,30]. rooms=1. max=1.
t=5: Start [5,10]. rooms=2. max=2.
t=10: End [5,10]. rooms=1.
t=15: Start [15,20]. rooms=2. max=2.

java

public class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n], ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts); Arrays.sort(ends);
        int rooms = 0, max = 0, s = 0, e = 0;
        while (s < n) {
            if (starts[s] < ends[e]) {
                rooms++; s++;
            } else {
                rooms--; e++;
            }
            max = Math.max(max, rooms);
        }
        return max;
    }
}

Approach 3

Level III: Optimal Greedy (Min-Heap)

Intuition

As we process meetings by start time, we use a Min-Heap to track the end times of rooms currently in use. The top of the heap is the room that will be free soonest.

Thought Process

Sort meetings by start time.
Add the first meeting's end time to a Min-Heap.
For each next meeting, if its start >= heap.peek() (earliest end), we can reuse that room: heap.pop().
Always push current meeting's end time to the heap.
Answer is heap.size().

Pattern: Resource Allocation / Priority Queue

⏱ O(N log N) for sorting and heap ops.💾 O(N) for heap.

Detailed Dry Run

[[0,30],[5,10],[15,20]] Sorted

[0,30]: Heap=[30], rooms=1
[5,10]: 5 < 30? YES. Heap=[10, 30], rooms=2
[15,20]: 15 >= 10? YES. Pop 10, Push 20. Heap=[20, 30], rooms=2

java

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

Candy Distribution

Each child has a rating. You must give candies such that:

Every child gets at least 1 candy.
Children with a higher rating get more candies than their neighbors.

Return the minimum total candies.

Visual Representation

Ratings: [1, 0, 2]

Pass 1 (L->R):
[1, 0, 2] -> [1, 1, 2] (fixes child at index 2 rank > index 1)

Pass 2 (R->L):
[1, 0, 2] -> [2, 1, 2] (fixes child at index 0 rank > index 1)

Total: 5

Hard

Examples

Input: ratings = [1,0,2]
Output: 5
Candies: [2, 1, 2]. Total = 5.

Approach 1

Level I: Brute Force (Iterative Satisfaction)

Intuition

Repeatedly scan the ratings and candies. If a child has a higher rating than a neighbor but doesn't have more candies, give them one more. Repeat until no more changes are needed.

Thought Process

Initialize candies with 1 for all.
In a loop, keep track if any changes were made (changed = false).
For each child i:
- If ratings[i] > ratings[i-1] and candies[i] <= candies[i-1], set candies[i] = candies[i-1] + 1, changed = true.
- Same for i+1.
Stop when changed is false.

⏱ O(N^2) in the worst case (e.g., strictly increasing ratings).💾 O(N)

Detailed Dry Run

ratings=[1,2,3], initial=[1,1,1] Pass 1: [1,2,1] (i=1), [1,2,3] (i=2). changed=true. Pass 2: No changes. Total=6.

java

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < n; i++) {
                if (i > 0 && ratings[i] > ratings[i-1] && candies[i] <= candies[i-1]) {
                    candies[i] = candies[i-1] + 1; changed = true;
                }
                if (i < n - 1 && ratings[i] > ratings[i+1] && candies[i] <= candies[i+1]) {
                    candies[i] = candies[i+1] + 1; changed = true;
                }
            }
        }
        int sum = 0; for (int c : candies) sum += c; return sum;
    }
}

Approach 2

Level II: Peak and Valley (Single Pass)

Intuition

We can think of the ratings as a sequence of mountains (peaks) and valleys. The number of candies increases as we climb a mountain from a valley, and decreases as we descend. The 'peak' child gets the maximum needed from both sides.

Thought Process

Use variables up, down, and peak to track the current mountain slopes.
If rating increases, up++, down=0, peak=up. Candies += up + 1.
If rating decreases, down++, up=0. Candies += down.
If down > peak, we need to add one extra candy to the peak to keep it higher than the descending slope.

Pattern: Slope Analysis

⏱ O(N)💾 O(1)

Detailed Dry Run

ratings = [1, 2, 1]

i=1 (up): up=1, peak=1, candies = 1 + (1+1) = 3.
i=2 (down): down=1, up=0. down <= peak (1 <= 1). candies = 3 + 1 = 4. Sum = 4? Wait, [1, 2, 1] should be [1, 2, 1] -> 4. Correct.

java

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n <= 1) return n;
        int candies = 1, up = 0, down = 0, peak = 0;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                up++; down = 0; peak = up; candies += 1 + up;
            } else if (ratings[i] == ratings[i - 1]) {
                up = 0; down = 0; peak = 0; candies += 1;
            } else {
                down++; up = 0; candies += down + (down > peak ? 1 : 0);
            }
        }
        return candies;
    }
}

Approach 3

Level III: Optimal Greedy (Two Independent Passes)

Intuition

A child must satisfy two conditions: candies[i] > candies[i-1] if ratings[i] > ratings[i-1], and candies[i] > candies[i+1] if ratings[i] > ratings[i+1]. We can solve these separately.

Thought Process

Start all children with 1 candy.
L-to-R: If rating[i] > rating[i-1], set candies[i] = candies[i-1] + 1.
R-to-L: If rating[i] > rating[i+1], set candies[i] = max(candies[i], candies[i+1] + 1).

Pattern: Constraint Satisfaction in Multiple Passes

⏱ O(N) - Two passes.💾 O(N) for candies.

Detailed Dry Run

ratings = [1, 2, 8, 7, 3, 4, 1] L->R: [1, 2, 3, 1, 1, 2, 1] R->L: [1, 2, 3, 2, 1, 2, 1] Result: 12

java

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1])
                candies[i] = Math.max(candies[i], candies[i+1] + 1);
        }
        int sum = 0; for (int c : candies) sum += c;
        return sum;
    }
}

Minimum Cost to Connect Sticks

You have sticks with positive integer lengths. You can connect any two sticks into one by paying a cost equal to their sum. Return the minimum cost to connect all sticks.

Visual Representation

Sticks: [2, 4, 3]

1. Combine 2 and 3: Cost = 5. Remaining: [5, 4]
2. Combine 5 and 4: Cost = 9. Remaining: [9]
Total: 14

Medium

Examples

Input: sticks = [2,4,3]
Output: 14
Combining 2+3 first followed by 4 is cheaper than other combinations.

Approach 1

Level I: Brute Force (Try All Pairs)

Intuition

Try every possible sequence of connecting two sticks and find the one that results in the minimum total cost. This can be implemented using recursion by trying all pairs at each step.

Thought Process

If only 1 stick remains, return 0.
For every pair of sticks $(i, j)$ $(i, j)$ :
- Combine them: cost = sticks[i] + sticks[j].
- Recursively solve for the new set of sticks.
- Track the minimum total cost across all possible initial pairs.

⏱ O(N!)💾 O(N)

Detailed Dry Run

sticks = [2, 4, 3]

Option 1: (2,4) -> [6,3]. Then (6,3) -> [9]. Cost = 6 + 9 = 15.
Option 2: (2,3) -> [5,4]. Then (5,4) -> [9]. Cost = 5 + 9 = 14. (MIN)
Option 3: (4,3) -> [7,2]. Then (7,2) -> [9]. Cost = 7 + 9 = 16.

java

public class Solution {
    public int connectSticks(int[] sticks) {
        List<Integer> list = new ArrayList<>();
        for (int s : sticks) list.add(s);
        return solve(list);
    }
    private int solve(List<Integer> list) {
        if (list.size() <= 1) return 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                int sum = list.get(i) + list.get(j);
                List<Integer> next = new ArrayList<>();
                for (int k = 0; k < list.size(); k++)
                    if (k != i && k != j) next.add(list.get(k));
                next.add(sum);
                min = Math.min(min, sum + solve(next));
            }
        }
        return min;
    }
}

Approach 2

Level II: Sorting and Re-sorting

Intuition

At each step, we identify the two smallest sticks by sorting the list, combine them, and repeat. While better than brute force, re-sorting at every step is inefficient.

Thought Process

While more than 1 stick exists:
- Sort the current list of sticks.
- Take the two smallest elements, sum them.
- Add the sum to totalCost, remove the two elements, and add the sum back.
Repeat until 1 stick remains.

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

Detailed Dry Run

sticks = [2, 4, 3]

Sort: [2, 3, 4]. Combine 2+3=5. Total=5. Sticks: [5, 4]
Sort: [4, 5]. Combine 4+5=9. Total=14. Sticks: [9] Result: 14

java

public 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 sum = list.remove(0) + list.remove(0);
            total += sum;
            list.add(sum);
        }
        return total;
    }
}

Approach 3

Level III: Optimal Greedy (Min-Heap)

Intuition

To minimize the total cost, we should always combine the two smallest sticks currently available. This is the Huffman Coding principle.

Thought Process

Add all sticks to a Min-Heap.
While heap.size() > 1:
- Pop s1 and s2 (two smallest).
- cost = s1 + s2.
- totalCost += cost, Push cost back to heap.

Pattern: Huffman Coding (Greedy Merging)

⏱ O(N log N) for heap operations.💾 O(N) for heap.

Detailed Dry Run

Sticks: [1, 8, 3, 5]

Pop 1, 3. Sum = 4. Total = 4. Heap: [4, 5, 8]
Pop 4, 5. Sum = 9. Total = 13. Heap: [8, 9]
Pop 8, 9. Sum = 17. Total = 30. Result: 30

java

public class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int s : sticks) pq.add(s);
        int totalCost = 0;
        while (pq.size() > 1) {
            int sum = pq.poll() + pq.poll();
            totalCost += sum;
            pq.add(sum);
        }
        return totalCost;
    }
}

Patching Array

Add minimum elements to a sorted array so all numbers in [1, n] can be formed by sums.

Visual Representation

nums = [1, 3], n = 6

Reach: [1, 1] (via 1)
Next miss: 2. nums[i]=3 > 2. PATCH 2.
Reach: [1, 3] (via 1, 2)
Next miss: 4. nums[i]=3 <= 4. Use 3.
Reach: [1, 6] (via 1, 2, 3)
Done. Patches: 1

Hard

Examples

Input: nums = [1,3], n = 6
Output: 1
Adding 2 allows forming sums up to 6.

Approach 1

Level I: Brute Force (Recursion / Subsets)

Intuition

Try all possible combinations of patches (numbers from 1 to n) and check if each subset sum can form all numbers in [1, n]. This is extremely slow but guaranteed to find the minimum patches.

Thought Process

isPossible(current_nums, n): Checks if all numbers in [1, n] can be formed.
solve(current_nums, count): Recursively tries adding each possible number p that is not in current_nums.
Return the minimum count such that isPossible is true.

⏱ O(2^n * n^2) roughly.💾 O(n)

Detailed Dry Run

nums = [1, 3], n = 6

isPossible([1, 3], 6)? No (cannot form 2).
Try adding 2: [1, 2, 3]. sums: 1, 2, 3, 4(1+3), 5(2+3), 6(1+2+3). YES. Min patches = 1.

java

// Brute Force: Exponential complexity
// 1. Generate all power sets of [1, n].
// 2. Check each subset to see if it covers [1, n].
// 3. Return the smallest subset size minus original array size.

Approach 2

Level II: Dynamic Programming (Boolean Knapsack)

Intuition

Treat this as a variation of the Subset Sum problem. For a given set of numbers, maintain a boolean array can_form where can_form[i] is true if sum i can be reached.

Thought Process

dp[i] = true if sum i is possible.
Start with original nums. Update dp for each number.
If dp[miss] is false for some miss <= n, we must add a patch.
Greedy choice for patch is always the smallest missing number to maximize coverage.

⏱ O(N * n) where N is array size and n is target.💾 O(n)

Detailed Dry Run

nums = [1, 3], n = 6, dp=[T, F, F, F, F, F, F] (dp[0]=T)

Use 1: dp=[T, T, F, F, F, F, F]
Use 3: dp=[T, T, F, T, T, F, F]
Miss = 2. Patch 2.
Use 2: dp=[T, T, T, T, T, T, T]. DONE.

java

public class Solution {
    public int minPatches(int[] nums, int n) {
        // DP-based simulation to check reachability
        // This still requires a greedy choice for *which* number to patch.
        return -1; 
    }
}

Approach 3

Level III: Optimal Greedy (Reachability Range)

Intuition

Maintain the smallest number miss that cannot be formed. If nums[i] <= miss, use it to extend the range. Otherwise, patch miss to double the reach.

Thought Process

miss = current gap.
If nums[i] <= miss: miss += nums[i++].
Else: miss += miss, count++.

Pattern: Greedy Range Extension

⏱ O(M + log N).💾 O(1).

Detailed Dry Run

nums = [1, 5, 10], n = 20 miss=1: Use 1, miss=2 miss=2: nums[1]=5 > 2. Patch 2, miss=4 miss=4: nums[1]=5 > 4. Patch 4, miss=8 miss=8: Use 5, miss=13 miss=13: Use 10, miss=23. DONE.

java

public class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1; int patches = 0, i = 0;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) miss += nums[i++];
            else {
                miss += miss;
                patches++;
            }
        }
        return patches;
    }
}

Reorganize String

Rearrange string so no two adjacent characters are identical.

Visual Representation

s = "aaabcc"

a: 3, b: 1, c: 2

1. Fill 'a' at 0, 2, 4 -> [a, _, a, _, a, _]
2. Fill 'c' at 1, 3    -> [a, c, a, c, a, _]
3. Fill 'b' at 5       -> [a, c, a, c, a, b]

Medium

Examples

Input: s = "aab"
Output: "aba"
Interleaving 'a' and 'b' satisfies the requirement.

Approach 1

Level I: Brute Force (All Permutations)

Intuition

Generate all possible permutations of the input string $S$ and check if any of them satisfy the condition that no two adjacent characters are identical.

Thought Process

Use recursion to generate all $N!$ permutations.
For each unique permutation, check adjacency: s[i] == s[i+1].
Return the first valid permutation found, or "" if none exist.

⏱ O(N!)💾 O(N)

Detailed Dry Run

s = "aab" Permutations: ["aab", "aba", "baa"]

"aab": a == a (FAIL)
"aba": a != b, b != a (SUCCESS). Return "aba".

java

public class Solution {
    public String reorganizeString(String s) {
        List<String> res = new ArrayList<>();
        permute(s.toCharArray(), 0, res);
        return res.isEmpty() ? "" : res.get(0);
    }
    private void permute(char[] chars, int idx, List<String> res) {
        if (!res.isEmpty()) return;
        if (idx == chars.length) {
            if (isValid(chars)) res.add(new String(chars));
            return;
        }
        Set<Character> used = new HashSet<>();
        for (int i = idx; i < chars.length; i++) {
            if (!used.add(chars[i])) continue;
            swap(chars, idx, i);
            permute(chars, idx + 1, res);
            swap(chars, idx, i);
        }
    }
    private boolean isValid(char[] s) {
        for (int i = 0; i < s.length - 1; i++) if (s[i] == s[i+1]) return false;
        return true;
    }
    private void swap(char[] c, int i, int j) { char t = c[i]; c[i] = c[j]; c[j] = t; }
}

Approach 2

Level II: Greedy with Max-Heap

Intuition

Always pick the most frequent character that is different from the last one placed. A Max-Heap allows us to fetch the highest frequency character efficiently.

Thought Process

Count frequencies and push into a Max-Heap (count, char).
In each step, pop the top character.
Add it to the result and keep it aside (don't push back yet) because we can't use it in the very next step.
Push the character from the previous step back into the heap if it still has remaining count.

Pattern: Priority Queue / Interleaving

⏱ O(N log 26) = O(N).💾 O(26) = O(1).

Detailed Dry Run

s = "aaabcc" Heap: [(a,3), (c,2), (b,1)]

Pop (a,3). Res: "a". prev=(a,2)
Pop (c,2). Res: "ac". Push prev (a,2). prev=(c,1)
Pop (a,2). Res: "aca". Push prev (c,1). prev=(a,1) Result: "acacab"

java

public class Solution {
    public String reorganizeString(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.put(c, counts.getOrDefault(c, 0) + 1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (char c : counts.keySet()) pq.add(new int[]{c, counts.get(c)});
        
        StringBuilder sb = new StringBuilder();
        int[] prev = null;
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            sb.append((char) cur[0]);
            if (prev != null && prev[1] > 0) pq.add(prev);
            cur[1]--;
            prev = cur;
        }
        return sb.length() == s.length() ? sb.toString() : "";
    }
}

Approach 3

Level III: Optimal Greedy (Frequency Interleaving)

Intuition

Place the most frequent character at even indices (0, 2, 4...). If it fits, we can always interleave the rest.

Thought Process

Count frequencies. If any char count $> (N+1)/2$ , impossible.
Start with the most frequent char.
Fill indices 0, 2, 4... then wrap to 1, 3, 5...

Pattern: Frequency-Based Positioning

⏱ O(N).💾 O(N).

Detailed Dry Run

s = "aab" Max char 'a' count = 2. Place at 0, 2. [a, _, a] Next char 'b' count = 1. Place at 1. [a, b, a]

java

public class Solution {
    public String reorganizeString(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) counts[c - 'a']++;
        int max = 0, letter = 0, n = s.length();
        for (int i = 0; i < 26; i++) {
            if (counts[i] > max) { max = counts[i]; letter = i; }
        }
        if (max > (n + 1) / 2) return "";
        char[] res = new char[n];
        int idx = 0;
        while (counts[letter] > 0) {
            res[idx] = (char) (letter + 'a');
            idx += 2;
            counts[letter]--;
        }
        for (int i = 0; i < 26; i++) {
            while (counts[i] > 0) {
                if (idx >= n) idx = 1;
                res[idx] = (char) (i + 'a');
                idx += 2; counts[i]--;
            }
        }
        return String.valueOf(res);
    }
}

Minimum Number of K Consecutive Bit Flips

You are given a binary array nums and an integer k. A k-bit flip is choosing a subarray of length k and reversing all bits. Return the minimum flips to make all elements 1.

Visual Representation

nums = [0, 1, 0], k = 1

i=0: 0 -> Flip! [1, 1, 0], ans=1
i=1: 1 -> OK.
i=2: 0 -> Flip! [1, 1, 1], ans=2

Total: 2

Hard

Examples

Input: nums = [0,1,0], k = 1
Output: 2
Flip nums[0], then flip nums[2].

Approach 1

Level I: Brute Force Simulation

Intuition

Traverse the array from left to right. Whenever we encounter a 0, we flip the next k elements. If at any point we need to flip but don't have enough elements left, it's impossible.

Thought Process

For each index i from 0 to n-1:
- If nums[i] == 0:
  - Check if i + k > n. If so, return -1.
  - Manually flip nums[i...i+k-1].
  - Increment ans.
Return ans.

⏱ O(N * K)💾 O(1) (modifying input) or O(N) (copy).

Detailed Dry Run

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

i=0: nums[0]=0. Flip [0,1]. nums becomes [1, 0, 0, 1]. ans=1.
i=1: nums[1]=0. Flip [1,2]. nums becomes [1, 1, 1, 1]. ans=2.
i=2,3: nums[i]=1. OK. Result: 2

java

public class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (i + k > n) return -1;
                for (int j = i; j < i + k; j++) nums[j] ^= 1;
                ans++;
            }
        }
        return ans;
    }
}

Approach 2

Level II: Greedy with Queue

Intuition

Instead of manually flipping elements, use a queue to track which indices still have an active flip effect. This avoids the $O(K)$ inner loop.

Thought Process

Maintain a queue of indices where a flip was initiated.
At each index i, remove expired flips from the queue (indices $j$ where $j + k \le i$ ).
The number of flips currently affecting i is queue.size().
If nums[i] is effectively 0 (i.e., nums[i] == queue.size() % 2), start a new flip at i.

⏱ O(N)💾 O(K) for the queue.

Detailed Dry Run

nums = [0, 0, 0], k = 2 i=0: nums[0]=0, q=[] (size 0). 0==0. Push 0. q=[0], ans=1. i=1: nums[1]=0, q=[0] (size 1). 0!=1. OK. i=2: i-k=0. Expire 0. q=[]. nums[2]=0. 0==0. Push 2. i+k > n. Return -1.

java

public class Solution {
    public int minKBitFlips(int[] nums, int k) {
        Queue<Integer> q = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!q.isEmpty() && q.peek() + k <= i) q.poll();
            if (nums[i] == q.size() % 2) {
                if (i + k > nums.length) return -1;
                q.add(i);
                ans++;
            }
        }
        return ans;
    }
}

Approach 3

Level III: Optimal Greedy (Sliding Window Flips)

Intuition

Traverse left to right. If nums[i] is 0 after all previous flips affecting it, we MUST flip the window starting at i. Use a queue or difference array to track active flips efficiently.

Thought Process

curFlips = count of active flips affecting index i.
When index i reaches k, remove the effect of the flip that started at i-k.
If nums[i] is effectively 0 (i.e., nums[i] == curFlips % 2), flip it.

Pattern: Greedy Sliding Window Flip

⏱ O(N).💾 O(N) for flip tracking (can be O(1) if modifying input).

Detailed Dry Run

nums = [0,0,0,1,0], k=3 i=0: nums[0]=0, cur=0. Flip! ans=1, cur=1, mark[0]=1 i=1,2: cur=1, nums[i] effectively 1. OK. i=3: i>=3, remove mark[0]. cur=0. nums[3]=1. OK. i=4: nums[4]=0, cur=0. Flip! i+k > n. FAIL.

java

public class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length, curFlips = 0, ans = 0;
        int[] isFlipped = new int[n];
        for (int i = 0; i < n; i++) {
            if (i >= k) curFlips ^= isFlipped[i - k];
            if (nums[i] == curFlips) {
                if (i + k > n) return -1;
                isFlipped[i] = 1;
                curFlips ^= 1;
                ans++;
            }
        }
        return ans;
    }
}

Weighted Job Scheduling

Find maximum profit from non-overlapping jobs with given startTime, endTime, and profit.

Visual Representation

Jobs (S, E, P):
J1: [1, 3, 50], J2: [2, 4, 10], J3: [3, 5, 40], J4: [3, 6, 70]

Combination J1 (50) + J4 (70) = 120 (Max)

Hard

Examples

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
The subset of jobs [J1, J4] gives maximum profit.

Approach 1

Level I: Recursive Backtracking

Intuition

Try all possible subsets of compatible jobs and return the maximum profit. To handle compatibility, we sort by start time and at each step, decide to either pick the current job and skip all overlapping ones, or skip the current job.

Thought Process

solve(idx): Max profit starting from job idx.
Decision 1: Skip job idx -> solve(idx + 1).
Decision 2: Pick job idx. Find the next job k > idx that starts after jobs[idx].end. Result = profit[idx] + solve(k).
Return max(Decision 1, Decision 2).

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

Detailed Dry Run

Jobs: [1,3,50], [2,4,10], [3,5,40]

solve(0):
- Skip J1: solve(1)
- Pick J1: 50 + solve(2) (J3 starts at 3, J1 ends at 3). Result = 50 + 40 = 90.
Return 90.

java

public class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        return solve(0, jobs);
    }
    private int solve(int idx, int[][] jobs) {
        if (idx == jobs.length) return 0;
        // Skip
        int res = solve(idx + 1, jobs);
        // Pick
        int next = idx + 1;
        while (next < jobs.length && jobs[next][0] < jobs[idx][1]) next++;
        res = Math.max(res, jobs[idx][2] + solve(next, jobs));
        return res;
    }
}

Approach 2

Level II: Dynamic Programming (O(N^2))

Intuition

This is a variation of the Longest Increasing Subsequence (LIS) problem. For each job i, we look at all previous jobs j < i and if they are compatible, we update dp[i] = max(dp[i], dp[j] + profit[i]).

Thought Process

Sort jobs by end time.
dp[i] = max profit ending at job i.
For each i, iterate all j < i and check if jobs[j].end <= jobs[i].start.
This approach is $O(N^2)$ and will pass for medium constraints but TLE for $N=10^5$ .

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

Detailed Dry Run

Jobs: [J1:1-3, 50], [J2:2-4, 10], [J3:3-5, 40]

dp[0] = 50 (J1)
dp[1] = 10 (J2). J1 overlaps with J2.
dp[2] = 40 + dp[0] = 90. J1 is compatible with J3. Max Profit = 90.

java

public class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);
        int[] dp = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = jobs[i][2];
            for (int j = 0; j < i; j++) {
                if (jobs[j][1] <= jobs[i][0]) dp[i] = Math.max(dp[i], dp[j] + jobs[i][2]);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

Approach 3

Level III: Optimal (DP + Binary Search)

Intuition

Sort by end time. For each job, the max profit is either excluding it (same as max profit of previous job) or including it (profit + max profit of latest compatible job).

Thought Process

Combine data and sort by endTime.
dp[i] = max profit for first i jobs.
Search for the latest job j < i where jobs[j].end <= jobs[i].start using binary search.
dp[i] = max(dp[i-1], job[i].profit + dp[j]).

Pattern: Dynamic Programming + Binary Search

⏱ O(N log N) for sorting and binary searching.💾 O(N) for DP array.

Detailed Dry Run

Sorted: [J1:[1,3,50], J2:[2,4,10], J3:[3,5,40], J4:[3,6,70]] J1: dp[0]=50 J2: j=-1, dp[1]=max(50, 10)=50 J3: j=0, dp[2]=max(50, 40+50)=90 J4: j=0, dp[3]=max(90, 70+50)=120

java

public class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);
        int[] dp = new int[n];
        dp[0] = jobs[0][2];
        for (int i = 1; i < n; i++) {
            int cur = jobs[i][2];
            int l = 0, r = i - 1, idx = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (jobs[mid][1] <= jobs[i][0]) { idx = mid; l = mid + 1; }
                else r = mid - 1;
            }
            if (idx != -1) cur += dp[idx];
            dp[i] = Math.max(dp[i - 1], cur);
        }
        return dp[n - 1];
    }
}

Course Schedule III

Take maximum number of courses given [duration, lastDay] constraints.

Visual Representation

Courses: [[100, 200], [1000, 1250], [200, 1300]]

1. [100, 200]   -> time=100. Heap: [100].
2. [1000, 1250] -> time=1100. Heap: [100, 1000].
3. [200, 1300]  -> time=1300. Heap: [100, 200, 1000].

Result: 3

Hard

Examples

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Take course 1, 3, and 2.

Approach 1

Level I: Recursive Backtracking

Intuition

Try all possible subsets of courses. For each subset, check if there exists an ordering that satisfies all deadlines. The maximum subset size that works is the answer.

Thought Process

Generate all $2^N$ subsets of courses.
For each subset, sort it by deadline and check if it's feasible.
Return the maximum feasible subset size.

Pattern: Brute Force / Subsets

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

Detailed Dry Run

[[100,200], [1000, 1250], [200, 1300]]

Try subset [[100,200], [200,1300]]: Feasible? 100<=200 (Y), 300<=1300 (Y). Size 2.
Try subset [[100,200], [1000,1250], [200,1300]]: Feasible? 100<=200, 1100<=1250, 1300<=1300. YES. Size 3.

java

// Brute Force Code: Exponential O(2^N)
// Try every subset and check feasibility after sorting by deadline.

Approach 2

Level II: Dynamic Programming

Intuition

This can be viewed as an 0/1 Knapsack problem where the 'weight' is the duration and the 'limit' is the deadline. We sort by deadline first to ensure we process courses in an order that respects feasibility.

Thought Process

Sort courses by lastDay.
dp[i][t] = max courses among first i that can be finished by time t.
This is still too slow ( $N \cdot MaxDay$ ). A better DP is dp[i][j] = min time to finish j courses using first i courses.

Pattern: Dynamic Programming

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

Detailed Dry Run

Sorted: [[100,200], [200, 1300]] dp[0][0]=0, dp[0][1]=100 (others inf) dp[1][0]=0, dp[1][1]=min(100, 200)=100, dp[1][2]=100+200=300 (300<=1300? Yes)

java

public class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        int n = courses.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        int max = 0;
        for (int[] c : courses) {
            for (int j = max; j >= 0; j--) {
                if (dp[j] + c[0] <= c[1]) {
                    dp[j + 1] = Math.min(dp[j + 1], dp[j] + c[0]);
                    max = Math.max(max, j + 1);
                }
            }
        }
        return max;
    }
}

Approach 3

Level III: Optimal Greedy (Max-Heap + Retroactive Swap)

Intuition

Process courses by deadline. If a course doesn't fit, replace the longest course already taken with this shorter one to save time.

Thought Process

Sort by lastDay.
Maintain time and a Max-Heap of durations.
Add current duration to time and heap.
If time > lastDay, subtract the max duration from time (pop heap).

Pattern: Greedy with Retroactive Swap

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

Detailed Dry Run

[[100, 200], [500, 600], [200, 600]]

[100, 200]: time=100, heap=[100]
[500, 600]: time=600, heap=[500, 100]
[200, 600]: time=800 > 600. Pop 500. time=300, heap=[200, 100] Result: 2

java

public class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int time = 0;
        for (int[] c : courses) {
            time += c[0]; pq.add(c[0]);
            if (time > c[1]) time -= pq.poll();
        }
        return pq.size();
    }
}

Two City Scheduling

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCost_i, bCost_i], the cost of flying the $i^{th}$ person to city A is aCost_i, and the cost of flying the $i^{th}$ person to city B is bCost_i.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Visual Representation

Costs: [[10, 20], [30, 200], [400, 50], [30, 20]]

Profit of picking A over B (a - b):
1. 10 - 20  = -10
2. 30 - 200 = -170 (Huge saving if A)
3. 400 - 50 = +350 (Huge saving if B)
4. 30 - 20  = +10

Sorted diffs: -170, -10, +10, +350
Pick first 2 for A, last 2 for B.

Medium

Examples

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Fly person 1 and 2 to city A, and person 3 and 4 to city B.

Approach 1

Level I: Recursive Backtracking

Intuition

Try every possible way to assign $N$ people to City A and $N$ people to City B. This results in $\binom{2N}{N}$ combinations.

Thought Process

solve(idx, countA, countB): Assign person idx.
Option 1: Assign to A (if countA < n).
Option 2: Assign to B (if countB < n).
Return minimum total cost from both paths.

Pattern: Brute Force / Combinations

⏱ O(2^{2N}) or more accurately O(\binom{2N}{N}).💾 O(N) for recursion.

Detailed Dry Run

[[10,20], [30,200]]

A(10) then B(200) = 210
B(20) then A(30) = 50 Min = 50.

java

public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        return solve(0, 0, 0, costs.length / 2, costs, new HashMap<>());
    }
    private int solve(int i, int a, int b, int n, int[][] costs, Map<String, Integer> memo) {
        if (i == costs.length) return 0;
        String key = i + "," + a;
        if (memo.containsKey(key)) return memo.get(key);
        int res = Integer.MAX_VALUE;
        if (a < n) res = Math.min(res, costs[i][0] + solve(i + 1, a + 1, b, n, costs, memo));
        if (b < n) res = Math.min(res, costs[i][1] + solve(i + 1, a, b + 1, n, costs, memo));
        memo.put(key, res);
        return res;
    }
}

Approach 2

Level II: Dynamic Programming

Intuition

This is a classic 2D DP problem. dp[i][j] represents the minimum cost for the first i+j people, with i people assigned to City A and j people assigned to City B.

Thought Process

dp[i][j] = min cost for i in A and j in B.
Transition: dp[i][j] = min(dp[i-1][j] + costA, dp[i][j-1] + costB).
Base case: dp[0][0] = 0.

Pattern: 2D Dynamic Programming

⏱ O(N^2).💾 O(N^2) or O(N) using space optimization.

Detailed Dry Run

[[10,20], [30,200], [400,50], [30,20]] dp[1][0] = 10, dp[0][1] = 20 dp[1][1] = min(10+200, 20+30) = 50 dp[2][0] = 10+30 = 40 (N=2) ...

java

public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2;
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + costs[i - 1][0];
            dp[0][i] = dp[0][i - 1] + costs[i - 1][1];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + costs[i + j - 1][0], 
                                    dp[i][j - 1] + costs[i + j - 1][1]);
            }
        }
        return dp[n][n];
    }
}

Approach 3

Level III: Optimal Greedy (Sorting by Relative Cost)

Intuition

Imagine we send everyone to City B first. Now we need to pick $N$ people to 'swap' to City A. To minimize total cost, we should pick the people for whom the cost reduction (or least increase) of moving to A is greatest. This is $aCost - bCost$ .

Thought Process

Assume everyone goes to B initially (Total = $\sum bCost$ ).
The 'refund' we get by moving person $i$ to A instead of B is $(bCost_i - aCost_i)$ , or conversely, the 'extra cost' is $(aCost_i - bCost_i)$ .
Sort all people by $(aCost_i - bCost_i)$ .
Pick the first $N$ people (those with the most negative or smallest diffs) and send them to A.

Pattern: Greedy Difference Sorting

⏱ O(N log N) for sorting.💾 O(1) or O(N) depending on sort.

Detailed Dry Run

Costs: [[10,20], [30,200], [400,50], [30,20]] Diffs (A-B): [-10, -170, 350, 10] Sorted by diff: [-170, -10, 10, 350] People: [30,200], [10,20] -> Go to A. [30,20], [400,50] -> Go to B. Total: 30 + 10 + 20 + 50 = 110.

java

import java.util.*;

public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
        int total = 0, n = costs.length / 2;
        for (int i = 0; i < n; i++) total += costs[i][0]; // First n go to A
        for (int i = n; i < costs.length; i++) total += costs[i][1]; // Last n go to B
        return total;
    }
}

Hand of Straights

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Visual Representation

Hand: [1,2,3,6,2,3,4,7,8], Size: 3

1. Smallest is 1. Start group: [1, 2, 3]. Remaining: [6, 2, 3, 4, 7, 8]
2. Smallest is 2. Start group: [2, 3, 4]. Remaining: [6, 7, 8]
3. Smallest is 6. Start group: [6, 7, 8]. Remaining: []
Result: True

Medium

Examples

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Approach 1

Level I: Recursive Backtracking

Intuition

Try all possible ways to group the cards. For each card, either start a new group or add it to an existing incomplete group. This is highly inefficient but follows the core requirement.

Thought Process

solve(remaining_cards): Pick a card and try to form a group of groupSize starting with it.
Recurse with the remaining cards.
If all cards are used, return true.

Pattern: Brute Force / Backtracking

⏱ O(N!) or O(N^N).💾 O(N)

Detailed Dry Run

Hand: [1,2,3,4], Size: 2

Try [1,2], left [3,4].
Try [3,4], left []. Success.

java

// Brute Force Code: Exponential O(N!)
// Try all permutations of groups.

Approach 2

Level II: Sorting + Simulation (O(N^2))

Intuition

Sort the hand first. Then, repeatedly find the smallest card and try to form a group of size groupSize starting from it by searching for subsequent cards in the array.

Thought Process

Sort hand.
Use a boolean array used to mark cards.
For each i from 0 to n-1:
- If !used[i]:
  - Mark used[i] = true. This is the start of a group.
  - Search for hand[i]+1, hand[i]+2, ..., hand[i]+groupSize-1 in the remaining array.
  - If any card is not found or already used, return false.

Pattern: Sorting and Linear Scanning

⏱ O(N^2).💾 O(N) for used array.

Detailed Dry Run

Hand: [1,2,2,3,3,4], Size: 3. Sorted: [1,2,2,3,3,4]

Start with 1. Find 2 (idx 1) and 3 (idx 3). Mark used. [X, X, 2, X, 3, 4]
Next unused is 2. Find 3 (idx 4) and 4 (idx 5). Mark used. [X, X, X, X, X, X] Success.

java

public class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        Arrays.sort(hand);
        boolean[] used = new boolean[hand.length];
        for (int i = 0; i < hand.length; i++) {
            if (used[i]) continue;
            int next = hand[i];
            used[i] = true;
            for (int k = 1; k < groupSize; k++) {
                boolean found = false;
                for (int j = i + 1; j < hand.length; j++) {
                    if (!used[j] && hand[j] == next + 1) {
                        used[j] = true;
                        next = hand[j];
                        found = true;
                        break;
                    }
                }
                if (!found) return false;
            }
        }
        return true;
    }
}

Approach 3

Level III: Optimal Greedy (TreeMap/Frequency Map)

Intuition

To form consecutive groups, every 'start' of a group must be the smallest available card. If we always start groups with the smallest remaining card, we either succeed or hit a card that cannot complete a group.

Thought Process

Count frequencies of all cards.
Sort unique cards (using a TreeMap or sorted keys).
For each card $C$ $C$ that still has remaining counts:
- It MUST be the start of count[C] groups.
- Each such group requires cards $C+1, C+2, ..., C+groupSize-1$ .
- If any of these cards have fewer counts than count[C], return false.
- Decrement counts of all cards in the group.

Pattern: Greedy Frequency Grouping

⏱ O(N log N) for sorting/map operations.💾 O(N) for map.

Detailed Dry Run

Hand: [1,2,2,3,3,4], Size: 3 Map: {1:1, 2:2, 3:2, 4:1}

Smallest is 1. Count=1. Start group [1,2,3]. Map becomes: {1:0, 2:1, 3:1, 4:1}
Next smallest is 2. Count=1. Start group [2,3,4]. Map becomes: {2:0, 3:0, 4:0} Result: True.

java

import java.util.*;

public class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int h : hand) map.put(h, map.getOrDefault(h, 0) + 1);
        
        for (int h : map.keySet()) {
            int count = map.get(h);
            if (count > 0) {
                for (int i = 0; i < groupSize; i++) {
                    if (map.getOrDefault(h + i, 0) < count) return false;
                    map.put(h + i, map.get(h + i) - count);
                }
            }
        }
        return true;
    }
}

Minimum Initial Energy to Finish Tasks

You are given an array tasks where tasks[i] = [actual_i, minimum_i]:

actual_i is the actual amount of energy you spend to finish the $i^{th}$ task.
minimum_i is the minimum amount of energy you need to begin the $i^{th}$ task.

You can finish the tasks in any order. Return the minimum initial amount of energy you need to finish all tasks.

Visual Representation

Tasks: [[1, 3], [2, 4], [10, 11]]

Optimal Order: Sort by (minimum - actual) descending.
1. [1, 3]: diff 2
2. [2, 4]: diff 2
3. [10, 11]: diff 1

Simulation starting with 14:
[1, 3]: 14 >= 3. Spend 1. Left 13.
[2, 4]: 13 >= 4. Spend 2. Left 11.
[10,11]: 11 >= 11. Spend 10. Left 1.
Result: 14

Hard

Examples

Input: tasks = [[1,3],[2,4],[10,11]]
Output: 14
Starting with 14 energy: finish [1,3] (left 13), [2,4] (left 11), [10,11] (left 1).

Approach 1

Level I: Brute Force (All Permutations)

Intuition

Since we can finish tasks in any order, we can try all $N!$ permutations of tasks. For each permutation, we calculate the minimum initial energy required to complete the tasks in that specific order. The answer is the minimum of these values.

Thought Process

Generate all $N!$ permutations of tasks.
For each permutation:
- Start with current energy $E = 0$ (working backwards) or try binary search on initial energy.
- Simpler: starting backwards from the last task, energy = max(min_i, energy + actual_i).
Return the minimum energy found across all permutations.

Pattern: Brute Force / Permutations

⏱ O(N! * N) - Factorial number of permutations.💾 O(N) for recursion stack.

java

import java.util.*;

public class Main {
    public static int minimumEffort(int[][] tasks) {
        // To find all permutations and get the minimum, the logic would be complex.
        // A simpler way: try all permutations using recursion.
        return -1; // Placeholder for brute force logic
    }

    public static void main(String[] args) {
        System.out.println("Brute force tries all N! orders of tasks.");
    }
}

Approach 2

Level II: Binary Search on Initial Energy

Intuition

If we can finish the tasks with initial energy E, then we can also finish them with any energy E' > E. This monotonicity allows us to binary search for the minimum energy. However, even with binary search, we still need a greedy order to verify feasibility efficiently.

Thought Process

Search range: [sum(actual), 10^9].
canFinish(energy): Try a greedy order (e.g., sort by minimum - actual desc) and see if the tasks are completed.
If canFinish(mid) is true, try smaller; else try larger.

Pattern: Binary Search on Answer

⏱ O(N log N + N log MaxSum).💾 O(1).

Detailed Dry Run

Try Energy 14 for [[1,3],[2,4],[10,11]]

Task [1,3]: 14 >= 3. Spend 1. Left 13.
Task [2,4]: 13 >= 4. Spend 2. Left 11.
Task [10,11]: 11 >= 11. Spend 10. Left 1. True. Try Energy 13...

java

public class Solution {
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));
        int l = 0, r = 1000000000, ans = r;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (check(mid, tasks)) { ans = mid; r = mid - 1; }
            else l = mid + 1;
        }
        return ans;
    }
    private boolean check(int energy, int[][] tasks) {
        for (int[] t : tasks) {
            if (energy < t[1]) return false;
            energy -= t[0];
        }
        return energy >= 0;
    }
}

Approach 3

Level III: Optimal Greedy (Sorting)

Intuition

To minimize initial energy, we want to perform tasks that 'save' the most energy requirement for later. The 'saved' energy after a task is $(minimal - actual)$ . Sorting tasks by this difference in descending order ensures we handle the most restrictive tasks (relative to their cost) while we have the most energy.

Thought Process

Sort tasks by (minimum - actual) descending.
Work backwards: Start with 0 energy. For each task, you must have at least m energy, so energy = max(m, energy + a).
Alternatively, work forwards: Keep track of totalEnergy needed and currentEnergy available.

Pattern: Greedy Sorting

⏱ O(N log N) for sorting.💾 O(1) if sorting in place.

Detailed Dry Run

tasks = [[1,3],[2,4],[10,11]] Sorted by (m-a) desc: [1,3] (2), [2,4] (2), [10,11] (1)

Task	Actual	Minimal	New Energy Needed
[10,11]	10	11	max(11, 0+10) = 11
[2,4]	2	4	max(4, 11+2) = 13
[1,3]	1	3	max(3, 13+1) = 14

java

import java.util.*;

public class Main {
    public static int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));
        int effort = 0, current = 0;
        for (int[] task : tasks) {
            if (current < task[1]) {
                effort += task[1] - current;
                current = task[1];
            }
            current -= task[0];
        }
        return effort;
    }

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

Maximum Number of Events That Can Be Attended

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 at any day d.

Return the maximum number of events you can attend.

Visual Representation

Events: [[1, 2], [1, 2], [3, 3]]

Day 1: Attend [1, 2] (Event 1)
Day 2: Attend [1, 2] (Event 2)
Day 3: Attend [3, 3] (Event 3)
Result: 3

Medium

Examples

Input: events = [[1,2],[1,2],[3,3]]
Output: 3
You can attend all 3 events.

Approach 1

Level I: Brute Force (Recursive Scheduling)

Intuition

Try every possible combination of events you could attend. For each subset of events, check if there exists a valid day for each event such that no two events are attended on the same day and each event is attended within its [start, end] range.

Thought Process

Use recursion to try and attend or skip each event.
When attending an event, try every possible day in its range $[start, end]$ that hasn't been used yet.
Keep track of the maximum number of events attended.
This approach is $O(2^N \cdot MaxDay)$ or worse if checking all day combinations.

Pattern: Backtracking / Search

⏱ O(2^N * MaxDay) - Exponential.💾 O(N + MaxDay) for recursion and tracking used days.

java

import java.util.*;

public class Main {
    public static int maxEvents(int[][] events) {
        // Brute force would involve trying all subsets and checking validity.
        return -1; // Placeholder
    }

    public static void main(String[] args) {
        System.out.println("Brute force tries all possible subsets of events.");
    }
}

Approach 2

Level II: Greedy Simulation (O(N^2))

Intuition

For each day, we scan all available events that have not been attended yet and pick the one that ends the earliest. This is a direct simulation of the optimal strategy without a Priority Queue.

Thought Process

Sort events by startDay.
Maintain a used boolean array.
For each day d from minStart to maxEnd:
- Find an unvisited event i such that events[i].start <= d and events[i].end >= d and it has the minimum end time among all such candidates.
- If found, mark used[i] = true and increment count.

Pattern: Greedy Scanning

⏱ O(MaxDay * N).💾 O(N) for used array.

Detailed Dry Run

Events: [[1,2],[1,2],[3,3]] Day 1: Both [1,2] available. Pick one. Mark used. Day 2: Only other [1,2] available. Pick it. Mark used. Day 3: [3,3] available. Pick it. Mark used. Total: 3.

java

public class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);
        int n = events.length, res = 0;
        boolean[] usedDays = new boolean[100001];
        for (int[] e : events) {
            for (int d = e[0]; d <= e[1]; d++) {
                if (!usedDays[d]) {
                    usedDays[d] = true;
                    res++;
                    break;
                }
            }
        }
        return res;
    }
}

Approach 3

Level III: Optimal Greedy (Min-Heap + Sorting)

Intuition

On any given day, if multiple events are available, we should prioritize the one that ends the earliest. This is because an event with a later end day can potentially be attended on a future day.

Thought Process

Sort events by startDay.
Use a Min-Heap to store the end days of currently available events.
Iterate through days:
- Add all events starting today to the heap.
- Remove events from the heap that have already ended.
- If the heap is not empty, attend the event that ends the earliest (pop from heap) and increment count.

Pattern: Greedy / Priority Queue

⏱ O(N log N + MaxDay log N) - Sorting and heap operations.💾 O(N) for the heap.

Detailed Dry Run

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

Day	Add to Heap	Expired	Attend	Heap
1	[2, 2]	-	Attend(2)	[2]
2	-	-	Attend(2)	[]
3	[3]	-	Attend(3)	[]
Result: 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> pq = new PriorityQueue<>();
        int i = 0, n = events.length, res = 0;
        for (int d = 1; d <= 100000; d++) {
            while (i < n && events[i][0] == d) pq.add(events[i++][1]);
            while (!pq.isEmpty() && pq.peek() < d) pq.poll();
            if (!pq.isEmpty()) {
                pq.poll();
                res++;
            }
            if (pq.isEmpty() && i == n) break;
        }
        return res;
    }

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

← Previous TopicDynamic Programming

Next Topic →Backtracking

Found an issue or have a suggestion?

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