grid47 Exploring patterns and algorithms
Nov 5, 2024
6 min read
Solution to LeetCode 15: 3Sum Problem
Given an integer array nums, find all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of integers nums.
Example: nums = [-2, 0, 2, 1, -1, -3]
Constraints:
• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5
Output: Return a list of all unique triplets such that their sum is zero.
Example: [[-3, 1, 2], [-2, 0, 2]]
Constraints:
• The triplets should be unique and not repeated in any order.
Goal: Find all unique triplets that sum to zero.
Steps:
• Sort the input array.
• Iterate over the array using the first element as the fixed one and use a two-pointer technique for the remaining part of the array.
• Avoid duplicates by skipping the same elements while iterating over the array.
Goal: The array should have at least 3 elements, and each element should be within the range [-10^5, 10^5].
Steps:
• The input array has a length between 3 and 3000.
• Each element of the array is between -10^5 and 10^5.
Assumptions:
• The array contains at least three elements.
• Input: nums = [-2, 0, 2, 1, -1, -3]
• Explanation: The valid triplets are [-3, 1, 2] and [-2, 0, 2], as both sum to zero.
• Input: nums = [0, 2, 3, 1]
• Explanation: No valid triplets exist as no combination sums to zero.
• Input: nums = [-1, 0, 1, -1, 2, 0]
• Explanation: The valid triplets are [-1, 0, 1], [-1, -1, 2], and [0, 0, 0], all of which sum to zero.
Approach: The approach to solving this problem involves sorting the array first and then using a two-pointer technique to find triplets that sum to zero.
Observations:
• Sorting helps in efficiently finding the triplets using the two-pointer technique.
• Duplicates can be avoided by skipping over equal elements while iterating.
• The problem is a variation of the 3-sum problem that can be solved in O(n^2) time.
Steps:
• Sort the array in non-decreasing order.
• Iterate through the array, fixing the first element of the triplet.
• Use two pointers to find the other two elements of the triplet that sum up to zero.
• Skip duplicate elements to avoid repeating triplets.
Empty Inputs:
• The input array will always have at least 3 elements, as stated in the problem constraints.
Large Inputs:
• The solution should efficiently handle up to 3000 elements in the input array.
Special Values:
• The array may contain duplicate elements, which should be handled to ensure unique triplets.
Constraints:
• The solution should avoid adding duplicate triplets.
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i =0; i < nums.size(); i++) {
int target =-nums[i];
int s = i +1;
int e = nums.size() -1;
while(s < e) {
if(nums[s] + nums[e] < target) {
s++;
} elseif (nums[s] + nums[e] > target) {
e--;
} else {
vector<int> res = {nums[i], nums[s], nums[e]};
ans.push_back(res);
while(s < e && nums[s] == res[1]) s++;
while(s < e && res[2] == nums[e]) e--;
}
}
while(i +1< nums.size() && nums[i] == nums[i +1]) i++;
}
return ans;
}
1 : Function Declaration
vector<vector<int>> threeSum(vector<int>& nums) {
Declare the `threeSum` function, which takes a vector of integers `nums` as input and returns a vector of vectors representing the unique triplets.
2 : Variable Initialization
vector<vector<int>> ans;
Initialize an empty vector `ans` to store the triplets.
3 : Sorting Operations
sort(nums.begin(), nums.end());
Sort the `nums` vector in ascending order.
4 : Loop Iteration
for(int i =0; i < nums.size(); i++) {
Start a loop to iterate through each element `nums[i]` in the sorted array.
5 : Variable Initialization
int target =-nums[i];
Calculate the target sum for the remaining two numbers: `target = -nums[i]`.
6 : Variable Initialization
int s = i +1;
Initialize two pointers `s` and `e` to point to the elements after `nums[i]`. `s` will move from the left, and `e` will move from the right.
7 : Variable Initialization
int e = nums.size() -1;
Initialize `e` to point to the last element of the array.
8 : Loop Iteration
while(s < e) {
Start a two-pointer loop to find pairs of numbers that add up to the `target`.
9 : Conditional Check
if(nums[s] + nums[e] < target) {
If the sum of `nums[s]` and `nums[e]` is less than the `target`, move `s` to the right to increase the sum.
10 : Index Update
s++;
Increment `s` to consider the next larger number.
11 : Conditional Check
} elseif (nums[s] + nums[e] > target) {
If the sum of `nums[s]` and `nums[e]` is greater than the `target`, move `e` to the left to decrease the sum.
12 : Index Update
e--;
Decrement `e` to consider the next smaller number.
13 : Conditional Check
} else {
If the sum is equal to the `target`, a triplet is found.
14 : Array Manipulation
vector<int> res = {nums[i], nums[s], nums[e]};
Create a new vector `res` to store the triplet.
15 : Array Manipulation
ans.push_back(res);
Add the triplet `res` to the `ans` vector.
16 : Loop Iteration
while(s < e && nums[s] == res[1]) s++;
Skip duplicate elements at `s` to avoid redundant triplets.
17 : Loop Iteration
while(s < e && res[2] == nums[e]) e--;
Skip duplicate elements at `e` to avoid redundant triplets.
