Find All Triplets with Zero Sum | Hash Maps | MEDIUM

Hey everyone! In today's video, we're diving into an interesting problem titled "Find All Triplets with Zero Sum." This is an easy-level problem, but we’ll explore it in a medium-level way to enhance our understanding. We’ll go through the problem statement, examples, and both brute force and optimized approaches.

Problem Description: Given an array, find all possible triplet indices (i, j, k) such that the sum of the elements at these indices equals zero.
Example Explanation: We’ll analyze an example array to identify valid triplets.
Brute Force Approach: A step-by-step walkthrough of a basic solution using nested loops.
Optimized Approach: Using a hash map for better efficiency.
Code Walkthrough: Complete code implementation to solve the problem.

Timestamps
0:00 - Introduction
0:02 - Overview of the Problem
0:18 - Problem Explanation
1:05 - Example Analysis
2:05 - Brute Force Approach
4:03 - Time Complexity Discussion
5:05 - Optimized Approach
6:19 - Using Hash Maps
7:56 - Example Walkthrough
13:06 - Conclusion and Code Recap

If you find this video helpful, please like, share, and subscribe for more content! Your feedback is valuable, so drop your thoughts in the comments below. I'll also provide the code in the description for you to try out.

// SEO
Find All Triplets with Zero Sum
Find All Triplets with Zero Sum gfg
Find All Triplets with Zero Sum gfg potd
Find All Triplets with Zero Sum gfg potd today
Find All Triplets with Zero Sum geeks for geeks

#coding​​ #helpajobseeker​​ #leetcode #gfg​​ #gfgstreek​​​​ #cpp​​​ #motivation​ #motivation​ #developers​ #codingtools​ #gfg​ #potd​ #linkedlist #gfglearning #explore #leetcodedailychallenge #geek #geeksforgeeks #hashmap #algorithms #logic #logical

[galepraveen]

vector<vector<int>> findTriplets(vector<int> &arr) {
set<vector<int>> resSet;
unordered_map<int, vector<pair<int, int>>> mp;

int n = arr.size();

for(int i = 0; i < n; ++i){
for(int j = i+1; j < n; ++j){
mp[arr[i] + arr[j]].push_back({i, j});
}
}

for (int i = 0; i < n; i++) {
if (mp.count(-arr[i])) {
for (auto &p : mp[-arr[i]]) {
if(p.first == i || p.second == i) continue;

vector<int> curr = {p.first, p.second, i};
sort(begin(curr), end(curr));
resSet.insert(curr);
}
}
}

vector<vector<int> > res(begin(resSet), end(resSet));


return res;
}

[chanchalchauhan]

This code failing for a test case, can you explain why?

vector<vector<int>> findTriplets(vector<int> &arr) {
vector<vector<int>>ans;
int n = arr.size();

for (int i = 0; i < n; i++) {
unordered_map<int, int> m;
for (int j = i+1 ; j < n; j++) {
int third = -(arr[i] + arr[j]);

if (m.find(third) != m.end()) {

vector<int> temp = {i, m[third], j};
sort(temp.begin(), temp.end())
ans.push_back(temp);
}
m[arr[j]] = j;
}
}
return ans;
}