LeetCode 15 Solution & Blind 9 : 3Sum

Problem Statement (LeetCode 15 - 3Sum)

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that:

• i != j, i != k, and j != k
• nums[i] + nums[j] + nums[k] == 0

Notice that the solution set must not contain duplicate triplets.

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: []

---

Optimal Approach: Sorting + Two Pointers

Intuition

1. Sorting: Sort the input array to allow the use of two pointers to avoid checking for duplicate triplets.
2. Iterating with a Fixed Element: Use the first element of the array as the fixed element, and then solve the two-sum problem for the rest of the array using two pointers.
3. Two Pointers Approach: For each fixed element, place two pointers on the remaining part of the array and move them accordingly to find pairs that sum up to the target (0 - nums[i]).

Why This Approach Works

• Efficiency: Sorting ensures that duplicates can be avoided by skipping over identical elements, and the two-pointer approach reduces the problem from O(n^3) to O(n^2).
• Handling Duplicates: After fixing one element, we skip over duplicate elements by checking the current number against the previous one.
• Time Complexity: The time complexity is dominated by the sorting step, making the overall time complexity O(n^2).

---

LeetCode-Compatible C++ Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());  // Sort the array to use two-pointer technique
        
        for (int i = 0; i < nums.size(); ++i) {
            // Skip duplicate elements to avoid repeating triplets
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            int target = -nums[i];  // We need to find two numbers that sum up to -nums[i]
            int left = i + 1, right = nums.size() - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    // Skip duplicates for left and right
                    while (left < right && nums[left] == nums[left + 1]) {
                        ++left;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        --right;
                    }
                    ++left;
                    --right;
                } else if (sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
        
        return result;
    }
};

---

Step-by-Step Explanation of Code

1. Sorting:
   We first sort the input array nums. This helps in using the two-pointer technique efficiently and helps in skipping duplicate elements during the iteration.

2. Iterating through the Array:
   We iterate over the array using index i. For each i, we set the target sum as -nums[i]. Our goal is to find two numbers whose sum equals this target.

3. Two Pointers:
   After fixing the first number, we use two pointers (left and right) to find pairs that sum up to the target. The left pointer starts just after i, and the right pointer starts from the end of the array. We move the pointers towards each other based on whether their sum is less than, greater than, or equal to the target.

4. Skipping Duplicates:

   • To avoid duplicate triplets, we skip duplicate numbers by checking if the current number is the same as the previous one.
   • After finding a valid triplet, we increment left and decrement right, skipping over any duplicate values at those positions.

5. Return Result:
   After processing all elements and finding the triplets, we return the result vector.

---

Dry Run with Example

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

Step 1: Sort the array: [-4, -1, -1, 0, 1, 2]

Step 2: Iterate over each element (i from 0 to 3).

• For i = 0 (element -4):
  • Target = 4
  • left = 1, right = 5: Sum of -1 + 2 = 1 (move left)
  • left = 2, right = 5: Sum of -1 + 2 = 1 (move left)
  • left = 3, right = 5: Sum of 0 + 2 = 2 (move left)
  • No valid triplet found.
• For i = 1 (element -1):
  • Target = 1
  • left = 2, right = 5: Sum of -1 + 2 = 1 (valid triplet [-1, -1, 2])
  • Skip duplicates and continue until left = 3, right = 4.
  • Valid triplet [-1, 0, 1].

Step 3: Final output: [[-1, -1, 2], [-1, 0, 1]]

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Triple Nested Loop)	O(n^3)	O(1)	This approach checks all triplets, which is inefficient for large input arrays.
Sorting + Binary Search	O(n^2 log n)	O(1)	This approach is less efficient due to the extra log n factor introduced by binary search.
Sorting + HashMap	O(n^2)	O(n)	Requires additional space for the HashMap, making it less space-efficient than the two-pointer approach.

---

Why Two-Pointer Approach is the Best

• Time Complexity is O(n^2): Sorting the array takes O(n log n), and the two-pointer technique reduces the need for nested loops.
• Space Complexity is O(1): We don't use any extra data structures (except the result), making this solution space-efficient.
• Avoiding Duplicates: Sorting and skipping duplicates during iteration allows us to avoid duplicate triplets efficiently.

---

Complexity Analysis

• Time Complexity: O(n^2)
  The sorting step takes O(n log n), and the two-pointer approach inside the loop runs in O(n), resulting in a total time complexity of O(n^2).

• Space Complexity: O(1)
  The space complexity is constant, as we only store the result and use a few variables for iteration.

---

Conclusion

✅ Best Approach: Sorting + Two Pointers
✅ Time Complexity: O(n^2)
✅ Space Complexity: O(1)
✅ Optimal Solution for the Problem

Recommended Problems for Practice

1. 4Sum
2. Two Sum II - Input Array Is Sorted
3. Three Sum Smaller

🚀 Master 3Sum with the Two-Pointer Approach!