4Sum

🎯

4Sum

mediumTWO_POINTERAmazonGoogle

Imagine you are a treasure hunter trying to find four unique gems whose combined value matches exactly a target sum, but you only have a list of gem values.

💡 This problem is about finding quadruplets in an array that sum to a target. Beginners often struggle because the naive approach is very slow and handling duplicates correctly is tricky. Understanding how to reduce complexity using sorting and two pointers is key.

📋

Problem Statement

Given an array nums of n integers and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n, a, b, c, and d are distinct indices, and nums[a] + nums[b] + nums[c] + nums[d] == target. The solution set must not contain duplicate quadruplets.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9-10^9 ≤ target ≤ 10^9

💡

Example

Input"nums = [1, 0, -1, 0, -2, 2], target = 0"

Output[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

After sorting, we find all quadruplets that sum to zero without duplicates.

• Empty array → []
• Array with less than 4 elements → []
• All elements are the same and sum matches target → one quadruplet
• No quadruplet sums to target → []

⚠️

Common Mistakes

Not sorting the array before two-pointer approach

Two-pointer technique fails or duplicates are not handled correctly

✅ Always sort the array before applying two pointers

Not skipping duplicates for all four indices

Duplicate quadruplets appear in the output

✅ Add checks to skip duplicates for i, j, left, and right pointers

Using 'if quad not in res' in brute force leading to O(n^5) complexity

Code becomes extremely slow and times out

✅ Use sorting and two pointers or hash sets to avoid duplicates efficiently

Not checking for index overlap in hash map approach

Quadruplets with repeated indices are included, violating problem constraints

✅ Ensure pairs combined do not share any index

Integer overflow when summing four numbers

Incorrect sums leading to wrong results or runtime errors

✅ Use 64-bit integers or cast sums to long/long long before addition

🧠

Brute Force (Four Nested Loops)

💡 Starting with brute force helps understand the problem deeply by exploring all quadruplets, though it is inefficient and impractical for large inputs.

Intuition

Try every combination of four numbers and check if their sum equals the target.

Algorithm

1. Use four nested loops to pick every quadruplet combination.
2. Calculate the sum of the selected four numbers.
3. If the sum equals the target, add the quadruplet to the result list.
4. After checking all combinations, remove duplicates if any.

💡 The challenge is the huge number of combinations and handling duplicates after the fact.

</>

Code

from typing import List

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    n = len(nums)
    res = []
    nums.sort()
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                for l in range(k+1, n):
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quad = [nums[i], nums[j], nums[k], nums[l]]
                        if quad not in res:
                            res.append(quad)
    return res

# Driver code
if __name__ == '__main__':
    print(fourSum([1,0,-1,0,-2,2], 0))

Line Notes

nums.sort()Sorting helps to detect duplicates later and keeps quadruplets ordered.

for i in range(n):First loop picks the first element of the quadruplet.

for j in range(i+1, n):Second loop picks the second element, ensuring unique indices.

if quad not in res:Avoid adding duplicate quadruplets to the result.

import java.util.*;

public class FourSumBrute {
    public static 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; 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 (nums[i] + nums[j] + nums[k] + nums[l] == target) {
                            List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
                            if (!res.contains(quad)) {
                                res.add(quad);
                            }
                        }
                    }
                }
            }
        }
        return res;
    }

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

Line Notes

Arrays.sort(nums);Sorting to help with duplicate detection and ordering.

