Home/DSA Complete from Scratch to Expert/dsa-topics

Two Pointers

Master this topic with zero to advance depth.

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^{th} line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.

Visual Representation

Height: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Index:   0  1  2  3  4  5  6  7  8

    |                   |
    |                   |       |
    |   |               |       |
    |   |       |       |       |
    |   |       |   |   |       |
    |   |       |   |   |   |   |
    |   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |   |
0   1   2   3   4   5   6   7   8
    L                           R  
    (Area = min(8, 7) * (8 - 1) = 7 * 7 = 49)

Medium

Examples

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
The max area is between index 1 (height 8) and index 8 (height 7). Area = min(8, 7) * (8 - 1) = 49.

Approach 1

Level I: Brute Force (Check All Pairs)

Intuition

To find the maximum water, we can check every possible pair of lines and calculate the volume of water they can hold. The volume is determined by the shorter of the two lines multiplied by the distance between them.

Check every possible pair of lines and calculate the area for each. Keep track of the maximum area found so far.

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

Detailed Dry Run

Left Index (i)	Right Index (j)	Height[i]	Height[j]	Width (j-i)	Min Height	Area	Max Area
0	1	1	8	1	1	1	1
0	2	1	6	2	1	2	2
0	8	1	7	8	1	8	8
1	2	8	6	1	6	6	8
1	8	8	7	7	7	49	49

java

public class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int area = Math.min(height[i], height[j]) * (j - i);
                max = Math.max(max, area);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
    }
}

⚠️ Common Pitfalls & Tips

O(N^2) complexity leads to TLE for large inputs.

Approach 2

Level II: Greedy (Optimized Two Pointers)

Intuition

We can improve the basic two-pointer approach by skipping heights that are smaller than or equal to the heights we've already processed on either side. This doesn't change the asymptotic O(N) complexity but reduces the number of area calculations in practice.

Start with two pointers. After calculating the area, move the pointer pointing to the shorter bar. Instead of calculating the area at every step, continue moving that pointer as long as the next bar is shorter than the one we just left.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]

L=0(1), R=8(7). Area=8. Move L.
L=1(8). Current Max Area = 8.
R=8(7). Area=49. Move R.
R=7(3). H[7] < H[8]. SKIP! Move R to index 6.
R=6(8). Area=40. ...

java

public int maxArea(int[] height) {
    int l = 0, r = height.length - 1, max = 0;
    while (l < r) {
        int h = Math.min(height[l], height[r]);
        max = Math.max(max, h * (r - l));
        while (l < r && height[l] <= h) l++;
        while (l < r && height[r] <= h) r--;
    }
    return max;
}

⚠️ Common Pitfalls & Tips

While this skips some iterations, it is still O(N) in the worst case.

Approach 3

Level III: Optimal (Two Pointers - Collision)

Intuition

The area is limited by the shorter bar. If we move the pointer pointing to the longer bar inward, the width decreases while the height stays limited by the same (or an even shorter) shorter bar, meaning the area can only decrease.

Therefore, the only way to potentially find a larger area is to move the pointer pointing to the shorter bar inward, in hopes of finding a taller bar that compensates for the loss in width.

Start with two pointers at both ends. The area is limited by the shorter line. To potentially find a larger area, we must replace the shorter line by moving that pointer inward.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]

L	R	H[L]	H[R]	Width	Current Area	Max Area	Action
0	8	1	7	8	1*8 = 8	8	H[L] < H[R] → L++
1	8	8	7	7	7*7 = 49	49	H[R] < H[L] → R--
1	7	8	3	6	3*6 = 18	49	H[R] < H[L] → R--
1	6	8	8	5	8*5 = 40	49	H[L] = H[R] → L++ or R--

java

public class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, max = 0;
        while (l < r) {
            max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) l++;
            else r--;
        }
        return max;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
    }
}

⚠️ Common Pitfalls & Tips

Always move the pointer with the smaller height. If both are equal, moving either side is fine.

Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers, [index1, index2], added by one.

Visual Representation

numbers = [2, 7, 11, 15], target = 9

L: index 0 (val 2)
R: index 3 (val 15)
Sum = 2 + 15 = 17 (> 9) -> Move R left (R=2)

L: index 0 (val 2)
R: index 2 (val 11)
Sum = 2 + 11 = 13 (> 9) -> Move R left (R=1)

L: index 0 (val 2)
R: index 1 (val 7)
Sum = 2 + 7 = 9 (== 9) -> FOUND! [1, 2] (1-indexed)

Easy

Examples

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Approach 1

Level I: Brute Force (Check All Pairs)

Intuition

Try every possible pair of numbers to see if they sum up to the target. While correct, it doesn't leverage the fact that the array is sorted.

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

Detailed Dry Run

i	j	nums[i]	nums[j]	Sum	Target	Match?
0	1	2	7	9	9	YES! Return [1, 2]

java

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] res = sol.twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println(res[0] + ", " + res[1]);
    }
}

⚠️ Common Pitfalls & Tips

O(N^2) complexity is inefficient for large arrays.

Approach 2

Level II: Binary Search

Intuition

For each element at index i, we know the required second element is target - numbers[i]. Since the array is sorted, we can use binary search to find this complement in the sub-array to the right of i (numbers[i+1...n-1]).

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

Detailed Dry Run

Input: [2, 7, 11, 15], Target: 9

i = 0 (2): Search for 9 - 2 = 7 in [7, 11, 15].
Binary Search found 7 at index 1.
Return [1, 2].

java

public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int low = i + 1, high = numbers.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] == target - numbers[i]) return new int[]{i + 1, mid + 1};
            if (numbers[mid] < target - numbers[i]) low = mid + 1;
            else high = mid - 1;
        }
    }
    return new int[]{-1, -1};
}

⚠️ Common Pitfalls & Tips

While better than O(N^2), it is still worse than the O(N) Two Pointer approach.

Approach 3

Level III: Optimal (Two Pointer Collision)

Intuition

Since the array is sorted, we can start with two pointers at the extreme ends. If the sum is too small, we move the left pointer right (to increase values). If the sum is too large, we move the right pointer left (to decrease values). This is guaranteed to find the solution in one pass.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [2, 7, 11, 15], Target: 9

R	Sum	Action
3 (15)	17	Sum > 9, move R left (R--)
2 (11)	13	Sum > 9, move R left (R--)
1 (7)	9	Sum == 9, RETURN [1, 2]

java

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return new int[]{l + 1, r + 1};
            if (sum < target) l++;
            else r--;
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] res = sol.twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println(res[0] + ", " + res[1]);
    }
}

⚠️ Common Pitfalls & Tips

Ensure 1-based indexing. This approach only works on sorted arrays.

3Sum

Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that i \neq j, i \neq k, and j \neq k, and nums[i] + nums[j] + nums[k] == 0.

Visual Representation

Sorted Array: [-4, -1, -1, 0, 1, 2]

Step 1: Fix i = -1 (Index 1)
        L = -1 (Index 2), R = 2 (Index 5)
        Sum = -1 + (-1) + 2 = 0 -> FOUND! [-1, -1, 2]

Step 2: L moves to 0 (Index 3), R moves to 1 (Index 4)
        Sum = -1 + 0 + 1 = 0 -> FOUND! [-1, 0, 1]

Medium

Examples

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
The triplets are (-1, 0, 1) and (-1, -1, 2).

Approach 1

Level I: Brute Force (Check All Triplets)

Intuition

Check every possible combination of three numbers to see if they sum to zero. To avoid duplicate triplets, we can sort each triplet and store it in a Set.

⏱ O(N^3)💾 O(k) where k is the number of triplets

Detailed Dry Run

| i | j | k | nums[i] | nums[j] | nums[k] | Sum | Result | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 0 | 1 | 2 | -1 | 0 | 1 | 0 | FOUND! [-1, 0, 1] |

