#18

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

4Sum

The 4Sum problem requires finding all unique quadruplets in an array that sum to a specific target value.

Problem Statement

Given an array of integers, your task is to find all unique quadruplets that sum up to a given target value. A quadruplet is defined by four numbers from the array, and you are to return all such quadruplets in any order. Duplicates should be avoided in the result.

The input will consist of an array with integer elements and a target value. The array may contain positive, negative, or zero values. Constraints apply to the array length, and the values must fall within a specified range, making it necessary to implement an efficient solution to solve within time limits.

Examples

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 details omitted.

Example 2

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

Output: [[2,2,2,2]]

Example details omitted.

Constraints

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

Solution Approach

Sorting and Two-Pointer Approach

Start by sorting the array, which allows you to apply a two-pointer technique effectively. The outer loop iterates over the array, treating the current element as the first element of the quadruplet. For each element, a pair of pointers is used to find matching sums in the remaining part of the array. This approach helps reduce time complexity and ensures uniqueness by skipping duplicate elements during iteration.

Avoiding Duplicates

After sorting, duplicates in the array must be avoided. When a pair of pointers finds a valid sum, it’s crucial to skip duplicate values by advancing the pointers past the duplicates. Additionally, check for duplicated first elements in the outer loop to prevent redundant quadruplets from being counted. This is crucial for ensuring that only unique quadruplets are returned.

Efficient Search

Each iteration in the two-pointer approach reduces the problem size by narrowing the search space. The array is scanned for valid quadruplets by selecting a first element and applying the two-pointer technique to find the remaining three elements. The time complexity of O(n^3) comes from the combination of the outer loop and two-pointer scanning, where n is the array size.

Complexity Analysis

Metric	Value
Time	O(n^{k - 1})
Space	O(n)

The time complexity is O(n^3) due to the triple nested iteration for the first element and the two-pointer scan for the remaining elements. Sorting the array takes O(n log n), but it is overshadowed by the cubic complexity of the searching process. The space complexity is O(n) because of the space used by the sorting algorithm and the result storage.

What Interviewers Usually Probe

Do you know how to handle duplicates effectively while using the two-pointer technique?
Can you explain why sorting is a crucial step in this problem?
Will you ensure that the final result contains only unique quadruplets without redundancy?

Common Pitfalls or Variants

Common pitfalls

Skipping duplicate values: If duplicates are not skipped properly, the algorithm will return repeated quadruplets.
Incorrect pointer movement: Failing to advance the pointers past duplicates after finding a valid quadruplet leads to inefficiency and incorrect results.
Overlooking edge cases: Ensure to handle cases where no quadruplet exists or when the array length is smaller than 4.

Follow-up variants

3Sum: A similar problem, but instead of quadruplets, you find all unique triplets in an array that sum to a target.
5Sum: This extends the 4Sum problem by finding all unique quintuplets that sum to the target value.
Sum of Three Largest/Smallest: Variants where the goal is to find the sum of the three largest or smallest numbers in the array that sum to the target.

FAQ

How do I ensure uniqueness in the 4Sum solution?

Uniqueness is maintained by sorting the array first, then skipping over duplicate elements during the two-pointer scan, both in the outer loop and inner iteration.

What is the time complexity of the 4Sum problem?

The time complexity is O(n^3) due to the triple nested iteration over the array and the two-pointer scanning, which combined leads to cubic complexity.

Why is sorting necessary in the 4Sum solution?

Sorting the array allows the efficient application of the two-pointer technique to find valid quadruplets and helps in skipping duplicates effectively during the scan.

What edge cases should I consider in 4Sum?

Consider edge cases like an array with fewer than four elements, arrays with only one repeated value, and cases where no valid quadruplet exists.

Can this approach be used for other variations like 3Sum?

Yes, the same two-pointer scanning technique can be applied to variations like 3Sum, where you reduce the target sum by removing one element.

terminal

Solution

Solution 1: Sorting + Double Pointers

We notice that the problem requires us to find non-repeating quadruplets. Therefore, we can first sort the array, which makes it easy to skip duplicate elements.

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

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        ans = []
        if n < 4:
            return ans
        nums.sort()
        for i in range(n - 3):
            if i 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
                k, l = j + 1, n - 1
                while k < l:
                    x = nums[i] + nums[j] + nums[k] + nums[l]
                    if x < target:
                        k += 1
                    elif x > target:
                        l -= 1
                    else:
                        ans.append([nums[i], nums[j], nums[k], nums[l]])
                        k, l = k + 1, l - 1
                        while k < l and nums[k] == nums[k - 1]:
                            k += 1
                        while k < l and nums[l] == nums[l + 1]:
                            l -= 1
        return ans

Continue Practicing

#16 3sum closest #15 3sum #75 sort colors