algoadvance

Leetcode 15. 3Sum

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.

Note: The solution set must not contain duplicate triplets.

Example:

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

Clarifying Questions

  1. Can the array contain duplicate numbers?
    • Yes, the array can contain duplicate numbers.
  2. What should be returned if no triplets are found?
    • If no triplets are found, return an empty list.
  3. Is the order of the triplets in the output important?
    • No, the order of triplets in the output is not important.
  4. What about the space and time complexity constraints?
    • Optimize for better time complexity; a solution better than O(n^3) is preferred, and keep additional space usage in mind.

Strategy

  1. Sort the Array: Begin by sorting the array. This will simplify the process of avoiding duplicates and using a two-pointer approach.
  2. Iterate with a Fixed Element: Use a variable i to iterate through the array, considering each element as the potential first element of the triplet.
  3. Two-Pointer Approach for Remaining Two Elements: For each fixed element nums[i], use two pointers (left starting from i+1 and right starting from the end of the array) to find pairs whose sum equals -nums[i].
  4. Skip Duplicates: To ensure the uniqueness of triplets, skip over duplicate elements by advancing the pointers past duplicate values.
  5. Collect Valid Triplets: If a valid triplet (nums[i], nums[left], nums[right]) is found, add it to the results and continue adjusting the left and right pointers, skipping any duplicates encountered.

Time Complexity

Thus, the time complexity is O(n^2).

Code

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    
    for (int i = 0; i < n - 2; ++i) {
        // Skip duplicate elements for the first element of the triplet
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1;
        int 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]});
                // Skip duplicate elements for the second and third elements of the triplet
                while (left < right && nums[left] == nums[left + 1]) ++left;
                while (left < right && nums[right] == nums[right - 1]) --right;
                ++left;
                --right;
            } else if (sum < 0) {
                ++left;
            } else {
                --right;
            }
        }
    }
    
    return result;
}

This code implements the strategy described and ensures that all triplets are unique by skipping over duplicates in both the initial iteration and the two-pointer process.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI