{x}
blog image

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:

  • 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
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

Solution Explanation: 4Sum

The problem asks to find all unique quadruplets in an array nums that sum up to a given target. The solution employs a strategy that combines sorting and a two-pointer approach for efficient search.

Algorithm:

  1. Sorting: The input array nums is first sorted. This enables efficient skipping of duplicate numbers and allows the use of the two-pointer technique effectively.

  2. Outer Loops: The solution iterates through the array using two nested loops ( i and j). These loops select the first two numbers of the potential quadruplet. Duplicate numbers are skipped to ensure uniqueness in the output.

  3. Two Pointers (Inner Loop): For each pair (nums[i], nums[j]), two pointers, k and l, are initialized to point to the beginning and end of the remaining portion of the array (after j).

  4. Sum and Comparison: The sum x of the four numbers (nums[i], nums[j], nums[k], nums[l]) is calculated.

    • If x < target, the left pointer k is incremented to increase the sum.
    • If x > target, the right pointer l is decremented to decrease the sum.
    • If x == target, a quadruplet is found. It's added to the result ans. The pointers k and l are then adjusted, and duplicate numbers are skipped to maintain the uniqueness of quadruplets.

  5. Duplicate Handling: The inner loop includes checks to skip duplicate numbers at both k and l pointers to prevent duplicate quadruplets from being added to the result.

  6. Return: Finally, the function returns the list ans containing all unique quadruplets that sum to the target.

Time Complexity Analysis:

  • Sorting the array takes O(n log n) time.
  • The three nested loops (outer two and inner two-pointer loop) contribute O(n^3) time complexity. The inner loop's execution time is dominated by the outer loops.
  • Therefore, the overall time complexity is O(n^3).

Space Complexity Analysis:

  • The space complexity is dominated by the space used to store the result ans, which can, in the worst case, store O(n^4) quadruplets (although this is highly unlikely in practice).
  • The sorting step uses logarithmic space in some implementations (e.g., merge sort), which is O(log n).
  • Hence, the overall space complexity is O(n^4) in the worst case (for storing the result) and O(log n) if we don't consider the output space. The output space is usually considered separately in complexity analysis.

Code Examples (Various Languages): The provided solution includes well-commented code in Python, Java, C++, Go, TypeScript, Javascript, C#, and PHP, all implementing the same algorithm described above. Each implementation handles sorting and duplicate checks to ensure the efficiency and correctness of the solution.