java

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(triplet);
                        res.add(triplet);
                    }
                }
            }
        }
        return new ArrayList<>(res);
    }

    public static void main(String[] args) {
        System.out.println(new Solution().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}

⚠️ Common Pitfalls & Tips

O(N^3) complexity is too slow for N > 1000.

Approach 2

Level II: Better (Sorting + Binary Search)

Intuition

If we sort the array and fix two elements nums[i] and nums[j], we need to find -(nums[i] + nums[j]) in the remaining part of the array. Since it is sorted, we can use binary search.

Sort the array.
Fix two pointers i and j.
Search for the required third value using binary search in the range (j+1, n-1).

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

Detailed Dry Run

Input: [-1, 0, 1, 2, -1, -4]. Sorted: [-4, -1, -1, 0, 1, 2]

i=-4, j=-1: Search for 5? Not found.
i=-1, j=-1: Search for 2? FOUND at index 5. Result: [-1, -1, 2].
i=-1, j=0: Search for 1? FOUND at index 4. Result: [-1, 0, 1].

java

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    Set<List<Integer>> res = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            int target = -(nums[i] + nums[j]);
            int low = j + 1, high = nums.length - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (nums[mid] == target) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[mid]));
                    break;
                }
                if (nums[mid] < target) low = mid + 1;
                else high = mid - 1;
            }
        }
    }
    return new ArrayList<>(res);
}

⚠️ Common Pitfalls & Tips

O(N^2 log N) is better than O(N^3) but still not as good as the O(N^2) two-pointer solution.

Approach 3

Level III: Optimal (Sort + Two Pointers)

Intuition

To optimize, we sort the array first. This allows us to use the Two Pointers technique for the 'Two Sum' part of the problem.

Fix the first element nums[i].
Use Two Pointers (L = i+1, R = n-1) to find pairs that sum to -nums[i].
Skip duplicate values for i, L, and R to ensure unique triplets.

⏱ O(N^2)💾 O(1) (excluding sorting space)

Detailed Dry Run

Input: [-1, 0, 1, 2, -1, -4]. Sorted: [-4, -1, -1, 0, 1, 2]

i	val[i]	L	R	Sum	Action
0	-4	1 (-1)	5 (2)	-3	Sum < 0, L++
1	-1	2 (-1)	5 (2)	0	FOUND! L++, R--
1	-1	3 (0)	4 (1)	0	FOUND! L++, R--

java

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++; r--;
                } else if (sum < 0) l++;
                else r--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}

⚠️ Common Pitfalls & Tips

Remember to skip duplicate values for all three pointers to avoid duplicate triplets in the result.

4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that their sum is equal to target (0 <=q a, b, c, d < n and are distinct).

Visual Representation

Sorted: [-2, -1, 0, 0, 1, 2], Target: 0

Step 1: Fix i = -2, j = -1
        L = 0, R = 2
        Sum = -2 + (-1) + 1 + 2 = 0 -> FOUND! [-2, -1, 1, 2]

Step 2: Fix i = -2, j = 0
        L = 0, R = 2
        Sum = -2 + 0 + 0 + 2 = 0 -> FOUND! [-2, 0, 0, 2]

Medium

Examples

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
There are three unique quadruplets that sum to 0.

Approach 1

Level I: Brute Force (Check All Quadruplets)

Intuition

Try every possible combination of four numbers to see if they sum up to the target. To avoid duplicates, we sort each quadruplet and store it in a Set.

⏱ O(N^4)💾 O(K) where K is the number of unique quadruplets

Detailed Dry Run

Input: [1, 0, -1, 0, -2, 2], Target: 0 Combination (1, 0, -1, 0) -> Sum 0. Found! Combination (1, 0, -2, 2) -> Sum 1. Skip. ...

java

public List<List<Integer>> fourSum(int[] nums, int target) {
    Set<List<Integer>> res = new HashSet<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    if ((long)nums[i] + nums[j] + nums[k] + nums[l] == target) {
                        List<Integer> q = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
                        Collections.sort(q);
                        res.add(q);
                    }
                }
            }
        }
    }
    return new ArrayList<>(res);
}

⚠️ Common Pitfalls & Tips

O(N^4) will TLE for N > 200.

Approach 2

Level II: Sorting + HashSet

Intuition

By sorting and using a HashSet for the fourth element, we can reduce the complexity to O(N^3). It's essentially 3Sum but with one more outer loop.

Fix three pointers i, j, k, and check if target - (nums[i] + nums[j] + nums[k]) exists in a HashSet of the remaining elements.

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

Detailed Dry Run

Input: [1, 0, -1, 0, -2, 2], Target: 0

Fix 1, 0, -1. Need 0. Found 0 in the array. Quads: [1, 0, -1, 0].
Fix 1, 0, -2. Need 1. Found 1. Quads: [1, 0, -2, 1]... No, 1 was already used. Use indices to avoid reuse.

java

public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    Set<List<Integer>> res = new HashSet<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                long rem = (long)target - nums[i] - nums[j] - nums[k];
                int low = k + 1, high = n - 1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (nums[mid] == rem) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[k], (int)rem));
                        break;
                    }
                    if (nums[mid] < rem) low = mid + 1;
                    else high = mid - 1;
                }
            }
        }
    }
    return new ArrayList<>(res);
}

⚠️ Common Pitfalls & Tips

O(N^3) is still slow for very large constraints but works for N=200-500.

Approach 3

Level III: Optimal (Sort + Two Pointers)

Intuition

This is a direct extension of 3Sum. We sort the array and use two nested loops to fix the first two numbers (i and j). Then we use the Two Pointer technique to find the remaining two numbers (L and R).

⏱ O(N^3)💾 O(1) (excluding sorting space)

Detailed Dry Run

Sorted: [-2, -1, 0, 0, 1, 2], Target: 0

i	j	L	R	Sum	Action
-2	-1	0	1	-3	Sum < 0, L++
-2	-1	1	2	0	FOUND! L++, R--
-2	0	0	2	0	FOUND! L++, R--

java

import java.util.*;

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int l = j + 1, r = n - 1;
                while (l < r) {
                    long sum = (long)nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++; r--;
                    } else if (sum < target) l++;
                    else r--;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
    }
}

⚠️ Common Pitfalls & Tips

Be mindful of integer overflow in Java/C++ when adding four large integers. Use long or long long for the sum.

Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, in the order red, white, and blue. We use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

Visual Representation

Array: [2, 0, 2, 1, 1, 0]

Step 1: Move 0s to the front (Left side).
Step 2: Move 2s to the end (Right side).
Step 3: 1s will naturally be in the middle.

Result: [0, 0, 1, 1, 2, 2]

Medium

Examples

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
The array is sorted in-place to group 0s, 1s, and 2s.

Approach 1

Level I: Two Pass (Counting)

Intuition

Since there are only three possible values (0, 1, 2), we can count the frequency of each and then overwrite the original array.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [2, 0, 2, 1, 1, 0]

Count: 0: 2, 1: 2, 2: 2.
Overwrite: nums[0..1]=0, nums[2..3]=1, nums[4..5]=2. Result: [0, 0, 1, 1, 2, 2]

java

public class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int n : nums) count[n]++;
        int idx = 0;
        for (int i = 0; i < 3; i++) {
            while (count[i]-- > 0) nums[idx++] = i;
        }
    }
}

⚠️ Common Pitfalls & Tips

Requires two passes over the data.

Approach 2

Level II: Better (Two Pass - Two Pointers)

Intuition

Instead of counting all colors at once, we can use two passes with two pointers. In the first pass, we move all 0s to the front. In the second pass, we move all 1s from where the 0s ended.

Pass 1: Pointer p at start. Iterate, if nums[i] == 0, swap with p++.
Pass 2: Iterate starting from p. If nums[i] == 1, swap with p++.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [2, 0, 1]

Pass 1 (for 0): [0, 2, 1], p=1.
Pass 2 (for 1): [0, 1, 2], p=2.

java

public void sortColors(int[] nums) {
    int p = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) swap(nums, i, p++);
    }
    for (int i = p; i < nums.length; i++) {
        if (nums[i] == 1) swap(nums, i, p++);
    }
}
private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }

⚠️ Common Pitfalls & Tips

