(Friday) June 24, 2022

# LeetCode Series - Step by Step Explaination to solve 3Sum Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

## Caveats

1. This question can be solved using two/three-pointers.
2. This question emphasizes how to de-duplicate the value from the array.

## Solution

We are going to use three-pointers in this question.

Firstly, use an outer loop to control the first pointer.

``````for (int i = 0; i < nums.length; i++) {
...
}
``````

So we can ensure this outer loop will traverse all the numbers.

Next to implement the inner loop by using two pointers method.

``````for (int i = 0; i < nums.length; i++) {
int left = i + 1;
int right = nums.length - 1;
}
``````

We use `left = i + 1` because I want the pointer to always start after `i` .

Since `nums.length - 1` has been called more than once. I would refactor this and extract it.

``````int length = nums.length;

for (int i = 0; i < length; i++) {
int left = i + 1;
int right = length - 1;
}
``````

Next, we want to ensure the two pointers traverse the array and terminate when `left` and `right` overlap.

``````int length = nums.length;

for (int i = 0; i < length; i++) {
int left = i + 1;
int right = length - 1;

while (left < right) {
...
}
}
``````

Within the `while` loop, we need to check if the current number + left pointer number + right pointer number is equal to 0.

We need to add those numbers into an array if the sum is 0. Therefore, we have to declare a `List` variable named `ans`. I will be using two `Lists` since the return method except for it.

Lastly, return the `ans`.

``````int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();

for (int i = 0; i < length; i++) {
int left = i + 1;
int right = length - 1;

while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {
}
}
}

return ans;
``````

## Moving the left and right pointers

Now we have implemented the logic to add the numbers into the `ans` and return it.

Next, we have to think about moving the left and right pointers.

Suppose the sum equals 0, the left increases by 1, and the right decrease by 1. That’s pretty straightforward.

If the `sum` is greater than 0, we have to reduce the numbers that are the right pointers.

Vice versa if the `sum` is smaller than 0.

``````int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();

for (int i = 0; i < length; i++) {
int left = i + 1;
int right = length - 1;

while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {
right--;
left++;
} else if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
left++;
}
}
}

return ans;
``````

You might aware the `nums[i] + nums[left] + nums[right]` has been used for three times, we need to refactor it again. Keep it as a good coding habit. It will save you a ton of time to debug or create bug.

``````int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();

for (int i = 0; i < length; i++) {
int left = i + 1;
int right = length - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {
right--;
left++;
} else if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
}
}
}

return ans;
``````

## Condition to Break the Outer Loop

As you might notice, we are searching for the number combination that equals 0. This means if the current number is greater than 0, there’s no point for us to continue. So we can break the loop.

``````int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();

for (int i = 0; i < length; i++) {
if (nums[i] > 0)
break;

int left = i + 1;
int right = length - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {
right--;
left++;
} else if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
}
}
}

return ans;
``````

## De-duplicate the number

However, this solution won’t work if there are duplicate numbers.

According to the question, we are not allowed to existing answers to the answer.  Also means, `i != left && i != right && left != right`

We need to implement the logic to detect the duplication numbers. We might notice the input array is not sorted and it is challenging to de-duplicate using two pointers.

We can utilize the `Arrays.sort()` method to sort the array first.

``````Arrays.sort(nums);

int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();

for (int i = 0; i < length; i++) {
if (nums[i] > 0)
break;

int left = i + 1;
int right = length - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {
right--;
left++;
} else if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
}
}
}

return ans;
``````

Then we start to implement the duplication logic.

First, let’s scan through all the number at the outer loop and we will continue the loop if the following number is the same as the current one.

``````Arrays.sort(nums);

int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();

for (int i = 0; i < length; i++) {
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i - 1])
continue;

int left = i + 1;
int right = length - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {
right--;
left++;
} else if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
}
}
}

return ans;
``````

We need to check `i > 0` to equal the `i - 1` is not out of bound.

Next, we need to de-duplicate the number inside the two-pointers loop.

We want to avoid adding the same number to the `ans` again if the following number is the same as the current one that equals 0.

Therefore we need to loop the number until the next following is different from the current one.

``````Arrays.sort(nums);

int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();

for (int i = 0; i < length; i++) {
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i - 1])
continue;

int left = i + 1;
int right = length - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {

while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}

right--;
left++;
} else if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
}
}
}

return ans;
``````

So far we have pretty much implemented the de-duplicate logic.

## Implement Edge Cases

However, we must always have the habit to check the edge case. Sometimes, the edge case provides in the constraints section.  From the constraints, we understand that the length of the `nums` could be 0 and the answer expects us to provide at least three numbers that equal 0.

So, we can add the logic to check if the `nums` is smaller than 3, then return an empty array.

I moved the `Array.sort()` after the logic because I don’t want to waste the compute resource since we are not using it.

### Final Solution

``````int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();

if (nums.length < 3) {
return ans;
}

Arrays.sort(nums);

for (int i = 0; i < length; i++) {
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i - 1])
continue;

int left = i + 1;
int right = length - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {

while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}

right--;
left++;
} else if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
}
}
}

return ans;
``````