LeetCode #15 - 3 Sum

Hello fellow LeetCode enthusiasts 👋! Today we are going to discuss one of the popular problems on LeetCode.

Problem Statement

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Constraints:

  • 0 ≤ nums.length ≤ 3000
  • -105nums[i] ≤ 105

Examples

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Analysis

This problem is an extension of the Two Sum problem. Here, the target is zero. Thus, if a + b + c = 0, then a + b = -c. This essentially reduces this problem to Two Sum.

Thus, we have to find such triplets whose sum is zero and there should be no duplicates in the answer.

Approach

The naive approach is to check for each possible triplet. This can be done via three nested loops which will make the time complexity proportional to the third power of the number of elements in the array i.e., O(n3).

Can we do better 🤔? We can use two pointer trick as follows -

  1. Sort the array (in time O(n * log(n))).
  2. Now for each element i, do the following steps
  3. Set two pointers left — j = i + 1 and right — k = nums.length - 1.
  4. Check if nums[i] + nums[j] + nums[k] == 0 and if it is zero, add these three numbers to the resultant list.
  5. If the sum nums[i] + nums[j] + nums[k] < 0, this means we can move left pointer forward because since the array is sorted and the sum is less than zero, therefore, it makes sense to check for greater value to make the sum bigger.
  6. If the sum nums[i] + nums[j] + nums[k] > 0, this means we are too right and can move the right pointer backward because since the array is sorted and the sum is greater than zero, therefore, it makes sense to check for smaller value to make the sum lesser.
  7. In between loops, we also need to make sure that we are not checking for duplicate values.

Time Complexity

We are scanning the entire array keeping one element fixed. We are doing this for every element in the array. Thus, we are scanning each element of array n number of times. And we are doing this for n times, hence the worst case time complexity will be O(n2 + n * log n) which comes down to O(n2).

Space Complexity

We are not using any data structure for the intermediate computations, hence the space complexity is O(1).

Code

Java

public class ThreeSum {

    public List<List<Integer>> threeSum(int[] nums) {
        // Sort the array
        Arrays.sort(nums);
        // Length of the array
        int n = nums.length;
        // Resultant list
        List<List<Integer>> triplets = new ArrayList<>();
        // Loop for each element of the array
        for (int i = 0; i < n; i++) {
            // Skip the duplicates
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // Left and right pointers
            int j = i + 1;
            int k = n - 1;
            // Loop for all the remaining pairs
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    triplets.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    // Never let j refer to the same value twice (in an output) to avoid duplicates
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                } else if (nums[i] + nums[j] + nums[k] < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return triplets;
    }
}

Python

"""
@author - Anirudh Sharma
"""
def threeSum(nums: List[int]) -> List[List[int]]:
    # Sort the given array
    nums.sort()
    # Length of the array
    n = len(nums)
    # Resultant list
    triplets = list()
    # Loop for each character in the array
    for i in range(0, n):
        # Avoid duplicates due to i
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # Left and right pointers
        j = i + 1
        k = n - 1
        # Loop for remaining pairs
        while j < k:
            if nums[i] + nums[j] + nums[k] == 0:
                triplets.append([nums[i], nums[j], nums[k]])
                j += 1
                # Avoid duplicates for j
                while j < k and nums[j] == nums[j - 1]:
                    j += 1
            elif nums[i] + nums[j] + nums[k] < 0:
                j += 1
            else:
                k -= 1
    return triplets

JavaScript

var threeSum = function (nums) {
    // Sort the array
    nums.sort((a, b) => a - b);
    // Length of the array
    const n = nums.length;
    // Resultant list
    const triplets = [];
    // Loop for each element of the array
    for (let i = 0; i < n; i++) {
        // Skip the duplicates
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        // Left and right pointers
        let j = i + 1;
        let k = n - 1;
        // Loop for all the remaining pairs
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] === 0) {
                triplets.push([nums[i], nums[j], nums[k]]);
                j++;
                // Never let j refer to the same value twice (in an output) to avoid duplicates
                while (j < k && nums[j] === nums[j - 1]) {
                    j++;
                }
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                j++;
            } else {
                k--;
            }
        }
    }
    return triplets;
};

Kotlin

fun threeSum(nums: IntArray): List<List<Int>> {
    // Sort the array
    Arrays.sort(nums)
    // Length of the array
    val n = nums.size
    // Resultant list
    val triplets: MutableList<List<Int>> = ArrayList()
    // Loop for each element of the array
    for (i in 0 until n) {
        // Skip the duplicates
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue
        }
        // Left and right pointers
        var j = i + 1
        var k = n - 1
        // Loop for all the remaining pairs
        while (j < k) {
            when {
                nums[i] + nums[j] + nums[k] == 0 -> {
                    triplets.add(listOf(nums[i], nums[j], nums[k]))
                    j++
                    // Never let j refer to the same value twice (in an output) to avoid duplicates
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++
                    }
                }
                nums[i] + nums[j] + nums[k] < 0 -> {
                    j++
                }
                else -> {
                    k--
                }
            }
        }
    }
    return triplets
}

Complete Code

Conclusion

Congratulations 👏! We have solved one more problem from LeetCode.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!


Created and maintained by@Anirudh Sharma
I love to learn and share. Hence, this site has no ads, no affiliation links, or any BS. If you like what you see, give me a thumbs up.

GitHub iconMedium iconTwitter iconFacebook iconLinkedIn iconStackoverflow icon