4Sum

LeetCode 18 | Difficulty: Medium

Medium

Problem Description

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:

- `0 <= a, b, c, d < n`

- `a`, `b`, `c`, and `d` are **distinct**.

- `nums[a] + nums[b] + nums[c] + nums[d] == target`

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

- `1 <= nums.length <= 200`

- `-10^9 <= nums[i] <= 10^9`

- `-10^9 <= target <= 10^9`

Topics: Array, Two Pointers, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

---

Solutions

Solution 1: C# (Best: 639 ms)

Metric	Value
Runtime	639 ms
Memory	N/A
Date	2017-08-01

Solution

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);   
    return kSum(nums, 0, 4, target);
}

public IList<IList<int>> kSum(int[] nums, int start, int k, int target)
{
    int len = nums.Length;
    IList<IList<int>> res = new List<IList<int>>();
    if (k == 2)
    {
        int left = start, right = len - 1;
        while (left < right)
        {
            int sum = nums[left] + nums[right];
            if (sum == target)
            {
                res.Add((new List<int> { nums[left], nums[right]}));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
            else if (sum < target) left++;
            else right--;
        }
    }
    else
    {
        for (int i = start; i < len-k+1; i++)
        {
            while (i > start && i<len-1 && nums[i] == nums[i - 1]) { i++;};
            var temp = kSum(nums, i+1, k-1, target-nums[i]);
            foreach (var element in temp)
            {
                element.Add(nums[i]);
            }
            foreach (var val in temp)
            {
                res.Add(val);
            }
        }
    }
    
    return res;
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.