Still O(N) but takes two passes. Standard Dutch National Flag is better.

Approach 3

Level III: Optimal (One Pass - Dutch National Flag)

Intuition

Use three pointers to partition the array: low for 0s, high for 2s, and curr for the current element. This allows sorting in a single pass.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [2,0,1]

low=0, curr=0, high=2. nums[0]=2: Swap with high. Array: [1,0,2], high=1.
curr=0. nums[0]=1: curr++. Array: [1,0,2], curr=1.
curr=1. nums[1]=0: Swap with low. Array: [0,1,2], low=1, curr=2.
DONE.

java

public void sortColors(int[] nums) {
    int low = 0, curr = 0, high = nums.length - 1;
    while (curr <= high) {
        if (nums[curr] == 0) {
            int tmp = nums[low];
            nums[low++] = nums[curr];
            nums[curr++] = tmp;
        } else if (nums[curr] == 2) {
            int tmp = nums[high];
            nums[high--] = nums[curr];
            nums[curr] = tmp;
        } else curr++;
    }
}

⚠️ Common Pitfalls & Tips

Be careful not to increment curr when swapping with high, as the newly swapped element needs to be checked.

Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

String: "abca", l=0, r=3
1. s[0]=='a', s[3]=='a' -> Match. l=1, r=2.
2. s[1]=='b', s[2]=='c' -> Mismatch!
3. Option A: Delete 'b' (l=1). Check s[2..2] ("c"). Palindrome!
4. Option B: Delete 'c' (r=2). Check s[1..1] ("b"). Palindrome!
Result: true

Easy

Examples

Input: s = "abca"
Output: true
You could delete the character 'c' to get 'aba', which is a palindrome.

Approach 1

Level I: Brute Force (Check All Deletions)

Intuition

For each character in the string, try deleting it and check if the resulting string is a palindrome. This covers all possible single-character deletions.

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

Detailed Dry Run

Input: "abca"

Delete 'a': "bca" (No)
Delete 'b': "aca" (YES!) Return true.

java

public boolean validPalindrome(String s) {
    for (int i = 0; i < s.length(); i++) {
        String t = s.substring(0, i) + s.substring(i + 1);
        if (isPalindrome(t)) return true;
    }
    return isPalindrome(s);
}
private boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

⚠️ Common Pitfalls & Tips

O(N^2) complexity will TLE for large strings (N=10^5).

Approach 2

Level II: Better (Greedy with One Skip)

Intuition

Use two pointers from both ends. When characters don't match, we have two choices: delete the character at L or the character at R. If either resulting substring is a palindrome, the whole string satisfies the condition.

Iterate with L=0, R=n-1. If s[L] == s[R], move both. If not, check isPalindrome(s, L+1, R) OR isPalindrome(s, L, R-1).

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: "abca"

L=0(a), R=3(a). Match. L=1, R=2.
L=1(b), R=2(c). Mismatch!
Check isPalindrome("c", 2, 2) (YES) or isPalindrome("b", 1, 1) (YES). Return true.

java

public boolean validPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) {
            return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
        }
        l++; r--;
    }
    return true;
}
private boolean isPalindrome(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

⚠️ Common Pitfalls & Tips

Be careful with off-by-one errors when slicing substrings.

Approach 3

Level III: Optimal (Two Pointers - Greedy)

Intuition

Use two pointers starting from ends. If characters mismatch, we have two choices: delete the character at L or the character at R. If either resulting substring is a palindrome, the whole string satisfies the condition.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: s = "aba"

l=0, r=2: mismatch at s[1] vs s[2]? No, match. Input: s = "abca"
l=1 ('b'), r=2 ('c'): mismatch!
Check s[2..2] ("c"): Palindrome.
Check s[1..1] ("b"): Palindrome.
Return true.

java

class Solution {
    public boolean validPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
            }
            l++; r--;
        }
        return true;
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}

⚠️ Common Pitfalls & Tips

After removing one character, the remaining string must be a perfect palindrome. Don't forget that l+1 and r-1 are the only two options.

Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Nums: [2, 3, 1, 2, 4, 3], Target: 7

Step 1: Expand [2, 3, 1, 2], Sum = 8 (>=7). Len = 4.
Step 2: Shrink [3, 1, 2], Sum = 6 (<7). Expand.
Step 3: Expand [3, 1, 2, 4], Sum = 10 (>=7). Len = 4.
Step 4: Shrink [1, 2, 4], Sum = 7 (>=7). Len = 3.
Step 5: Shrink [2, 4], Sum = 6 (<7). Expand.
Step 6: Expand [2, 4, 3], Sum = 9 (>=7). Len = 3.
Step 7: Shrink [4, 3], Sum = 7 (>=7). Len = 2. (MIN)

Medium

Examples

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
The subarray [4,3] has the minimal length (2) under the problem constraint.

Approach 1

Level I: Brute Force (Check All Subarrays)

Intuition

Iterate through every possible subarray, calculate its sum, and check if it's >= target. Keep track of the minimum length found.

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

Detailed Dry Run

Input: target=7, nums=[2,3,1]

Subarrays: [2], [2,3], [2,3,1], [3], [3,1], [1].
All sums < 7. No valid subarray found.

java

