# Problem 18. 4Sum
LeetCode Problem Link (opens new window)
Description: Given an array nums containing n integers and a target value target, determine if there are four elements a, b, c, and d in nums such that a + b + c + d is equal to target. Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given an array nums = [1, 0, -1, 0, -2, 2], and target = 0.
The solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
1
2
3
4
5
2
3
4
5
# Thought Process
The 4Sum problem is similar in approach to 0015.3Sum (opens new window) and uses a two-pointer technique. The basic solution involves adding another layer of for loop on top of the 0015.3Sum (opens new window) solution.
However, some details need attention, such as not exiting early from the loop with a condition like nums[k] > target. While in the 3Sum problem you can return early with nums[i] > 0, here target can be any value. For example, with an array of [-4, -3, -2, -1] and target of -10, you cannot skip checking just because -4 > -10. However, you can still perform pruning by transforming the logic to nums[k] > target && (nums[k] >=0 || target >= 0).
The two-pointer solution for 3Sum involves a for loop where num[i] is the fixed value, and within the loop, left and right indices act as pointers to find if nums[i] + nums[left] + nums[right] == 0.
For 4Sum, this technique involves two loops where nums[k] + nums[i] are the fixed values, and similarly, within the nested loops, left and right act as pointers to find scenarios where nums[k] + nums[i] + nums[left] + nums[right] == target. While 3Sum has a time complexity of O(n^2), 4Sum progresses to O(n^3).
The same logic can be extended to solve for five numbers, six numbers, etc., using the same approach.
The two-pointer method for 0015.3Sum (opens new window) efficiently reduces the complexity from O(n^3) to O(n^2), and for 4Sum, it optimizes from O(n^4) to O(n^3).
We previously discussed hash table usages in classic problems like 0454.4Sum II (opens new window), which is comparatively simpler because it requires finding sums across different arrays without worrying about unique quadruplets.
Let's review several problems where the two-pointer technique was utilized:
This technique optimizes time complexity from O(n^2) to O(n) by reducing an order of magnitude, seen in problems like:
Related linked list problems using two-pointer technique:
- 0206.Reverse Linked List (opens new window)
- 0019.Remove Nth Node From End of List (opens new window)
- Intersection of Two Linked Lists (opens new window)
- 0142.Linked List Cycle II (opens new window)
The two-pointer approach has numerous applications in string-related problems, which will be introduced later.
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
// Pruning
if (nums[k] > target && nums[k] >= 0) {
break;
}
// De-duplicate nums[k]
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// Second level pruning
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
// De-duplicate nums[i]
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// Handling overflow
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// De-duplicate nums[left] and nums[right]
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// Once a solution is found, converge both pointers
right--;
left++;
}
}
}
}
return result;
}
};
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
- Time Complexity: O(n^3)
- Space Complexity: O(1)
# Supplement
The second level pruning:
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
1
2
3
2
3
can be optimized to:
if (nums[k] + nums[i] > target && nums[i] >= 0) {
break;
}
1
2
3
2
3
Because if nums[k] + nums[i] > target, and the numbers after nums[i] are all positive, then they will definitely not satisfy the conditions.
But this form of pruning can be a bit convoluted, and understanding the complete code with the implemented pruning should suffice.
# Other Language Versions
# C:
/* qsort */
static int cmp(const void* arg1, const void* arg2) {
int a = *(int *)arg1;
int b = *(int *)arg2;
return (a > b);
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
/* Sort nums array */
qsort(nums, numsSize, sizeof(int), cmp);
int **res = (int **)malloc(sizeof(int *) * 40000);
int index = 0;
/* k */
for (int k = 0; k < numsSize - 3; k++) { /* First level */
/* k pruning */
if ((nums[k] > target) && (nums[k] >= 0)) {
break;
}
/* De-duplicate k */
if ((k > 0) && (nums[k] == nums[k - 1])) {
continue;
}
/* i */
for (int i = k + 1; i < numsSize - 2; i++) { /* Second level */
/* i pruning */
if ((nums[k] + nums[i] > target) && (nums[i] >= 0)) {
break;
}
/* De-duplicate i */
if ((i > (k + 1)) && (nums[i] == nums[i - 1])) {
continue;
}
/* left and right */
int left = i + 1;
int right = numsSize - 1;
while (left < right) {
/* Prevent overflow */
long long val = (long long)nums[k] + nums[i] + nums[left] + nums[right];
if (val > target) {
right--;
} else if (val < target) {
left++;
} else {
int *res_tmp = (int *)malloc(sizeof(int) * 4);
res_tmp[0] = nums[k];
res_tmp[1] = nums[i];
res_tmp[2] = nums[left];
res_tmp[3] = nums[right];
res[index++] = res_tmp;
/* De-duplicate right */
while ((right > left) && (nums[right] == nums[right - 1])) {
right--;
}
/* De-duplicate left */
while ((left < right) && (nums[left] == nums[left + 1])) {
left++;
}
/* Update right and left */
left++, right--;
}
}
}
}
/* Handle return values */
*returnSize = index;
int *column = (int *)malloc(sizeof(int) * index);
for (int i = 0; i < index; i++) {
column[i] = 4;
}
*returnColumnSizes = column;
return res;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# Java:
import java.util.*;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums); // Sort the array
List<List<Integer>> result = new ArrayList<>(); // Result set
for (int k = 0; k < nums.length; k++) {
// Pruning
if (nums[k] > target && nums[k] >= 0) {
break; // This break is equivalent to return result;
}
// De-duplicate nums[k]
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.length; i++) {
// Second level pruning
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break; // Note that this breaks to the outer loop; return result; may miss some cases
}
// De-duplicate nums[i]
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (right > left) {
long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
// De-duplicate nums[left] and nums[right]
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
List<List<Integer>> results = solution.fourSum(nums, target);
for (List<Integer> result : results) {
System.out.println(result);
}
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# Python:
(Version 1) Using Two Pointers
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
result = []
for i in range(n):
if nums[i] > target and nums[i] > 0 and target > 0: # Pruning (can be omitted)
break
if i > 0 and nums[i] == nums[i-1]: # De-duplicate
continue
for j in range(i+1, n):
if nums[i] + nums[j] > target and target > 0: # Pruning (can be omitted)
break
if j > i+1 and nums[j] == nums[j-1]: # De-duplicate
continue
left, right = j+1, n-1
while left < right:
s = nums[i] + nums[j] + nums[left] + nums[right]
if s == target:
result.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif s < target:
left += 1
else:
right -= 1
return result
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
29
30
31
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
29
30
31
(Version 2) Using Dictionary
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
# Create a dictionary to store the frequency of each number in the input list
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
# Create a set to store the final answers, iterate through unique combinations of 4 numbers
ans = set()
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
for k in range(j + 1, len(nums)):
val = target - (nums[i] + nums[j] + nums[k])
if val in freq:
# Ensure no duplicates
count = (nums[i] == val) + (nums[j] == val) + (nums[k] == val)
if freq[val] > count:
ans.add(tuple(sorted([nums[i], nums[j], nums[k], val])))
return [list(x) for x in ans]
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Go:
func fourSum(nums []int, target int) [][]int {
if len(nums) < 4 {
return nil
}
sort.Ints(nums)
var res [][]int
for i := 0; i < len(nums)-3; i++ {
n1 := nums[i]
// if n1 > target { // Cannot write like this, as the target can be negative
// break
// }
if i > 0 && n1 == nums[i-1] { // De-duplicate nums[i]
continue
}
for j := i + 1; j < len(nums)-2; j++ {
n2 := nums[j]
if j > i+1 && n2 == nums[j-1] { // De-duplicate nums[j]
continue
}
l := j + 1
r := len(nums) - 1
for l < r {
n3 := nums[l]
n4 := nums[r]
sum := n1 + n2 + n3 + n4
if sum < target {
l++
} else if sum > target {
r--
} else {
res = append(res, []int{n1, n2, n3, n4})
for l < r && n3 == nums[l+1] { // De-duplicate
l++
}
for l < r && n4 == nums[r-1] { // De-duplicate
r--
}
// Once a solution is found, converge both pointers
r--
l++
}
}
}
}
return res
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# JavaScript:
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
const len = nums.length;
if(len < 4) return [];
nums.sort((a, b) => a - b);
const res = [];
for(let i = 0; i < len - 3; i++) {
// De-duplicate i
if(i > 0 && nums[i] === nums[i - 1]) continue;
for(let j = i + 1; j < len - 2; j++) {
// De-duplicate j
if(j > i + 1 && nums[j] === nums[j - 1]) continue;
let l = j + 1, r = len - 1;
while(l < r) {
const sum = nums[i] + nums[j] + nums[l] + nums[r];
if(sum < target) { l++; continue}
if(sum > target) { r--; continue}
res.push([nums[i], nums[j], nums[l], nums[r]]);
// De-duplicate nums[left] and nums[right]
while(l < r && nums[l] === nums[++l]);
while(l < r && nums[r] === nums[--r]);
}
}
}
return res;
};
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
29
30
31
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
29
30
31
# TypeScript:
function fourSum(nums: number[], target: number): number[][] {
nums.sort((a, b) => a - b);
let first: number = 0,
second: number,
third: number,
fourth: number;
let length: number = nums.length;
let resArr: number[][] = [];
for (; first < length; first++) {
if (first > 0 && nums[first] === nums[first - 1]) {
continue;
}
for (second = first + 1; second < length; second++) {
if ((second - first) > 1 && nums[second] === nums[second - 1]) {
continue;
}
third = second + 1;
fourth = length - 1;
while (third < fourth) {
let total: number = nums[first] + nums[second] + nums[third] + nums[fourth];
if (total === target) {
resArr.push([nums[first], nums[second], nums[third], nums[fourth]]);
third++;
fourth--;
while (nums[third] === nums[third - 1]) third++;
while (nums[fourth] === nums[fourth + 1]) fourth--;
} else if (total < target) {
third++;
} else {
fourth--;
}
}
}
}
return resArr;
};
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
29
30
31
32
33
34
35
36
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
29
30
31
32
33
34
35
36
# PHP:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[][]
*/
function fourSum($nums, $target) {
$res = [];
sort($nums);
for ($i = 0; $i < count($nums); $i++) {
if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
continue;
}
for ($j = $i + 1; $j < count($nums); $j++) {
if ($j > $i + 1 && $nums[$j] == $nums[$j - 1]) {
continue;
}
$left = $j + 1;
$right = count($nums) - 1;
while ($left < $right) {
$sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
if ($sum < $target) {
$left++;
}
else if ($sum > $target) {
$right--;
}
else {
$res[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];
while ($left < $right && $nums[$left] == $nums[$left+1]) $left++;
while ($left < $right && $nums[$right] == $nums[$right-1]) $right--;
$left++;
$right--;
}
}
}
}
return $res;
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
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
29
30
31
32
33
34
35
36
37
38
39
40
# Swift:
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
var res = [[Int]]()
var sorted = nums
sorted.sort()
for k in 0 ..< sorted.count {
// This form of pruning doesn’t work as the target could be negative
// if sorted[k] > target {
// return res
// }
// De-duplicate
if k > 0 && sorted[k] == sorted[k - 1] {
continue
}
let target2 = target - sorted[k]
for i in (k + 1) ..< sorted.count {
if i > (k + 1) && sorted[i] == sorted[i - 1] {
continue
}
var left = i + 1
var right = sorted.count - 1
while left < right {
let sum = sorted[i] + sorted[left] + sorted[right]
if sum < target2 {
left += 1
} else if sum > target2 {
right -= 1
} else {
res.append([sorted[k], sorted[i], sorted[left], sorted[right]])
while left < right && sorted[left] == sorted[left + 1] {
left += 1
}
while left < right && sorted[right] == sorted[right - 1] {
right -= 1
}
// Once a solution is found, converge both pointers
left += 1
right -= 1
}
}
}
}
return res
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# C#:
public class Solution
{
public IList<IList<int>> FourSum(int[] nums, int target)
{
var result = new List<IList<int>>();
Array.Sort(nums);
for (int i = 0; i < nums.Length - 3; i++)
{
int n1 = nums[i];
if (i > 0 && n1 == nums[i - 1])
continue;
for (int j = i + 1; j < nums.Length - 2; j++)
{
int n2 = nums[j];
if (j > i + 1 && n2 == nums[j - 1])
continue;
int left = j + 1;
int right = nums.Length - 1;
while (left < right)
{
int n3 = nums[left];
int n4 = nums[right];
int sum = n1 + n2 + n3 + n4;
if (sum > target)
{
right--;
}
else if (sum < target)
{
left++;
}
else
{
result.Add(new List<int> { n1, n2, n3, n4 });
while (left < right && nums[left] == n3)
{
left++;
}
while (left < right && nums[right] == n4)
{
right--;
}
}
}
}
}
return result;
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# Rust:
use std::cmp::Ordering;
impl Solution {
pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
let mut result: Vec<Vec<i32>> = Vec::new();
let mut nums = nums;
nums.sort();
let len = nums.len();
for k in 0..len {
// Pruning
if nums[k] > target && (nums[k] > 0 || target > 0) { break; }
// De-duplicate
if k > 0 && nums[k] == nums[k - 1] { continue; }
for i in (k + 1)..len {
// Pruning
if nums[k] + nums[i] > target && (nums[k] + nums[i] >= 0 || target >= 0) { break; }
// De-duplicate
if i > k + 1 && nums[i] == nums[i - 1] { continue; }
let (mut left, mut right) = (i + 1, len - 1);
while left < right {
match (nums[k] + nums[i] + nums[left] + nums[right]).cmp(&target){
Ordering::Equal => {
result.push(vec![nums[k], nums[i], nums[left], nums[right]]);
left += 1;
right -= 1;
while left < right && nums[left] == nums[left - 1]{
left += 1;
}
while left < right && nums[right] == nums[right + 1]{
right -= 1;
}
}
Ordering::Less => {
left +=1;
},
Ordering::Greater => {
right -= 1;
}
}
}
}
}
result
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Scala:
object Solution {
// Import packages
import scala.collection.mutable.ListBuffer
import scala.util.control.Breaks.{break, breakable}
def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
val res = ListBuffer[List[Int]]()
val nums_tmp = nums.sorted // Sort first
for (i <- nums_tmp.indices) {
breakable {
if (i > 0 && nums_tmp(i) == nums_tmp(i - 1)) {
break // Skip this loop if value is the same as previous, equivalent to continue
} else {
for (j <- i + 1 until nums_tmp.length) {
breakable {
if (j > i + 1 && nums_tmp(j) == nums_tmp(j - 1)) {
break // Same as above
} else {
// Two-pointer
var (left, right) = (j + 1, nums_tmp.length - 1)
while (left < right) {
var sum = nums_tmp(i) + nums_tmp(j) + nums_tmp(left) + nums_tmp(right)
if (sum == target) {
// If conditions are met, add to the collection
res += List(nums_tmp(i), nums_tmp(j), nums_tmp(left), nums_tmp(right))
while (left < right && nums_tmp(left) == nums_tmp(left + 1)) left += 1
while (left < right && nums_tmp(right) == nums_tmp(right - 1)) right -= 1
left += 1
right -= 1
} else if (sum < target) left += 1
else right -= 1
}
}
}
}
}
}
}
// The final return res should be converted to List, the return keyword can be omitted
res.toList
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
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
29
30
31
32
33
34
35
36
37
38
39
40
41
# Ruby:
def four_sum(nums, target)
# Result set
result = []
nums = nums.sort!
for i in 0..nums.size - 1
return result if i > 0 && nums[i] > target && nums[i] >= 0
# De-duplicate a
next if i > 0 && nums[i] == nums[i - 1]
for j in i + 1..nums.size - 1
break if nums[i] + nums[j] > target && nums[i] + nums[j] >= 0
# De-duplicate b
next if j > i + 1 && nums[j] == nums[j - 1]
left = j + 1
right = nums.size - 1
while left < right
sum = nums[i] + nums[j] + nums[left] + nums[right]
if sum > target
right -= 1
elsif sum < target
left += 1
else
result << [nums[i], nums[j], nums[left], nums[right]]
# De-duplicate c
while left < right && nums[left] == nums[left + 1]
left += 1
end
# De-duplicate d
while left < right && nums[right] == nums[right - 1]
right -= 1
end
right -= 1
left += 1
end
end
end
end
return result
end
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Copyright © 2025 keetcoder