// 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;
}Category: DS & Algo
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;
}GFG PTOD | 17th Dec | Aggressive Cows
bool isPossible(int mid, int k, vector<int> &stalls) {
int count = 1;
int lastPos = stalls[0];
for(int i=1; i < stalls.size(); i++) {
if(stalls[i] - lastPos >= mid) {
count++;
lastPos = stalls[i];
if(count == k) {
return true;
}
}
}
return false;
}
int aggressiveCows(vector<int> &stalls, int k) {
// Write your code here
sort(stalls.begin(), stalls.end());
int low = 1;
int high = stalls.back() - stalls.front();
int res = 0;
while(low <= high) {
int mid = low + (high - low) / 2;
if(isPossible(mid, k, stalls)) {
res = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return res;
}45. Jump Game II (Medium)
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where: 0 <= j <= nums[i] and i + j < n Return the minimum number of jumps to reach nums[n -…
55. Jump Game (Medium)
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Example 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3…