4Sum | LeetCode 18 | Two Pointers

Posted on Edited on In , Views:

šŸ§© Problem Description

Given an integer array nums and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

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

You may return the answer in any order.

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

Constraints:

  • 4 <= nums.length <= 200
  • -10ā¹ <= nums[i] <= 10ā¹
  • -10ā¹ <= target <= 10ā¹

šŸ’” Approach

This is a direct extension of the 3Sum problem.
We use sorting + two pointers:

  1. Sort the array.
  2. Use two nested loops for the first two numbers.
  3. Apply the two-pointer method to find the remaining two numbers.
  4. Skip duplicate values to avoid repeated quadruplets.

šŸ§  Key Insight

After fixing two indices i and j, we need to find two numbers whose sum equals target - nums[i] - nums[j].
This can be efficiently done with a two-pointer scan since the array is sorted.

šŸ§® Complexity

  • Time Complexity: O(nĀ³)
  • Space Complexity: O(1) (excluding output list)

šŸ’» Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates

            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates

                long newTarget = (long)target - nums[i] - nums[j];
                int left = j + 1, right = n - 1;

                while (left < right) {
                    long sum = nums[left] + nums[right];
                    if (sum == newTarget) {
                        res.add(Arrays.asList(nums[i], nums[j], 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 < newTarget) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

šŸ Summary

  • Sort ā†’ Fix two numbers ā†’ Use two pointers for the rest.
  • Handle duplicates carefully.
  • Similar to 3Sum, but one extra layer of iteration.