for (int i = 0; i < n; i++) {Outer loop picks first element index.

if (!res.contains(quad)) {Check to avoid duplicate quadruplets in results.

System.out.println(fourSum(...));Driver code to test the function.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    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 long)nums[i] + nums[j] + nums[k] + nums[l] == target) {
                        vector<int> quad = {nums[i], nums[j], nums[k], nums[l]};
                        if (find(res.begin(), res.end(), quad) == res.end()) {
                            res.push_back(quad);
                        }
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    vector<int> nums = {1,0,-1,0,-2,2};
    vector<vector<int>> result = fourSum(nums, 0);
    for (auto &quad : result) {
        for (int num : quad) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to help with duplicates and ordering.

for (int i = 0; i < n; i++) {First index of quadruplet.

if ((long long)nums[i] + nums[j] + nums[k] + nums[l] == target)Sum check with casting to avoid overflow.

if (find(res.begin(), res.end(), quad) == res.end()) {Avoid duplicate quadruplets in result.

function fourSum(nums, target) {
    nums.sort((a,b) => a - b);
    const res = [];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                for (let l = k + 1; l < n; l++) {
                    if (nums[i] + nums[j] + nums[k] + nums[l] === target) {
                        const quad = [nums[i], nums[j], nums[k], nums[l]];
                        if (!res.some(arr => arr.every((v, idx) => v === quad[idx]))) {
                            res.push(quad);
                        }
                    }
                }
            }
        }
    }
    return res;
}

// Test
console.log(fourSum([1,0,-1,0,-2,2], 0));

Line Notes

nums.sort((a,b) => a - b);Sort to help with duplicate detection and ordering.

for (let i = 0; i < n; i++) {Outer loop picks first element index.

if (nums[i] + nums[j] + nums[k] + nums[l] === target)Check if quadruplet sums to target.

if (!res.some(arr => arr.every((v, idx) => v === quad[idx]))) {Avoid duplicate quadruplets in results.

⏱

Complexity

TimeO(n^4)

SpaceO(k) where k is number of quadruplets found

Four nested loops each iterate up to n, resulting in O(n^4) time. Space depends on output size.

💡 For n=20, this means 20^4 = 160,000 operations, which is borderline but grows too fast for larger n.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Sorting + Two Pointers with Deduplication

💡 Sorting the array and using two pointers reduces complexity drastically. Deduplication is done during iteration to avoid repeated quadruplets.

Intuition

Fix two numbers with nested loops, then use two pointers to find pairs that complete the quadruplet to the target.

Algorithm

1. Sort the array to enable two-pointer technique and easy duplicate skipping.
2. Use two nested loops to fix the first two numbers.
3. For the remaining two numbers, use two pointers (left and right) to find pairs summing to the remaining target.
4. Skip duplicates for all four numbers to ensure unique quadruplets.

💡 The key difficulty is managing duplicates and correctly moving pointers to find all valid quadruplets.

</>

Code

from typing import List

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left, right = j + 1, n - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    res.append([nums[i], nums[j], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return res

# Driver code
if __name__ == '__main__':
    print(fourSum([1,0,-1,0,-2,2], 0))

Line Notes

nums.sort()Sorting enables two-pointer technique and simplifies duplicate handling.

if i > 0 and nums[i] == nums[i - 1]:Skip duplicates for the first fixed number.

while left < right:Two pointers scan the remaining array for pairs summing to target remainder.

while left < right and nums[left] == nums[left - 1]:Skip duplicates for the left pointer after finding a valid quadruplet.

import java.util.*;

public class FourSumTwoPointers {
    public static 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 left = j + 1, right = n - 1;
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }

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

Line Notes

Arrays.sort(nums);Sort array to enable two-pointer scanning and duplicate skipping.

if (i > 0 && nums[i] == nums[i - 1]) continue;Skip duplicates for first fixed number.

while (left < right) {Two-pointer loop to find pairs summing to remainder target.

while (left < right && nums[left] == nums[left - 1]) left++;Skip duplicates for left pointer after valid quadruplet.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    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 left = j + 1, right = n - 1;
            while (left < right) {
                long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    res.push_back({nums[i], nums[j], nums[left], nums[right]});
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return res;
}

int main() {
    vector<int> nums = {1,0,-1,0,-2,2};
    vector<vector<int>> result = fourSum(nums, 0);
    for (auto &quad : result) {
        for (int num : quad) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to enable two-pointer approach and duplicate skipping.

if (i > 0 && nums[i] == nums[i - 1]) continue;Skip duplicate first elements to avoid repeated quadruplets.

while (left < right) {Two-pointer search for pairs summing to remainder target.

while (left < right && nums[left] == nums[left - 1]) left++;Skip duplicates for left pointer after finding quadruplet.

function fourSum(nums, target) {
    nums.sort((a,b) => a - b);
    const res = [];
    const n = nums.length;
    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            let left = j + 1, right = n - 1;
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum === target) {
                    res.push([nums[i], nums[j], nums[left], nums[right]]);
                    left++;
                    right--;
                    while (left < right && nums[left] === nums[left - 1]) left++;
                    while (left < right && nums[right] === nums[right + 1]) right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return res;
}

// Test
console.log(fourSum([1,0,-1,0,-2,2], 0));

Line Notes

nums.sort((a,b) => a - b);Sort array to enable two-pointer technique and duplicate skipping.

if (i > 0 && nums[i] === nums[i - 1]) continue;Skip duplicate first fixed number to avoid repeated quadruplets.

while (left < right) {Two-pointer loop to find pairs summing to remainder target.

while (left < right && nums[left] === nums[left - 1]) left++;Skip duplicates for left pointer after finding quadruplet.

⏱

Complexity

TimeO(n^3)

SpaceO(k) where k is number of quadruplets found

Two nested loops fix two numbers (O(n^2)), and two pointers scan the rest (O(n)), total O(n^3).

💡 For n=100, this means about 1,000,000 operations, which is feasible in interviews.

Interview Verdict: Accepted

This approach balances clarity and efficiency, making it ideal for interviews.

🧠

Hash Map Based Pair Sum + Two Sum

💡 Using a hash map to store pair sums can reduce the problem to finding two pairs that sum to target, but requires careful duplicate handling.

Intuition

Precompute all pairs and their sums, then find two pairs whose sums add to target without overlapping indices.

Algorithm

1. Create a hash map mapping pair sums to list of index pairs.
2. Iterate over all pairs and store their sums in the map.
3. For each sum, check if target - sum exists in the map.
4. Combine pairs from both sums ensuring indices do not overlap and add unique quadruplets.

💡 The main challenge is avoiding index overlap and duplicates while combining pairs.

</>

Code

from typing import List
from collections import defaultdict

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    two_sum_map = defaultdict(list)
    res = set()
    for i in range(n):
        for j in range(i + 1, n):
            two_sum_map[nums[i] + nums[j]].append((i, j))
    for sum1 in two_sum_map:
        sum2 = target - sum1
        if sum2 not in two_sum_map:
            continue
        list1 = two_sum_map[sum1]
        list2 = two_sum_map[sum2]
        for (i, j) in list1:
            for (k, l) in list2:
                if i != k and i != l and j != k and j != l:
                    quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))
                    res.add(quad)
    return [list(quad) for quad in sorted(res)]

# Driver code
if __name__ == '__main__':
    print(fourSum([1,0,-1,0,-2,2], 0))

Line Notes

nums.sort()Sort to keep quadruplets ordered and simplify duplicate handling.

two_sum_map = defaultdict(list)Map sums to pairs of indices for quick lookup.

if i != k and i != l and j != k and j != l:Ensure pairs do not share indices to form valid quadruplets.

res.add(quad)Use a set to avoid duplicate quadruplets.

import java.util.*;

public class FourSumHashMap {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        Map<Integer, List<int[]>> twoSumMap = new HashMap<>();
        Set<List<Integer>> res = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = nums[i] + nums[j];
                twoSumMap.computeIfAbsent(sum, k -> new ArrayList<>()).add(new int[]{i, j});
            }
        }
        for (int sum1 : twoSumMap.keySet()) {
            int sum2 = target - sum1;
            if (!twoSumMap.containsKey(sum2)) continue;
            List<int[]> list1 = twoSumMap.get(sum1);
            List<int[]> list2 = twoSumMap.get(sum2);
            for (int[] pair1 : list1) {
                for (int[] pair2 : list2) {
                    int i = pair1[0], j = pair1[1], k = pair2[0], l = pair2[1];
                    if (i != k && i != l && j != k && j != l) {
                        int[] quadArr = new int[]{nums[i], nums[j], nums[k], nums[l]};
                        Arrays.sort(quadArr);
                        List<Integer> quad = Arrays.asList(quadArr[0], quadArr[1], quadArr[2], quadArr[3]);
                        res.add(quad);
                    }
                }
            }
        }
        List<List<Integer>> result = new ArrayList<>(res);
        result.sort((a,b) -> {
            for (int i = 0; i < 4; i++) {
                if (!a.get(i).equals(b.get(i))) return a.get(i) - b.get(i);
            }
            return 0;
        });
        return result;
    }

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

Line Notes

Arrays.sort(nums);Sort array to keep quadruplets ordered and simplify duplicates.

twoSumMap.computeIfAbsent(sum, k -> new ArrayList<>()).add(new int[]{i, j});Store pairs by their sum for quick lookup.

if (i != k && i != l && j != k && j != l)Ensure pairs do not share indices to form valid quadruplets.

res.add(quad);Use a set to avoid duplicate quadruplets.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>

using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    unordered_map<int, vector<pair<int,int>>> twoSumMap;
    set<vector<int>> res;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            twoSumMap[nums[i] + nums[j]].emplace_back(i, j);
        }
    }
    for (auto& [sum1, list1] : twoSumMap) {
        int sum2 = target - sum1;
        if (twoSumMap.find(sum2) == twoSumMap.end()) continue;
        auto& list2 = twoSumMap[sum2];
        for (auto& p1 : list1) {
            for (auto& p2 : list2) {
                int i = p1.first, j = p1.second, k = p2.first, l = p2.second;
                if (i != k && i != l && j != k && j != l) {
                    vector<int> quad = {nums[i], nums[j], nums[k], nums[l]};
                    sort(quad.begin(), quad.end());
                    res.insert(quad);
                }
            }
        }
    }
    return vector<vector<int>>(res.begin(), res.end());
}

int main() {
    vector<int> nums = {1,0,-1,0,-2,2};
    vector<vector<int>> result = fourSum(nums, 0);
    for (auto &quad : result) {
        for (int num : quad) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to keep quadruplets ordered and simplify duplicates.

twoSumMap[nums[i] + nums[j]].emplace_back(i, j);Store pairs by their sum for quick lookup.

if (i != k && i != l && j != k && j != l)Ensure pairs do not share indices to form valid quadruplets.

res.insert(quad);Use a set to avoid duplicate quadruplets.

function fourSum(nums, target) {
    nums.sort((a,b) => a - b);
    const twoSumMap = new Map();
    const res = new Set();
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const sum = nums[i] + nums[j];
            if (!twoSumMap.has(sum)) twoSumMap.set(sum, []);
            twoSumMap.get(sum).push([i, j]);
        }
    }
    for (let [sum1, list1] of twoSumMap.entries()) {
        const sum2 = target - sum1;
        if (!twoSumMap.has(sum2)) continue;
        const list2 = twoSumMap.get(sum2);
        for (let [i, j] of list1) {
            for (let [k, l] of list2) {
                if (i !== k && i !== l && j !== k && j !== l) {
                    const quad = [nums[i], nums[j], nums[k], nums[l]].sort((a,b) => a - b);
                    res.add(quad.join(','));
                }
            }
        }
    }
    return Array.from(res).map(s => s.split(',').map(Number));
}

// Test
console.log(fourSum([1,0,-1,0,-2,2], 0));

Line Notes

nums.sort((a,b) => a - b);Sort array to keep quadruplets ordered and simplify duplicates.

twoSumMap.get(sum).push([i, j]);Store pairs by their sum for quick lookup.

if (i !== k && i !== l && j !== k && j !== l)Ensure pairs do not share indices to form valid quadruplets.

res.add(quad.join(','));Use a set of strings to avoid duplicate quadruplets.

⏱

Complexity

TimeO(n^2 + k^2) where k is average pairs per sum

SpaceO(n^2) for storing pairs

Computing all pairs is O(n^2), combining pairs can be up to O(n^4) worst but usually less due to pruning.

💡 This approach uses more memory but can be faster for smaller inputs; for large n it may be impractical.

Interview Verdict: Accepted but less practical for large inputs

Good to know as an alternative approach, but space and complexity can explode for large arrays.

📊

All Approaches - One-Glance Tradeoffs

💡 The two-pointer approach is the best balance of clarity and efficiency for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^4)	O(k)	No	Yes	Mention only - never code
2. Sorting + Two Pointers	O(n^3)	O(k)	No	Yes	Code this approach
3. Hash Map Pair Sum	O(n^2 + k^2)	O(n^2)	No	Yes	Mention as alternative, rarely code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the two-pointer approach, and prepare to explain tradeoffs and edge cases.

How to Present

Clarify input size and constraints.Explain brute force approach and its inefficiency.Introduce sorting and two-pointer optimization.Discuss duplicate handling carefully.Mention alternative hash map approach if time permits.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Ability to optimize nested loops, handle duplicates correctly, and implement two-pointer technique efficiently.

Common Follow-ups

• What if we want k-sum instead of 4-sum? → Use recursion with two pointers for 2-sum base case.
• How to handle integer overflow? → Use long/long long or careful casting.

💡 These follow-ups test your ability to generalize and handle edge cases beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Asked to find quadruplets summing to target, 2) Input array can be sorted, 3) Need unique quadruplets, 4) Problem hints at two-pointer or k-sum approach.

