vector<vector<int>> findTriplets(vector<int> &arr) {
// Code here
// Set to handle duplicates
set<vector<int>> resSet;
int n = arr.size();
unordered_map<int, vector<pair<int, int>>> mp;
// Store sum of all the pairs with their indices
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++) {
// Find remaining value to get zero sum
int rem = -arr[i];
if (mp.find(rem) != mp.end()) {
vector<pair<int, int>> pairs = mp[rem];
for (auto p : pairs) {
// Ensure no two indices are same in triplet
if (p.first != i && p.second != i) {
vector<int> curr = {i, p.first, p.second};
sort(curr.begin(), curr.end());
resSet.insert(curr);
}
}
}
}
vector<vector<int>> res(resSet.begin(), resSet.end());
return res;
}Category: Competitive Programming
GFG PTOD | 27 Dec | Count pairs with given sum
int countPairs(vector<int> &arr, int target) {
// Code here
map<int, int> mp;
int count = 0;
for(int i=0; i<arr.size(); i++) {
if(mp.count(arr[i])){
count += mp.find(arr[i])->second;
}
mp[target - arr[i]]++;
}
return count;
}GFG PTOD | 26 Dec | Two Sum – Pair with Given Sum
bool twoSum(vector<int>& arr, int target) {
// code here
std::set<int> s;
for(int i=0; i<arr.size(); i++) {
if(s.find(arr[i]) != s.end()) {
return true;
} else {
s.insert(target-arr[i]);
}
}
return false;
}Set Matrix Zeroes
void setMatrixZeroes(vector<vector<int>> &mat) {
// code here
int row = mat.size(), col = mat[0].size();
bool isFirstRow = false, isFirstCol = false;
// check 0th row and 0th col, if value is 0
for(int j=0; j<col; j++) {
if(mat[0][j] == 0)
isFirstRow = true;
}
for(int i=0; i<row; i++) {
if(mat[i][0] == 0)
isFirstCol = true;
}
// mark from 1st row and 1st col to nth row and mth col
for(int i=1; i<row; i++) {
for(int j=1; j<col; j++) {
if(mat[i][j] == 0) {
mat[i][0] = 0;
mat[0][j] = 0;
}
}
}
// fill 0 from 1st row and 1st col to nth row and mth col
for(int i=1; i<row; i++) {
for(int j=1; j<col; j++) {
if(mat[i][0] == 0 || mat[0][j] == 0)
mat[i][j] = 0;
}
}
//fill the first row and first col to 0
if(isFirstRow) {
for(int j=0; j<col; j++)
mat[0][j] = 0;
}
if(isFirstCol) {
for(int i=0; i<row; i++)
mat[i][0] = 0;
}
}GFG PTOD | 24 Dec | Search in a sorted Matrix
// Function to search a given number in row-column sorted matrix.
bool searchMatrix(vector<vector<int>> &mat, int x) {
// your code here
int i = 0, j=mat[0].size()-1;
while(i<mat.size() && j>=0) {
if(mat[i][j] == x) return true;
if(mat[i][j] > x) j--;
else i++;
}
return false;
}GFG PTOD | 23 Dec | Search in a row-wise sorted matrix
bool searchRowMatrix(vector<vector<int>> &mat, int x) {
// code here
for(int i = 0; i<mat.size(); i++) {
int low = 0, high = mat[0].size();
while(low<=high) {
int mid = low + (high - low) / 2;
if(mat[i][mid] == x) return true;
if(mat[i][mid] < x)
low = mid+1;
else
high = mid-1;
}
}
return false;
}GFG PTOD | 22 Dec | Search in a Row-Column sorted matrix
bool matSearch(vector<vector<int>> &mat, int x) {
// your code here
int i = 0, j=mat[0].size()-1;
while(i<mat.size() && j>=0) {
if(mat[i][j] == x) return true;
if(mat[i][j] > x) j--;
else i++;
}
return false;
}GFG PTOD | 20 Dec | Rotate by 90 degree
void rotateby90(vector<vector<int>>& mat) {
// code here
int n = mat.size();
// transpose
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
swap(mat[i][j], mat[j][i]);
}
}
//Reverse
for(int i=0; i<n; i++) {
int top = 0, bottom = n-1;
while(top <= bottom) {
swap(mat[top][i], mat[bottom][i]);
top++;
bottom--;
}
}
}GFG PTOD | 20 DEC | spirally-traversing-a-matrix
vector<int> spirallyTraverse(vector<vector<int> > &mat) {
// code here
int row = mat.size(), col = mat[0].size();
int left = 0, top = 0, right = col-1, bottom = row-1, d=0;
vector<int> ans;
while(left <= right && top <= bottom) {
switch(d) {
case 0:
for(int i = left; i<=right; i++)
ans.push_back(mat[top][i]);
top++;
break;
case 1:
for(int i = top; i<=bottom; i++)
ans.push_back(mat[i][right]);
right--;
break;
case 2:
for(int i=right; i>=left; i--)
ans.push_back(mat[bottom][i]);
bottom--;
break;
case 3:
for(int i=bottom; i>=top; i--)
ans.push_back(mat[i][left]);
left++;
break;
}
if(d==3) d=0;
else d++;
}
return ans;
}GFG PTOD | 19 Dec | Kth Missing Positive Number in a Sorted Array
int kthMissing(vector<int> &arr, int k) {
// Your code goes here
int low = 0;
int high = arr.size()-1;
int ans = arr.size() + k;
while(low <= high) {
int mid = low + (high-low) / 2;
if(arr[mid] > mid+k) {
high = mid - 1;
ans = mid + k;
} else {
low = mid+1;
}
}
return ans;
}