4sum - Leetcode Solution

Problem Statement:

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:

1. 0 <= a, b, c, d < n
2. a, b, c, and d are distinct.
3. nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Solution:

Approach: Sorting + Two-pointer technique

An initial observation is that we need to have an algorithm that is better than the brute force of taking four elements and checking whether their sum is equal to the target.

To optimize the solution, sorting is a great technique. Let us sort the array, and then we can maintain two pointers, one from the left and one from the right. We will start by fixing two initial pointers, leftmost, and the second leftmost. We will further utilize two-pointer technique, and depending on the sum where l point at left, r point at right and we fix these two pointer, we will move either the left or right towards a specific value in the array. We keep repeating the process until all the elements are traversed.

We need four loops to obtain the quadruplets, similar to the brute force approach. The innermost two loops can be replaced by the two-pointer technique, as discussed. The two outermost loops are used for iteration over all the possible pairs (i,j) of lower indices and upper indices for the chosen quadruplet's first and last element, respectively.

Algorithm :

1. Sort the input array nums.
2. Initiate empty list result.
3. For each element within the nums array:
4. If the current value is not equal to the previous value, do the following steps: a. Iterate through each of the remaining array values. b. If the sum of the current value and the next three values are greater than the target, break the loop. c. If the sum of the current value and the last three values is less than the target, continue to the next value in the outermost loop. d. If the current value and the next three values are equal to the target value, add the quadruplet to the result list. e. Begin the two-pointer technique here with the left and right pointer. f. Iterate over the array from the left and right pointer positions toward each other and compare the sum of quadruplets to the target value. i. if the sum is less than the target, update the left pointer. ii. if the sum is greater than the target, update the right pointer. iii. if the sum is equal to the target, add the quadruplet to result list and break the loop.
5. Return the unique quadruplets from the result set.

Time Complexity : O(N^3), where N is the number of elements in the array. The outermost two loops, which iterate over all the possible pairs of lower indices and upper indices for the chosen quadruplet's first and last element, respectively, runs in O(N^2), where as inside them there's a two-pointer technique that runs in the worst-case scenario in O(N). Therefore, the overall time complexity of the algorithm can be expressed as O(N^2 x N), which can be simplified to O(N^3).

Space Complexity : O(N), where N is the number of elements in the array. The space occupied by the result list can grow up to O(N^2) in the worst case (when all the elements in the array are quadruplets that satisfy the given condition), but considering the number of distinct quadruplets will be much smaller than N^2 in the worst case, we can consider space complexity to be O(N).

Example:

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

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

1