Signature Phrases

four numbers sum to targetunique quadrupletssorted arraytwo pointers

NOT This Pattern When

Subset sum or combination sum problems that allow repeated elements or do not require fixed size subsets.

Similar Problems

3Sum - similar but with triplets instead of quadruplets2Sum - base case for k-sum problems3Sum Closest - variation focusing on closest sum

Practice

1. Consider the following code snippet implementing the Dutch National Flag algorithm. Given the input array [2, 0, 1], what is the value of mid after the first swap operation inside the while loop?

easy

A. 3

B. 2

C. 0

D. 1

Solution

1. Step 1: Trace initial pointers and first iteration

   Initially, low=0, mid=0, high=2, nums=[2,0,1]. Since nums[mid]=2, swap nums[mid] and nums[high]: swap nums[0] and nums[2]. Array becomes [1,0,2], high=1, mid remains 0.

2. Step 2: Value of mid after first swap

   After swapping 2 and 1, mid is not incremented and remains 0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   mid does not increment after swapping 2, so mid=0 after first swap [OK]

Hint: mid increments only after swapping 0 [OK]

Common Mistakes:

• Assuming mid increments after swapping 2
• Off-by-one on mid pointer
• Confusing low and mid increments

2. What is the time complexity of the optimal two-pointer solution for the Container With Most Water problem, and why?

