LeetCode 15. Pattern: Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “three sum” or “LeetCode .15”
Approaches
Two-Pointer Approach:
1. Sorting the Array
- The code first sorts the input vector nums to simplify the process of finding triplets.
2. Initialization
- It initializes an empty vector called answer to store the resulting triplets.
3. Handling Edge Case
- If the size of the nums vector is less than 3, the function returns an empty result since it’s impossible to find triplets in this case.
4. Main Loop Over Array
- The code iterates over the elements of the sorted nums array using a for loop.
- If the current element nums[i] is greater than zero, it breaks the loop because there cannot be any triplets that sum to zero when the first element is positive.
5. Duplicate Check
- Inside the loop, it checks if the current element is a duplicate of the previous one (excluding the first element). If it is, the loop continues to the next element to avoid duplicate triplets.
6. Two-Pointer Approach
- The code uses a two-pointer approach to find triplets efficiently.
- It initializes two pointers, low and high, one starting at the next element and the other at the end of the array.
7. Finding Triplets
- It calculates the sum of the current element, nums[low], and nums[high].
- If the sum is greater than zero, it decrements the high pointer.
- If the sum is less than zero, it increments the low pointer.
- When the sum equals zero, it means a triplet is found and adds it to the answer vector.
- It then handles duplicate values by advancing the pointers until they point to unique values.
8. Return the Result
- Once the loop finishes, the function returns the answer vector, which contains all unique triplets that sum to zero in the input array.
Sign Up To Get All Latest Post Notification and DSA Sheets , Javascript Personal Notes , C++ Notes and many more.
My Two Pointer Solution: LeetCode 15
C++ : Two Pointer Approach
class Solution {
public:
std::vector<std::vector<int>> threeSum(std::vector<int> &nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> answer;
if (nums.size() < 3) {
return answer;
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int low = i + 1, high = nums.size() - 1;
while (low < high) {
int sum = nums[i] + nums[low] + nums[high];
if (sum > 0) {
high--;
} else if (sum < 0) {
low++;
} else {
answer.push_back({nums[i], nums[low], nums[high]});
int last_low_occurrence = nums[low], last_high_occurrence = nums[high];
while (low < high && nums[low] == last_low_occurrence) {
low++;
}
while (low < high && nums[high] == last_high_occurrence) {
high--;
}
}
}
}
return answer;
}
};
Java : Two Pointer Approach
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> answer = new ArrayList<>();
if (nums.length < 3) {
return answer;
}
for (int i = 0; i < nums.length; ++i) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int low = i + 1, high = nums.length - 1;
while (low < high) {
int sum = nums[i] + nums[low] + nums[high];
if (sum > 0) {
high--;
} else if (sum < 0) {
low++;
} else {
answer.add(Arrays.asList(nums[i], nums[low], nums[high]));
int lastLowOccurrence = nums[low];
int lastHighOccurrence = nums[high];
while (low < high && nums[low] == lastLowOccurrence) {
low++;
}
while (low < high && nums[high] == lastHighOccurrence) {
high--;
}
}
}
}
return answer;
}
}Python : Two Pointer Approach
class Solution:
def threeSum(self, nums):
nums.sort()
answer = []
if len(nums) < 3:
return answer
for i in range(len(nums)):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
low, high = i + 1, len(nums) - 1
while low < high:
s = nums[i] + nums[low] + nums[high]
if s > 0:
high -= 1
elif s < 0:
low += 1
else:
answer.append([nums[i], nums[low], nums[high]])
lastLowOccurrence, lastHighOccurrence = nums[low], nums[high]
while low < high and nums[low] == lastLowOccurrence:
low += 1
while low < high and nums[high] == lastHighOccurrence:
high -= 1
return answer
JavaScript : Two Pointer Approach
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
nums.sort((a, b) => a - b);
let answer = [];
if (nums.length < 3) {
return answer;
}
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
let low = i + 1;
let high = nums.length - 1;
while (low < high) {
const sum = nums[i] + nums[low] + nums[high];
if (sum > 0) {
high--;
} else if (sum < 0) {
low++;
} else {
answer.push([nums[i], nums[low], nums[high]]);
let lastLowOccurrence = nums[low];
let lastHighOccurrence = nums[high];
while (low < high && nums[low] === lastLowOccurrence) {
low++;
}
while (low < high && nums[high] === lastHighOccurrence) {
high--;
}
}
}
}
return answer;
};
Leet Code 1658. Minimum Operations to Reduce X to Zero (Medium)(Opens in a new browser tab)
HashMap Approach:
- Sorting the Array:
- The code begins by sorting the input array nums in ascending order. This is an essential step for efficient searching of triplets with a sum of zero.
- Base Case Handling:
- If the size of the nums array is less than 3, it means there can’t be a valid triplet sum, so it returns an empty vector as a base case.
- Early Exit for Positive Values:
- Since the array is sorted, if the first element of the sorted array is greater than zero, there can’t be any triplet with a sum of zero. So, it returns an empty vector.
- Hashing Indices:
- An unordered map hashMap is used to store the indices of elements in the nums array. This map is populated with elements as keys and their corresponding indices as values.
- Finding Triplets:
- The code then iterates through the
numsarray to fix the first number of the triplet. It checks if this number is positive, and if so, it breaks the loop as explained earlier. - Inside this loop, another loop is used to fix the second number of the triplet. It calculates the third required number to make the sum zero (required = -1 * (nums[i] + nums[j])).
- It checks if this required number exists in the hashMap and if the last occurrence of this number (the last index) is greater than the index of the second fixed number (
j). If these conditions are met, a valid triplet is found and added to the answer vector. - To avoid duplicate triplets, it updates the index
jto the last occurrence of the second fixed number. - Similarly, it updates the index
ito the last occurrence of the first fixed number to avoid duplicate triplets.
- The code then iterates through the
- Returning the Result:
- Finally, the code returns the answer vector, which contains all the unique triplets that sum to zero.
My HashMap Solution: LeetCode 15
c++ : HashMap Approach:
class Solution {
public: vector < vector < int >> threeSum(vector < int > & nums) {
sort(nums.begin(), nums.end()); //Sorted Array
if (nums.size() < 3) { // Base Case 1
return {};
}
if (nums[0] > 0) { // Base Case 2
return {};
}
unordered_map < int, int > hashMap;
vector < vector < int >> answer;
for (int i = 0; i < nums.size(); ++i) { //Hashing of Indices
hashMap[nums[i]] = i;
}
for (int i = 0; i < nums.size() - 2; ++i) { //Traversing the array to fix the number.
if (nums[i] > 0) { //If number fixed is +ve, stop there because we can't make it zero by searching after it.
break;
}
for (int j = i + 1; j < nums.size() - 1; ++j) { //Fixing another number after first number
int required = -1 * (nums[i] + nums[j]);
//To make sum 0, we would require the -ve sum of both fixed numbers.
if (hashMap.count(required) && hashMap.find(required) -> second > j) {
answer.push_back({
nums[i],
nums[j],
required
});
}
j = hashMap.find(nums[j]) -> second; //Update j to last occurence of 2nd fixed number to avoid duplicate triplets.
}
i = hashMap.find(nums[i]) -> second; //Update i to last occurence of 1st fixed number to avoid duplicate triplets.
}
return answer; //Return answer vector.
}
};Java : HashMap Approach:
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // Sorted Array
List<List<Integer>> answer = new ArrayList<>();
if (nums.length < 3) {
return answer;
}
if (nums[0] > 0) {
return answer;
}
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
hashMap.put(nums[i], i);
}
for (int i = 0; i < nums.length - 2; ++i) {
if (nums[i] > 0) {
break;
}
for (int j = i + 1; j < nums.length - 1; ++j) {
int required = -1 * (nums[i] + nums[j]);
if (hashMap.containsKey(required) && hashMap.get(required) > j) {
answer.add(Arrays.asList(nums[i], nums[j], required));
}
j = hashMap.get(nums[j]);
}
i = hashMap.get(nums[i]);
}
return answer;
}
}
Javascript : HashMap Approach:
var threeSum = function(nums) {
nums.sort((a, b) => a - b); // Sorted Array
let answer = [];
if (nums.length < 3) {
return answer;
}
if (nums[0] > 0) {
return answer;
}
let hashMap = new Map();
for (let i = 0; i < nums.length; ++i) {
hashMap.set(nums[i], i);
}
for (let i = 0; i < nums.length - 2; ++i) {
if (nums[i] > 0) {
break;
}
for (let j = i + 1; j < nums.length - 1; ++j) {
let required = -1 * (nums[i] + nums[j]);
if (hashMap.has(required) && hashMap.get(required) > j) {
answer.push([nums[i], nums[j], required]);
}
j = hashMap.get(nums[j]);
}
i = hashMap.get(nums[i]);
}
return answer;
};
