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;
}Tag: GFG PTOD
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;
}GFG PTOD | 18 Dec | Allocate Minimum Pages
bool isPossible(int k, int mid, const vector<int> &arr) {
int students = 1, curPage = 0;
for(pages : arr) {
if(pages > mid) return false;
if(curPage + pages > mid) {
students++;
curPage = pages;
if(students > k) return false;
} else {
curPage += pages;
}
}
return true;
}
int findPages(vector<int> &arr, int k) {
// code here
if(k > arr.size()) return -1;
int ret = -1;
int low = *max_element(arr.begin(), arr.end()); // max value in array
int high = accumulate(arr.begin(), arr.end(), 0); // sum of all elements in array
while(low <= high) {
int mid = low + (high-low) /2;
if(isPossible(k, mid, arr)) {
ret = mid;
high = mid-1;
} else {
low = mid+1;
}
}
return ret;
}