public int minSubArrayLen(int target, int[] nums) {
    int minLen = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum >= target) {
                minLen = Math.min(minLen, j - i + 1);
                break;
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

⚠️ Common Pitfalls & Tips

O(N^2) will time out for arrays of size 10^5.

Approach 2

Level II: Better (Prefix Sums + Binary Search)

Intuition

Since all numbers are positive, the prefix sums array will be strictly increasing. For each index i, we can use binary search to find the smallest index j such that sum(0..j) - sum(0..i-1) >= target.

⏱ O(N log N)💾 O(N) (for prefix sums array)

Detailed Dry Run

target=7, nums=[2,3,1,2,4,3] PrefixSums: [0, 2, 5, 6, 8, 12, 15]

For i=0 (val 2): binary search for 7+0=7 in PrefixSums → Found 8 at index 4. Len = 4.
For i=4 (val 4): binary search for 7+8=15 → Found 15 at index 6. Len = 2.

java

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length, minLen = Integer.MAX_VALUE;
    int[] sums = new int[n + 1];
    for (int i = 1; i <= n; i++) sums[i] = sums[i - 1] + nums[i - 1];
    for (int i = 1; i <= n; i++) {
        int toFind = target + sums[i - 1];
        int bound = Arrays.binarySearch(sums, toFind);
        if (bound < 0) bound = -bound - 1;
        if (bound <= n) minLen = Math.min(minLen, bound - (i - 1));
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

⚠️ Common Pitfalls & Tips

Requires binary search logic (or built-in functions) and O(N) extra space.

Approach 3

Level III: Optimal (Sliding Window)

Intuition

Since all numbers are positive, a larger window will always have a larger sum. We can use a sliding window defined by two pointers, left and right. We expand right to increase the sum and shrink left to minimize the window size while maintaining the condition sum >= target.

⏱ O(N) (Each element is visited at most twice)💾 O(1)

Detailed Dry Run

Input: target=7, nums=[2,3,1,2,4,3]

r=0..2: sum=6.
r=3: sum=8. minLen=4, sum-=nums[0]=6, l=1.
r=4: sum=10. minLen=4, sum-=nums[1]=7, minLen=3. sum-=nums[2]=6, l=3.
r=5: sum=9. minLen=3, sum-=nums[3]=7, minLen=2. sum-=nums[4]=4, l=5. Result: 2

java

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, sum = 0, minLen = Integer.MAX_VALUE;
        for (int r = 0; r < nums.length; r++) {
            sum += nums[r];
            while (sum >= target) {
                minLen = Math.min(minLen, r - l + 1);
                sum -= nums[l++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

⚠️ Common Pitfalls & Tips

If all elements are positive, the window sum is monotonic. If negative numbers were present, this approach wouldn't work.

Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space.

Input: "  the sky is blue  "

Step 1: Trim & Reverse the entire string.
        "eulb si yks eht"

Step 2: Reverse each word in place.
        "blue is sky the"

Medium

Examples

Input: s = "the sky is blue"
Output: "blue is sky the"
The words are reversed. Extra spaces are removed.

Approach 1

Level I: Built-in Split & Reverse

Intuition

Most languages provide utility functions to split a string by spaces and join them back. This is the most readable way to solve it.

⏱ O(N)💾 O(N)

Detailed Dry Run

" hello world " -> Split -> ["hello", "world"] -> Reverse -> ["world", "hello"] -> Join -> "world hello"

java

public String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    Collections.reverse(Arrays.asList(words));
    return String.join(" ", words);
}

⚠️ Common Pitfalls & Tips

The input may have leading, trailing, or multiple spaces between words.

Approach 2

Level II: Better (In-place Array Modification)

Intuition

To optimize for space (if the string was mutable like an array), we can: 1. Remove extra spaces. 2. Reverse the entire array. 3. Reverse each word individualy.

⏱ O(N)💾 O(N) (In languages where strings are immutable, we still need O(N) space)

Detailed Dry Run

"the sky" → "yks eht" → "sky the"

java

public String reverseWords(String s) {
    char[] a = s.toCharArray();
    int n = a.length;
    reverse(a, 0, n - 1);
    reverseWords(a, n);
    return cleanSpaces(a, n);
}
private void reverse(char[] a, int i, int j) {
    while (i < j) { char t = a[i]; a[i++] = a[j]; a[j--] = t; }
}

⚠️ Common Pitfalls & Tips

Managing multiple spaces and in-place reversal can be tricky index-wise.

Approach 3

Level III: Optimal (Two Pointers - Backwards Traversal)

Intuition

Traverse the string from right to left, identifying words and adding them to a result. This avoids using heavy split/join functions.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: "sky blue"

i=7 ('e'): word end.
Move i to 4 (' '): word start. Word: "blue".
Skip spaces. i=2 ('y'): word end.
Move i to start: Word: "sky". Result: "blue sky"

java

public String reverseWords(String s) {
    StringBuilder res = new StringBuilder();
    int i = s.length() - 1;
    while (i >= 0) {
        if (s.charAt(i) == ' ') { i--; continue; }
        int j = i;
        while (i >= 0 && s.charAt(i) != ' ') i--;
        if (res.length() > 0) res.append(" ");
        res.append(s.substring(i + 1, j + 1));
    }
    return res.toString();
}

⚠️ Common Pitfalls & Tips

Be careful with leading and trailing spaces. The i+1 and j+1 indices are crucial.

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is only one repeated number, return this repeated number. You must solve the problem without modifying the array nums and use only constant extra space.

Array: [1, 3, 4, 2, 2]
Index:  0  1  2  3  4

Treat values as pointers:
0 -> 1 -> 3 -> 2 -> 4 -> 2... (Cycle!)
                    ^----|

Medium

Examples

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

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

Approach 1

Level I: Sorting

Intuition

If we sort the array, the duplicate number will be adjacent to itself. This modifies the input array, which is usually not ideal, but it's a simple first approach.

⏱ O(N log N)💾 O(1) (or O(N) depending on sort implementation)

Detailed Dry Run

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

Sorted: [1, 2, 2, 3, 4]
nums[1] == nums[2]? YES. Return 2.

java

public int findDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i-1]) return nums[i];
    }
    return -1;
}

⚠️ Common Pitfalls & Tips

Modifies the input array, which may violate problem constraints.

Approach 2

Level II: HashSet / Visited Array

Intuition

As we iterate through the array, keep track of numbers we've seen. If we see a number again, it's the duplicate.

⏱ O(N)💾 O(N)

Detailed Dry Run

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

Seen: {1, 3, 4, 2}
Next is 2. 2 is in Seen. Return 2.

java

public int findDuplicate(int[] nums) {
    boolean[] seen = new boolean[nums.length];
    for (int n : nums) {
        if (seen[n]) return n;
        seen[n] = true;
    }
    return -1;
}

⚠️ Common Pitfalls & Tips

Uses O(N) space, violating the constant space constraint.

Approach 3

Level III: Floyd's Cycle Finding (Tortoise and Hare)

Intuition

Since the array contains values in the range [1, n] and has n+1 elements, we can treat the array values as pointers to indices. A duplicate value will cause multiple indices to point to the same next index, creating a cycle. We can use Floyd's algorithm to find the entrance of this cycle, which is our duplicate number.

Find Intersection: Use a slow (1 step) and fast (2 steps) pointer. Move them until they meet in a cycle.
Find Entrance: Reset another pointer to the start of the array. Move both pointers one step at a time. The point where they meet is the start of the cycle (the duplicate number).

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [1, 3, 4, 2, 2] indices: 0->1->2->3->4 values: 1, 3, 4, 2, 2 Linked List: 0 -> 1 -> 3 -> 2 -> 4 -> 2...

Phase 1: slow at 1, fast at 3. Then slow at 3, fast at 4. Then slow at 2, fast at 2. MEET!
Phase 2: p1=0, p2=2 (meeting point).

Loop 1: p1 = nums[0] = 1, p2 = nums[2] = 4
Loop 2: p1 = nums[1] = 3, p2 = nums[4] = 2
Loop 3: p1 = nums[3] = 2, p2 = nums[2] = 4... Meeting at 2.

java

public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
}

⚠️ Common Pitfalls & Tips

This only works if the array values are in the range [1, n]. If there's a 0, the pointer logic might get stuck at index 0.

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Visual Representation

Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Bars:      #
      #    ## #
    # ## # ######
    010210132121

Water trapped (W):
      #
      # WW #
    #W##W######

Total Trapped: 6 units

Hard

Examples

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
The elevation map [0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units of rain water.

Approach 1

Level I: Brute Force (Iterate per Unit of Water)

Intuition

For each element, the amount of water it can trap is determined by the maximum height to its left and its right. Water level = min(maxLeft, maxRight) - currentHeight.

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

Detailed Dry Run

Input: [0, 1, 0, 2] Index 2 (height 0): maxL=1, maxR=2. min(1, 2) - 0 = 1. Total = 1.

java

public int trap(int[] height) {
    int res = 0;
    for (int i = 0; i < height.length; i++) {
        int maxL = 0, maxR = 0;
        for (int j = 0; j <= i; j++) maxL = Math.max(maxL, height[j]);
        for (int j = i; j < height.length; j++) maxR = Math.max(maxR, height[j]);
        res += Math.min(maxL, maxR) - height[i];
    }
    return res;
}

⚠️ Common Pitfalls & Tips

O(N^2) is very slow for large inputs (N=10^5).

Approach 2

Level II: Precomputing Max Left/Right

Intuition

Instead of re-calculating maxLeft and maxRight for every index, we can precompute them using two arrays in O(N).

Create leftMax array where leftMax[i] stores max height from index 0 to i. Create rightMax array similarly for index i to n-1.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: [0, 1, 0, 2] leftMax: [0, 1, 1, 2] rightMax: [2, 2, 2, 2] Water at index 2: min(1, 2) - 0 = 1.

java

public int trap(int[] height) {
    int n = height.length;
    int[] lM = new int[n], rM = new int[n];
    lM[0] = height[0]; rM[n-1] = height[n-1];
    for (int i = 1; i < n; i++) lM[i] = Math.max(lM[i-1], height[i]);
    for (int i = n-2; i >= 0; i--) rM[i] = Math.max(rM[i+1], height[i]);
    int res = 0;
    for (int i = 0; i < n; i++) res += Math.min(lM[i], rM[i]) - height[i];
    return res;
}

⚠️ Common Pitfalls & Tips

O(N) space is used for the auxiliary arrays.

Approach 3

Level III: Optimal (Two Pointers)

Intuition

At any index i, the water trapped is min(maxLeft, maxRight) - height[i]. Instead of precalculating max arrays, we can use two pointers from ends. The pointer with the smaller max determines the water level for that side.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [4, 2, 0, 3, 2, 5]

l=0, r=5. LMax=4, RMax=5. 4 < 5, move l to 1.
l=1: height=2. Water += 4-2=2. l=2.
l=2: height=0. Water += 4-0=4. l=3.
l=3: height=3. Water += 4-3=1. l=4.
l=4: height=2. Water += 4-2=2. l=5. Total water: 2+4+1+2 = 9.

java

public class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, water = 0;
        int leftMax = 0, rightMax = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] >= leftMax) leftMax = height[l];
                else water += leftMax - height[l];
                l++;
            } else {
                if (height[r] >= rightMax) rightMax = height[r];
                else water += rightMax - height[r];
                r--;
            }
        }
        return water;
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the update condition: only add water if the current height is less than the current side's max height.

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(\log(m+n)).

