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.
1function fourSum(nums, target) {
2 nums.sort((a, b) => a - b);
3 const results = [];
4 const n = nums.length;
5 for (let i = 0; i < n - 3; i++) {
6 if (i > 0 && nums[i] === nums[i - 1]) continue;
7 for (let j = i + 1; j < n - 2; j++) {
8 if (j > i + 1 && nums[j] === nums[j - 1]) continue;
9 let k = j + 1, l = n - 1;
10 while (k < l) {
11 const sum = nums[i] + nums[j] + nums[k] + nums[l];
12 if (sum === target) {
13 results.push([nums[i], nums[j], nums[k], nums[l]]);
14 while (k < l && nums[k] === nums[k + 1]) k++;
15 while (k < l && nums[l] === nums[l - 1]) l--;
16 k++; l--;
17 } else if (sum < target) {
18 k++;
19 } else {
20 l--;
21 }
22 }
23 }
24 }
25 return results;
26}
27
28// Example Usage
29const nums = [1, 0, -1, 0, -2, 2];
30const target = 0;
31console.log(fourSum(nums, target));JavaScript handles the solution efficiently through in-built sorting and Array methods. The two-pointer framework after sorting allows an effective traversal for the problem's solution, avoiding excessive identical checks with conditions.
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.