medium

A. O(n^2) because each pointer moves multiple times and all pairs are checked.

B. O(n) because each pointer moves inward at most n times, scanning the array once.

C. O(n log n) due to sorting or binary search steps involved.

D. O(1) because only constant space and operations are used.

Solution

1. Step 1: Analyze pointer movements

   Each pointer starts at opposite ends and moves inward only when the shorter line pointer moves, so total moves per pointer ≤ n.

2. Step 2: Count total operations

   Since pointers move inward without revisiting positions, total iterations ≤ n, making time complexity O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer linear scan -> O(n) time [OK]

Hint: Two pointers each move at most n times -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing space complexity with time
• Thinking sorting is required

3. What is the time and space complexity of the optimal two-pointer overwrite approach for moving zeroes to the end of an array of length n?

medium

A. Time: O(n), Space: O(1) because it scans array twice but no extra space

B. Time: O(n^2), Space: O(1) due to nested loops

C. Time: O(n), Space: O(n) because it uses an auxiliary array implicitly

D. Time: O(n log n), Space: O(1) due to sorting involved

Solution

1. Step 1: Identify loops and operations

   The algorithm scans the array twice sequentially: once to overwrite non-zero elements, once to fill zeroes.

2. Step 2: Analyze time and space

   Each loop is O(n), total O(n). No extra arrays or recursion used, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear passes, constant extra space [OK]