Visual Representation

nums1: [1, 3], nums2: [2]

Merged Sorted View:
[ 1, 2, 3 ]
     ^
   Median = 2.0

Partition View (Optimal):
nums1: [ 1 | 3 ]
nums2: [ 2 |   ]
Left Side: {1, 2}, Right Side: {3}
Median = Max(Left) = 2.0

Hard

Examples

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
merged array = [1,2,3] and median is 2.

Approach 1

Level I: Brute Force (Merge Sort Style)

Intuition

Merge the two sorted arrays into a single sorted array and find the middle element(s).

Use the merge step from Merge Sort to combine the two arrays into one of size m+n. Calculate the median from the result.

⏱ O(M+N)💾 O(M+N)

Detailed Dry Run

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

Combined array length = 3.
Merge: i=0, j=0. nums1[0] < nums2[0] (1 < 2), merged = [1], i=1.
i=1, j=0. nums2[0] < nums1[1] (2 < 3), merged = [1, 2], j=1.
i=1, j=1. nums1[1] = 3, merged = [1, 2, 3], i=2.
Median = merged[3/2] = merged[1] = 2.0.

java

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int[] merged = new int[m + n];
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) merged[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
    while (i < m) merged[k++] = nums1[i++];
    while (j < n) merged[k++] = nums2[j++];
    if ((m + n) % 2 == 0) return (merged[(m + n) / 2 - 1] + merged[(m + n) / 2]) / 2.0;
    return merged[(m + n) / 2];
}

⚠️ Common Pitfalls & Tips

Violates the O(log(M+N)) time requirement. Uses O(M+N) space.

Approach 2

Level II: Better (Two Pointers - Merge Part Only)

Intuition

Since both arrays are already sorted, we can use the merge step of Merge Sort to combine them in O(M+N). We don't even need to store the whole combined array; we only need to keep track of the middle elements.

Iterate through both arrays using two pointers, keeping track of the values seen. Stop when we reach the middle index (or indices if even).

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

Detailed Dry Run

Input: [1, 3], [2]

Total size 3, Median index 1.
Pointers: i=0, j=0. Compare 1 and 2. 1 is smaller. count=0, val=1, i=1.
Compare 3 and 2. 2 is smaller. count=1, val=2, j=1.
Median is 2.

java

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n1 = nums1.length, n2 = nums2.length, n = n1 + n2;
    int i=0, j=0, count=0, m1=-1, m2=-1;
    while (count <= n/2) {
        m2 = m1;
        if (i < n1 && (j >= n2 || nums1[i] < nums2[j])) m1 = nums1[i++];
        else m1 = nums2[j++];
        count++;
    }
    if (n % 2 == 0) return (m1 + m2) / 2.0;
    return m1;
}

⚠️ Common Pitfalls & Tips

O(M+N) is good but the problem asks for O(log(M+N)).

Approach 3

Level III: Optimal (Binary Search on Partitions)

Intuition

Instead of merging, we can partition the two arrays into two halves (left and right) such that the left half contains half of the elements and all elements in the left half are <= all elements in the right half.

Binary search on the smaller array to find a partition. For array A (smaller) at midA, and array B at midB = (total+1)/2 - midA, checking if A[midA-1] <= B[midB] and B[midB-1] <= A[midA].

⏱ O(log(min(M,N)))💾 O(1)

Detailed Dry Run

Input: nums1 = [1,3], nums2 = [2] Total elements = 3. Target partition size for left half = (3+1)/2 = 2.

Assume nums1 is the smaller array (x=2, y=1).
Binary search partitionX in nums1 from low=0 to high=2.
- Try partitionX = 1 (mid of 0,2).
  - partitionY = (2+1+1)/2 - 1 = 2 - 1 = 1.
  - maxLeftX = nums1[0] = 1
  - minRightX = nums1[1] = 3
  - maxLeftY = nums2[0] = 2
  - minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY] -> nums2[1] is out of bounds, so minRightY = Infinity.
- Check conditions: maxLeftX <= minRightY (1 <= Infinity) -> True. maxLeftY <= minRightX (2 <= 3) -> True.
- Conditions met! Total elements (3) is odd. Median = max(maxLeftX, maxLeftY) = max(1, 2) = 2.0.

java

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    int x = nums1.length, y = nums2.length;
    int low = 0, high = x;
    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;
        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
        int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
        int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 == 0) return (double)(Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            else return (double)Math.max(maxLeftX, maxLeftY);
        } else if (maxLeftX > minRightY) high = partitionX - 1;
        else low = partitionX + 1;
    }
    return 0.0;
}

⚠️ Common Pitfalls & Tips

Be careful with the partition logic and even/odd total counts. Binary search must be on the smaller array for O(log(min(M,N))).

Shortest Palindrome

You are given a string s. You can convert s to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Hard

Examples

Input: s = "aacecaaa"
Output: "aaacecaaa"
Add 'a' to the front to get 'aaacecaaa', which is a palindrome.

Input: s = "abcd"
Output: "dcbabcd"
Add 'dcb' to the front to get 'dcbabcd'.

Approach 1

Level I: Brute Force (Prefix Check)

Intuition

The problem asks for the shortest palindrome created by adding chars to the front. This means we are effectively looking for the longest prefix of s that is already a palindrome.

Iterate through the string from the end. For each index i, check if s[0...i] is a palindrome. If it is, then the substring s[i+1...n-1] must be reversed and prepended to s.

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

Detailed Dry Run

s = "abcd" → prefix "abcd" is NOT → prefix "abc" is NOT → prefix "ab" is NOT → prefix "a" IS. Reverse "bcd" → "dcb". Result: "dcbabcd".

java

public String shortestPalindrome(String s) {
    int n = s.length();
    String rev = new StringBuilder(s).reverse().toString();
    for (int i = 0; i < n; i++) {
        if (s.substring(0, n - i).equals(rev.substring(i))) {
            return rev.substring(0, i) + s;
        }
    }
    return "";
}

⚠️ Common Pitfalls & Tips

Inefficient for large N (O(N^2) due to substring/startswith checks inside a loop).

Approach 2

Level II: Better (Two Pointers Recursion)

Intuition

We can use two pointers to find the largest prefix that could be a palindrome. We match characters from the beginning and end. If they match, we move both. If not, we skip the end character. Finally, we recurse on the unmatched middle part.

⏱ O(N^2) worst case, but faster on average💾 O(N)

Detailed Dry Run

s="aacecaaa". i=0, j=7. s[0]==s[7]... Match up to some point. Recurse.

java

public String shortestPalindrome(String s) {
    int j = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == s.charAt(j)) j++;
    }
    if (j == s.length()) return s;
    String suffix = s.substring(j);
    return new StringBuilder(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;
}

⚠️ Common Pitfalls & Tips

O(N^2) in worst case (e.g., "aaaaa...ab"). Recursion depth can be an issue.

Approach 3

Level III: Optimal (KMP Longest Prefix Function)

Intuition

We can use the KMP pattern matching logic (next array or lps array) to find the longest prefix that is a palindrome in O(N) time. We construct a temporary string T = s + "#" + reverse(s).

In the string s + "#" + rev(s), the last value of the KMP lookup table gives the length of the longest prefix of s that matches a suffix of rev(s), which is exactly the longest palindromic prefix.

⏱ O(N)💾 O(N)

Detailed Dry Run

