class Solution { public: vector findTriplets(vector& arr) { int n = arr.size(); vector ans; vector originalArr = arr; // Keep a copy of original array // Sort the array to use two-pointer technique sort(arr.begin(), arr.end()); // Keep track of already used triplets to avoid duplicates set used; for(int i = 0; i < n - 2; i++) { int j = i + 1; int k = n - 1; while(j < k) { int sum = arr[i] + arr[j] + arr[k]; if(sum > 0) { k--; } else if(sum < 0) { j++; } else { // Find original indices for these values vector indices; for(int x = 0; x < n; x++) { if(originalArr[x] == arr[i] || originalArr[x] == arr[j] || originalArr[x] == arr[k]) { indices.push_back(x); if(indices.size() == 3) break; } } sort(indices.begin(), indices.end()); // Sort indices // Only add if this combination hasn't been used if(used.find(indices) == used.end()) { used.insert(indices); ans.push_back(indices); } j++; k--; } } } sort(ans.begin(), ans.end()); // Sort all triplets return ans; } }; like using this not able to pass every test case
I can see some issues in your code like- a) Inefficient handling of original indices : For every triplet found (arr[i], arr[j], arr[k]), the code loops through the entire originalArr to find the indices of the values. This makes the solution inefficient because it introduces an O(n) overhead for each triplet, leading to an overall time complexity of O(n 3), even though the sorted array allows for a more efficient two-pointer technique. b) unnecessary duplicate check with set, c) Index Resolution is Incorrect in Case of Duplicate Values: If the input array contains duplicate values, the logic to find indices in the originalArr will not correctly differentiate between these duplicates. For example: If arr = [1, 2, 2, 3] and a triplet 1, 2, 3 is found, the code may incorrectly pick the first 2 for its index. This can lead to incorrect results, especially when the problem requires distinct indices I hope this helps.
Simple straight forward solution 👍🏻
Keep Coding 😊✌️
class Solution {
public:
vector findTriplets(vector& arr) {
int n = arr.size();
vector ans;
vector originalArr = arr; // Keep a copy of original array
// Sort the array to use two-pointer technique
sort(arr.begin(), arr.end());
// Keep track of already used triplets to avoid duplicates
set used;
for(int i = 0; i < n - 2; i++) {
int j = i + 1;
int k = n - 1;
while(j < k) {
int sum = arr[i] + arr[j] + arr[k];
if(sum > 0) {
k--;
}
else if(sum < 0) {
j++;
}
else {
// Find original indices for these values
vector indices;
for(int x = 0; x < n; x++) {
if(originalArr[x] == arr[i] ||
originalArr[x] == arr[j] ||
originalArr[x] == arr[k]) {
indices.push_back(x);
if(indices.size() == 3) break;
}
}
sort(indices.begin(), indices.end()); // Sort indices
// Only add if this combination hasn't been used
if(used.find(indices) == used.end()) {
used.insert(indices);
ans.push_back(indices);
}
j++;
k--;
}
}
}
sort(ans.begin(), ans.end()); // Sort all triplets
return ans;
}
};
like using this not able to pass every test case
I can see some issues in your code like-
a) Inefficient handling of original indices : For every triplet found (arr[i], arr[j], arr[k]), the code loops through the entire originalArr to find the indices of the values. This makes the solution inefficient because it introduces an
O(n) overhead for each triplet, leading to an overall time complexity of O(n 3), even though the sorted array allows for a more efficient two-pointer technique.
b) unnecessary duplicate check with set,
c) Index Resolution is Incorrect in Case of Duplicate Values:
If the input array contains duplicate values, the logic to find indices in the originalArr will not correctly differentiate between these duplicates. For example:
If arr = [1, 2, 2, 3] and a triplet 1, 2, 3 is found, the code may incorrectly pick the first 2 for its index.
This can lead to incorrect results, especially when the problem requires distinct indices
I hope this helps.
@@letspracticetogether yes thanks a lot 😊
thanks for explanation , but can we solve it by 3 pointers ?
Yes defined we can solve it by using 3 pointers but it will be of O(n^3) time complexity