Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

3Sum 🧠

LeetCode Link: 3Sum

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 15 - 3Sum

Description: Given an array nums of n integers, find all unique triplets in the array which gives the sum of zero. The solution set must not contain duplicate triplets.

Intuition: To find unique triplets that sum up to zero, we can leverage the two-pointer approach. By sorting the array and iterating through each element, we can convert the problem into finding two numbers that sum up to the negation of the current element.

Approach:

  1. Sort the input array nums in non-decreasing order.
  2. Iterate through each element nums[i] from 0 to n-3 (exclusive):
  • If i > 0 and nums[i] is equal to nums[i-1], skip the current iteration to avoid duplicate triplets.
  • Initialize two pointers, left pointing to the element next to nums[i], and right pointing to the last element of the array.
  • Iterate while left is less than right:
  • Calculate the current sum of the elements nums[i], nums[left], and nums[right].
  • If the sum is equal to zero, add the triplet [nums[i], nums[left], nums[right]] to the result.
  • Increment left and decrement right to search for the next pair of elements.
  • Skip any duplicate values of nums[left] and nums[right] to avoid duplicate triplets.
  • If the sum is less than zero, increment left.
  • If the sum is greater than zero, decrement right.
  1. Return the result, which contains all unique triplets that sum up to zero.

Time Complexity: The time complexity is O(n^2), where n is the number of elements in the input array. Sorting the array takes O(nlogn) time, and iterating through the array with two pointers takes O(n^2) time.

💾 Space Complexity: The space complexity is O(1) as we are using a constant amount of space to store the pointers and the result.

Solutions 💡

Cpp 💻

class Solution {
  public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        vector<vector<int>> result;
        int n = nums.size();
        sort(nums.begin(), nums.end());

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

            int left = i + 1, right = n - 1;

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

                if (sum == 0) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;

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

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

        return result;
    }
};

Python 🐍

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        n = len(nums)

        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]

                if current_sum == 0:
                    result.append([nums[i], nums[left], nums[right]])

                    # Skip duplicates
                    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 current_sum < 0:
                    left += 1
                else:
                    right -= 1

        return result