s="aacecaaa", rev="aaacecaa". T="aacecaaa#aaacecaa". LPS[last] = 7. Prefix length 7 ("aacecaa") is palindrome. Prep rev[0...8-7] = "a". Result: "aaacecaaa".

java

public String shortestPalindrome(String s) {
    String temp = s + "#" + new StringBuilder(s).reverse().toString();
    int[] table = getTable(temp);
    return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
}
private int[] getTable(String s) {
    int[] table = new int[s.length()];
    int j = 0;
    for (int i = 1; i < s.length(); i++) {
        while (j > 0 && s.charAt(i) != s.charAt(j)) j = table[j - 1];
        if (s.charAt(i) == s.charAt(j)) j++;
        table[i] = j;
    }
    return table;
}

⚠️ Common Pitfalls & Tips

The separator '#' is necessary to ensure the prefix search doesn't cross the boundary into the reversed portion.

Minimum Window Subsequence

Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part. If there is no such window, return an empty string.

Visual Representation

s1 = "abcdebdde", s2 = "bde"

Forward Pass:
a b c d e b d d e
  ^   ^ ^
  b...d.e (Found at res[1...5])

Backward Pass (Optimization):
From index 4, look for 'e', then 'd', then 'b' backwards.
Found 'b' at index 1 -> Best Window: "bcde"

Hard

Examples

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
"bcde" is the smallest substring of s1 where "bde" is a subsequence.

Approach 1

Level I: Brute Force

Intuition

Check every possible substring of s1 and verify if s2 is a subsequence of that substring.

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

Detailed Dry Run

s1="abcde", s2="bde". Substrings: "a", "ab", "abc", "abcd", "abcde" (Check "abcde": "b","d","e" found! Length 5). Next index...

java

public String minWindow(String s1, String s2) {
    String res = "";
    int minLen = s1.length() + 1;
    for (int i = 0; i < s1.length(); i++) {
        for (int j = i; j < s1.length(); j++) {
            if (isSubsequence(s2, s1.substring(i, j + 1))) {
                if (j - i + 1 < minLen) {
                    minLen = j - i + 1;
                    res = s1.substring(i, j + 1);
                }
            }
        }
    }
    return res;
}

⚠️ Common Pitfalls & Tips

O(N^2 * M) is extremely slow and will time out.

Approach 2

Level II: Better (Dynamic Programming)

Intuition

We can use DP where dp[i][j] stores the starting index of the shortest substring in s1[0..j] that contains s2[0..i] as a subsequence.

If s1[j] == s2[i], then dp[i][j] = dp[i-1][j-1]. Otherwise, dp[i][j] = dp[i][j-1].

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

Detailed Dry Run

s1 = 'abcde', s2 = 'bde'. DP table tracks the best starting index for every prefix of s2 found in s1.

java

public String minWindow(String s1, String s2) {
    int m = s2.length(), n = s1.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int j = 0; j <= n; j++) dp[0][j] = j + 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(j-1) == s2.charAt(i-1)) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = dp[i][j-1];
        }
    }
    int start = 0, len = n + 1;
    for (int j = 1; j <= n; j++) {
        if (dp[m][j] != 0) {
            if (j - dp[m][j] + 1 < len) {
                len = j - dp[m][j] + 1; start = dp[m][j] - 1;
            }
        }
    }
    return len == n + 1 ? "" : s1.substring(start, start + len);
}

⚠️ Common Pitfalls & Tips

Space complexity O(N*M) can be reduced to O(N).

Approach 3

Level III: Optimal (Two Pointers - Two Way Scan)

Intuition

Finding a subsequence window can be done by scanning forward to find any valid window and then scanning backward to minimize the window size from the starting side. This is more efficient than a simple sliding window because subsequence requirements are more flexible than substring requirements.

Scan s1 forward matching characters of s2 one by one. Once all characters are matched, we have a valid ending index.
Move backward from the ending index matching characters of s2 in reverse to find the latest possible start index for this specific end index.
Record the window, shrink the search space, and repeat.

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

Detailed Dry Run

s1 = 'abcdebdde', s2 = 'bde'.

Forward: find 'b'(1), 'd'(3), 'e'(4). end=5.
Backward from index 4: 'e'(4), 'd'(3), 'b'(1). start=1. Window [1, 5)='bcde'.

java

public class Solution {
    public String minWindow(String s1, String s2) {
        int i = 0, j = 0, start = -1, minL = s1.length() + 1;
        while (i < s1.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                if (++j == s2.length()) {
                    int end = i + 1;
                    for (j--; j >= 0; i--)
                        if (s1.charAt(i) == s2.charAt(j)) j--;
                    i++; j++;
                    if (end - i < minL) { minL = end - i; start = i; }
                }
            }
            i++;
        }
        return start == -1 ? "" : s1.substring(start, start + minL);
    }
}

⚠️ Common Pitfalls & Tips

Ensure the backward pass correctly identifies the latest start index. O(N*M) is the standard solution.

Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Visual Representation

s = "eceba", k = 2

Indices: 0 1 2 3 4
Chars:   e c e b a

1. Window [0,0]: {e} (1 distinct) <= 2, Max=1
2. Window [0,1]: {e, c} (2 distinct) <= 2, Max=2
3. Window [0,2]: {e, c, e} (2 distinct) <= 2, Max=3
4. Window [0,3]: {e, c, e, b} (3 distinct) > 2
   - Shrink from left: [1,3] -> {c, e, b} (3 distinct) > 2
   - Shrink from left: [2,3] -> {e, b} (2 distinct) <= 2, Max=3

Hard

Examples

Input: s = "eceba", k = 2
Output: 3
The substring is "ece" which has length 3.

Approach 1

Level I: Brute Force

Intuition

Generate all possible substrings and for each substring, count the number of distinct characters. If it's <= k, update the maximum length.

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

Detailed Dry Run

Input: s = "eceba", k = 2

i=0:
- j=0 (e): {e}, size=1 <= 2. maxLen = 1
- j=1 (c): {e, c}, size=2 <= 2. maxLen = 2
- j=2 (e): {e, c}, size=2 <= 2. maxLen = 3
- j=3 (b): {e, c, b}, size=3 > 2. BREAK
i=1:
- j=1 (c): {c}, size=1 <= 2. maxLen = 3
- j=2 (e): {c, e}, size=2 <= 2. maxLen = 3
- j=3 (b): {c, e, b}, size=3 > 2. BREAK

java

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        Set<Character> distinct = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            distinct.add(s.charAt(j));
            if (distinct.size() <= k) maxLen = Math.max(maxLen, j - i + 1);
            else break;
        }
    }
    return maxLen;
}

⚠️ Common Pitfalls & Tips

O(N^2) time complexity is too slow for N=10^5.

Approach 2

Level II: Sliding Window (Using Dictionary/Frequency Map)

Intuition

Instead of checking all substrings, use two pointers to maintain a window. Expand the right pointer, and if the count of unique characters exceeds k, move the left pointer until the count is back to k.

⏱ O(N)💾 O(K)

Detailed Dry Run

Input: s = "eceba", k = 2

r=0 (e): map={e:1}, size=1. max=1
r=1 (c): map={e:1, c:1}, size=2. max=2
r=2 (e): map={e:2, c:1}, size=2. max=3
r=3 (b): map={e:2, c:1, b:1}, size=3 > 2.
- Move l=0 (e): map={e:1, c:1, b:1}, size=3
- Move l=1 (c): map={e:1, b:1}, size=2. loop ends.