Hint: Two linear scans, no nested loops or extra arrays [OK]

Common Mistakes:

• Mistaking two loops as nested (O(n^2))
• Assuming extra space due to overwriting
• Confusing with sorting complexity

4. Suppose now the second array nums2 can contain negative numbers and the first array nums1 has no extra space at the end. Which of the following approaches correctly merges nums2 into nums1 while maintaining sorted order?

hard

A. Create a new array of size m+n, merge nums1 and nums2 into it, then copy back to nums1.

B. Use the two-pointer backward in-place merge as before, ignoring extra space constraints.

C. Sort nums1 and nums2 separately, then concatenate and sort the combined array.

D. Use a two-pointer forward approach merging into nums1 in-place without extra space.

Solution

1. Step 1: Understand constraints

   nums1 has no extra space at the end, so in-place backward merge is impossible.

2. Step 2: Identify correct approach

   Using extra space to merge into a new array and then copying back is necessary to maintain sorted order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Extra space is required when nums1 lacks buffer space [OK]

Hint: No extra space in nums1 means new array needed [OK]

Common Mistakes:

• Trying in-place merge without space
• Sorting combined array wastes time

5. If the problem is changed so that duplicates are allowed at most k times (where k is a positive integer), which modification to the optimal two-pointer approach is correct?

hard

A. Change the condition to compare current element with the element at write_index - k and allow writing if different

B. Use a hash map to count occurrences and rebuild the array with at most k duplicates

C. Keep the original condition comparing with write_index - 2 regardless of k

D. Use nested loops to remove duplicates exceeding k by shifting elements

Solution

1. Step 1: Understand the generalization

   Allowing at most k duplicates means we must check if the current element differs from the element k positions before the write pointer.

2. Step 2: Modify the condition accordingly

   Replace the fixed 2 with k in the condition: write_index < k or nums[read_index] != nums[write_index - k]. This generalizes the approach.

3. Step 3: Avoid inefficient or incorrect methods

   Hash maps or nested loops increase time or space complexity unnecessarily.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Condition generalized to k duplicates ensures correctness and efficiency [OK]

Hint: Replace 2 with k in index offset check [OK]

Common Mistakes:

• Not generalizing condition to k
• Using hash maps increases space
• Nested loops cause O(n²) time