// 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: Competitive Programming
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;
}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…
189. Rotate Array (Medium)
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Example 1: Example 2: Solutions 1 : Solutions 2 : Solution 3:
169. Majority Element (Easy)
Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 Solution 1 Solution 2