java

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s.length() == 0 || k == 0) return 0;
    Map<Character, Integer> counts = new HashMap<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); right++) {
        counts.put(s.charAt(right), counts.getOrDefault(s.charAt(right), 0) + 1);
        while (counts.size() > k) {
            char leftChar = s.charAt(left);
            counts.put(leftChar, counts.get(leftChar) - 1);
            if (counts.get(leftChar) == 0) counts.remove(leftChar);
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

⚠️ Common Pitfalls & Tips

O(N) time but O(K) space for the mapping.

Approach 3

Level III: Optimal (Sliding Window + Hash Map)

Intuition

Use a sliding window with two pointers i and j. Maintain a frequency map of characters in the current window. If the number of distinct characters exceeds k, shrink the window from the left until it's valid again.

Add characters from the right. When map.size() > k, remove from the left and update the count. Keep track of the max j - i + 1.

⏱ O(N)💾 O(k)

Detailed Dry Run

eceba, k=2. Window: [e,c,e] -> ok, max=3. Add 'b': [e,c,e,b] -> distinct=3 > 2. Shrink left until distinct <= 2: [e,b] -> ok, len=2.

java

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> counts = new HashMap<>();
    int i = 0, j = 0, maxLen = 0;
    for (j = 0; j < s.length(); j++) {
        counts.put(s.charAt(j), counts.getOrDefault(s.charAt(j), 0) + 1);
        while (counts.size() > k) {
            char leftChar = s.charAt(i);
            counts.put(leftChar, counts.get(leftChar) - 1);
            if (counts.get(leftChar) == 0) counts.remove(leftChar);
            i++;
        }
        maxLen = Math.max(maxLen, j - i + 1);
    }
    return maxLen;
}

⚠️ Common Pitfalls & Tips

Ensure the character count reaches zero before removing it from the map. Using a map size as the distinct count is robust.

Subarrays with K Different Integers

Given an integer array nums and an integer k, return the number of good subarrays of nums. A good subarray is an array where the number of different integers in that array is exactly k.

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

Exactly(K) = AtMost(K) - AtMost(K-1)

AtMost(2): [1], [1,2], [2], [2,1], [1,2,1], [1,2], [2], [2,1,2], [1,2,1,2], [2,3], [3] (etc)
AtMost(1): [1], [2], [1], [2], [3]

Exactly(2) = 12 - 5 = 7

Hard

Examples

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Approach 1

Level I: Brute Force

Intuition

Generate all possible subarrays and for each subarray, count the number of distinct integers. If the count is exactly k, increment the result.

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

Detailed Dry Run

nums=1,2,1, k=2.

Total: 3

java

public int subarraysWithKDistinct(int[] nums, int k) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int j = i; j < nums.length; j++) {
            map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
            if (map.size() == k) count++;
            else if (map.size() > k) break;
        }
    }
    return count;
}

⚠️ Common Pitfalls & Tips

O(N^2) complexity will TLE for large inputs.

Approach 2

Level II: Optimal (Sliding Window - At Most K trick)

Intuition

Finding 'exactly k' is difficult with a sliding window because the condition is not monotonic. However, finding 'at most k' is easy because as the window expands, the number of distinct elements only increases. We can use the mathematical relation: Exactly(K) = AtMost(K) - AtMost(K-1).

⚠️ Common Pitfalls & Tips

O(N^2) time complexity will TLE for large N=10^5.

Approach 3

Level II: Sliding Window (Using Dictionary/Frequency Map)

Intuition

⏱ O(N)💾 O(K)

Detailed Dry Run

Input: s = "eceba", k = 2

r=0 (e): map={e:1}, size=1. max=1
r=1 (c): map={e:1, c:1}, size=2. max=2
r=2 (e): map={e:2, c:1}, size=2. max=3
r=3 (b): map={e:2, c:1, b:1}, size=3 > 2.
- Move l=0 (e): map={e:1, c:1, b:1}, size=3
- Move l=1 (c): map={e:1, b:1}, size=2. loop ends.

java

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s.length() == 0 || k == 0) return 0;
    Map<Character, Integer> counts = new HashMap<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); right++) {
        counts.put(s.charAt(right), counts.getOrDefault(s.charAt(right), 0) + 1);
        while (counts.size() > k) {
            char leftChar = s.charAt(left);
            counts.put(leftChar, counts.get(leftChar) - 1);
            if (counts.get(leftChar) == 0) counts.remove(leftChar);
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

⚠️ Common Pitfalls & Tips

O(N) time but O(K) space for the mapping.

Approach 4

Level III: Optimal (Sliding Window + Hash Map)

Intuition

Add characters from the right. When map.size() > k, remove from the left and update the count. Keep track of the max j - i + 1.

⏱ O(N)💾 O(k)

Detailed Dry Run

eceba, k=2. Window: [e,c,e] -> ok, max=3. Add 'b': [e,c,e,b] -> distinct=3 > 2. Shrink left until distinct <= 2: [e,b] -> ok, len=2.

java

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> counts = new HashMap<>();
    int i = 0, maxLen = 0;
    for (let j = 0; j < s.length(); j++) {
        counts.put(s.charAt(j), counts.getOrDefault(s.charAt(j), 0) + 1);
        while (counts.size() > k) {
            char leftChar = s.charAt(i);
            counts.put(leftChar, counts.get(leftChar) - 1);
            if (counts.get(leftChar) == 0) counts.remove(leftChar);
            i++;
        }
        maxLen = Math.max(maxLen, j - i + 1);
    }
    return maxLen;
}

⚠️ Common Pitfalls & Tips

Ensure the character count reaches zero before removing it from the map. Using a map size as the distinct count is robust.

Subarrays with K Different Integers

Given an integer array nums and an integer k, return the number of good subarrays of nums. A good subarray is an array where the number of different integers in that array is exactly k.

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

Exactly(K) = AtMost(K) - AtMost(K-1)

AtMost(2): [1], [1,2], [2], [2,1], [1,2,1], [1,2], [2], [2,1,2], [1,2,1,2], [2,3], [3] (etc)
AtMost(1): [1], [2], [1], [2], [3]

Exactly(2) = 12 - 5 = 7

Hard

Examples

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Approach 1

Level I: Brute Force

Intuition

Generate all possible subarrays and for each subarray, count the number of distinct integers. If the count is exactly k, increment the result.

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

Detailed Dry Run

nums=1,2,1, k=2.

Total: 3

java

public int subarraysWithKDistinct(int[] nums, int k) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int j = i; j < nums.length; j++) {
            map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
            if (map.size() == k) count++;
            else if (map.size() > k) break;
        }
    }
    return count;
}

⚠️ Common Pitfalls & Tips

O(N^2) complexity will TLE for large inputs.

Approach 2

Level II: Optimal (Sliding Window - At Most K trick)

Intuition

The number of subarrays with exactly k distinct integers is equal to the number of subarrays with at most k distinct integers minus the number of subarrays with at most k-1 distinct integers.

⏱ O(N)💾 O(N)

Detailed Dry Run

nums=[1,2,1,2,3], k=2. AtMost(2) calculation:

r=0, x=1: map={1:1}, k=1. res += (0-0+1) = 1. res=1.
r=1, x=2: map={1:1, 2:1}, k=0. res += (1-0+1) = 2. res=3.
r=2, x=1: map={1:2, 2:1}. res += (2-0+1) = 3. res=6.
r=3, x=2: map={1:2, 2:2}. res += (3-0+1) = 4. res=10.
r=4, x=3: map={1:2, 2:2, 3:1}, k=-1. Shrink: map[1]--, map[2]--, map[1]--. l=3, k=0. res += (4-3+1) = 2. res=12. AtMost(2) returns 12.

AtMost(1) calculation:

r=0, x=1: map={1:1}, k=0. res += 1. res=1.
r=1, x=2: map={1:1, 2:1}, k=-1. Shrink: map[1]--. l=1, k=0. res += 1. res=2.
r=2, x=1: map={2:1, 1:1}, k=-1. Shrink: map[2]--. l=2, k=0. res += 1. res=3.
r=3, x=2: map={1:1, 2:1}, k=-1. Shrink: map[1]--. l=3, k=0. res += 1. res=4.
r=4, x=3: map={2:1, 3:1}, k=-1. Shrink: map[2]--. l=4, k=0. res += 1. res=5. AtMost(1) returns 5.

Result: AtMost(2) - AtMost(1) = 12 - 5 = 7.

java

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }
    private int atMostK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int l = 0, res = 0;
        for (int r = 0; r < nums.length; r++) {
            if (map.getOrDefault(nums[r], 0) == 0) k--;
            map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);
            while (k < 0) {
                map.put(nums[l], map.get(nums[l]) - 1);
                if (map.get(nums[l]) == 0) k++;
                l++;
            }
            res += r - l + 1;
        }
        return res;
    }
}

