Sponsored
Sponsored
This approach employs sorting the array and fixing two pointers while searching for the other two via a two-pointer method. This reduces the dimensionality of the problem stepwise.
Time Complexity: O(n^3), where n is the number of elements in the array due to three nested loops.
Space Complexity: O(1), excluding the space required for the output storage.
1def fourSum(nums, target):
2 nums.sort()
3 results = []
4 n = len(nums)
5 for i in range(n - 3):
6 if i > 0 and nums[i] == nums[i - 1]:
7 continue
8 for j in range(i + 1, n - 2):
9 if j > i + 1 and nums[j] == nums[j - 1]:
10 continue
11 k, l = j + 1, n - 1
12 while k < l:
13 sum_ = nums[i] + nums[j] + nums[k] + nums[l]
14 if sum_ == target:
15 results.append([nums[i], nums[j], nums[k], nums[l]])
16 while k < l and nums[k] == nums[k + 1]:
17 k += 1
18 while k < l and nums[l] == nums[l - 1]:
19 l -= 1
20 k += 1
21 l -= 1
22 elif sum_ < target:
23 k += 1
24 else:
25 l -= 1
26 return results
27
28# Example usage
29nums = [1, 0, -1, 0, -2, 2]
30target = 0
31result = fourSum(nums, target)
32for r in result:
33 print(r)Python offers a succinct implementation using inbuilt list sorting and dynamic arrays. Two-index approach post looping avoids redundant processing of identical sums and handles all possible quadruplet combinations sequentially to match the target.
This method reduces the four-sum problem by first reducing it to a three-sum problem, and then a two-sum problem using hash maps.
Time Complexity: O(n^2), considering the use of a hash map.
Space Complexity: O(n), for storing intermediate and potential pairs.
1
This solution uses a hash map to store potential pairs and provides an immediate reference to check against the target. Developing all valid pairs without duplicates requires keeping unique property checks on loop iterations.