(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) {
            ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
        }
    }
}

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) {
            ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
            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) {
            ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
            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) {
            ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
            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.

3Sum Problem Statement

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) {
            ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
            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) {
            ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
            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) {
            ans.add(Arrays.asList(nums[i], nums[left], nums[right]));

            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.

3Sum Problem Constraints

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) {
            ans.add(Arrays.asList(nums[i], nums[left], nums[right]));

            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;