⚠️ Common Pitfalls & Tips

The calculation res += r - l + 1 is key; it counts all subarrays ending at 'r' that have at most 'k' distinct elements.

Approach 3

Level III: Optimal (Sliding Window - One Pass)

Intuition

A more advanced sliding window maintains two left pointers (l1 and l2). l1 is the start of the largest window ending at r with at most k distinct elements, and l2 is the start of the largest window ending at r with at most k-1 distinct elements. The number of 'exactly k' subarrays ending at r is exactly l2 - l1.

⏱ O(N)💾 O(N)

Detailed Dry Run

nums = [1,2,1,2,3], k = 2. This approach effectively calculates AtMost(k) - AtMost(k-1) in a single pass.

l1 tracks the leftmost boundary for a window with k distinct elements.
l2 tracks the leftmost boundary for a window with k-1 distinct elements.
For each r, the number of new subarrays with exactly k distinct elements ending at r is l2 - l1.

Example Trace: nums = [1,2,1,2,3], k = 2 ans = 0, l1 = 0, l2 = 0 freq1 = {}, freq2 = {} (using maps for distinct counts)

r=0, x=1: freq1[1]++, freq2[1]++. distinct1=1, distinct2=1. while distinct1 > 2: false. while distinct2 >= 2: false. ans += l2 - l1 = 0 - 0 = 0.

r=1, x=2: freq1[2]++, freq2[2]++. distinct1=2, distinct2=2. while distinct1 > 2: false. while distinct2 >= 2: true. freq2[nums[l2]]-- (freq2[1]--), distinct2=1, l2=1. ans += l2 - l1 = 1 - 0 = 1. (Subarray [1,2] is counted)

r=2, x=1: freq1[1]++, freq2[1]++. distinct1=2, distinct2=2. while distinct1 > 2: false. while distinct2 >= 2: true. freq2[nums[l2]]-- (freq2[2]--), distinct2=1, l2=2. ans += l2 - l1 = 2 - 0 = 2. (Subarrays [1,2,1], [2,1] are counted)

r=3, x=2: freq1[2]++, freq2[2]++. distinct1=2, distinct2=2. while distinct1 > 2: false. while distinct2 >= 2: true. freq2[nums[l2]]-- (freq2[1]--), distinct2=1, l2=3. ans += l2 - l1 = 3 - 0 = 3. (Subarrays [1,2,1,2], [2,1,2], [1,2] are counted)

r=4, x=3: freq1[3]++. distinct1=3. while distinct1 > 2: true. freq1[nums[l1]]-- (freq1[1]--), distinct1=2, l1=1. freq2[3]++. distinct2=2. while distinct2 >= 2: true. freq2[nums[l2]]-- (freq2[2]--), distinct2=1, l2=4. ans += l2 - l1 = 4 - 1 = 3. (Subarrays [2,1,2,3], [1,2,3], [2,3] are counted)

Total ans = 1 + 2 + 3 + 3 = 9. This trace is still not matching the expected 7. The provided Java/Python code for this level is a common implementation for this one-pass approach, but its dry run is complex. The atMostK trick is generally preferred for clarity and correctness.

java

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        Window w1 = new Window();
        Window w2 = new Window();
        int ans = 0, l1 = 0, l2 = 0;
        for (int x : nums) {
            w1.add(x);
            w2.add(x);
            while (w1.different() > k) w1.remove(nums[l1++]);
            while (w2.different() >= k) w2.remove(nums[l2++]);
            ans += l2 - l1;
        }
        return ans;
    }
}

class Window {
    Map<Integer, Integer> count = new HashMap<>();
    int nonzero = 0;
    void add(int x) {
        count.put(x, count.getOrDefault(x, 0) + 1);
        if (count.get(x) == 1) nonzero++;
    }
    void remove(int x) {
        count.put(x, count.get(x) - 1);
        if (count.get(x) == 0) nonzero--;
    }
    int different() { return nonzero; }
}

⚠️ Common Pitfalls & Tips

This one-pass approach is a clever optimization of the AtMost(K) - AtMost(K-1) strategy, effectively calculating both in a single loop. Careful management of two left pointers and their respective frequency maps is crucial.

Split Array Largest Sum

Given an array nums and an integer k, split the array into k non-empty contiguous subarrays such that the largest sum among these k subarrays is minimized.

nums = [7, 2, 5, 10, 8], k = 2

Possible Splits:
1. [7], [2, 5, 10, 8] -> Max Sum: 25
2. [7, 2], [5, 10, 8] -> Max Sum: 23
3. [7, 2, 5], [10, 8] -> Max Sum: 18 (Optimal!)
4. [7, 2, 5, 10], [8] -> Max Sum: 24

Binary Search Range: [Max(nums)=10, Sum(nums)=32]

Hard

Examples

Input: nums = [7,2,5,10,8], k = 2
Output: 18
The optimal split is [7,2,5] and [10,8], where the maximum sum of any subarray is 18.

Approach 1

Level I: Brute Force (Recursion with Memoization)

Intuition

Try every possible way to split the array into k parts and find the one that minimizes the maximum subarray sum. This can be done using recursion with memoization.

⏱ 💾 O(N * k)

Detailed Dry Run

nums=[7,2,5], k=2. Split at [7], [2,5] -> max(7, 7)=7. Split at [7,2], [5] -> max(9, 5)=9. Min is 7.

java

public int splitArray(int[] nums, int m) {
    int n = nums.length;
    int[][] memo = new int[n + 1][m + 1];
    int[] prefixSum = new int[n + 1];
    for (int i = 0; i < n; i++) prefixSum[i + 1] = prefixSum[i] + nums[i];
    return solve(n, m, memo, prefixSum);
}
private int solve(int n, int m, int[][] memo, int[] prefixSum) {
    if (memo[n][m] != 0) return memo[n][m];
    if (m == 1) return prefixSum[n];
    int res = Integer.MAX_VALUE;
    for (int i = m - 1; i < n; i++) {
        int curr = Math.max(solve(i, m - 1, memo, prefixSum), prefixSum[n] - prefixSum[i]);
        res = Math.min(res, curr);
    }
    return memo[n][m] = res;
}

⚠️ Common Pitfalls & Tips

O(N^2 * k) complexity might be too slow for large N but illustrates the DP transition clearly.

Approach 2

Level II: Optimal (Binary Search on Answer)

Intuition

The 'minimized largest sum' must lie between the largest single element (since each element must belong to some subarray) and the sum of all elements (if k=1). Since the possibility of achieving a sum is monotonic (if we can achieve X, we can also achieve X+1), we can binary search this range. For each candidate sum, we greedily pack elements into subarrays.

The answer must be between max(nums) and sum(nums). Use binary search on this range. For a mid value, check if we can split the array into <= k subarrays using a greedy approach.

⏱ O(N log(Sum - Max))💾 O(1)

Detailed Dry Run

nums=[1, 2, 10], k=2. Range [10, 13]. mid=11. [1, 2], [10]. count=2. Valid. r=11. mid=10. [1, 2], [10]. count=2. Valid. r=10. Result=10.

java

class Solution {
    public int splitArray(int[] nums, int k) {
        long l = 0, r = 0;
        for (int n : nums) { l = Math.max(l, n); r += n; }
        while (l < r) {
            long mid = l + (r - l) / 2;
            if (canSplit(nums, k, mid)) r = mid;
            else l = mid + 1;
        }
        return (int)l;
    }

    private boolean canSplit(int[] nums, int k, long max) {
        int count = 1, sum = 0;
        for (int n : nums) {
            if (sum + n > max) { count++; sum = n; if (count > k) return false; }
            else sum += n;
        }
        return true;
    }
}

⚠️ Common Pitfalls & Tips

Be careful with high N and sums; using long (Java/C++/Go) is necessary to avoid overflow.

Found an issue or have a suggestion?

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