# Matrix Search - Amazon Top Interview Questions

### Problem Statement :

```Given a two-dimensional integer matrix, where every row and column is sorted in ascending order, find the kth (0-indexed) smallest number.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in matrix

Example 1

Input
matrix = [
[1, 3, 30],
[2, 3, 31],
[5, 5, 32]
]
k = 4

Output
5

Example 2

Input

matrix = [
[1, 2, 3]
]
k = 0

Output
1

Example 3

Input
matrix = [
,
,

]
k = 2

Output
3```

### Solution :

```                        ```Solution in C++ :

int solve(vector<vector<int>>& A, int k) {
int M = A.size();
int N = A.size();

int t = N * M - k;

int l = 0;
int h = 1e7;

while (l <= h) {
int m = (l + h) >> 1;

int cnt = 0;

for (auto x : A) cnt += x.end() - upper_bound(x.begin(), x.end(), m);

if (cnt < t)
h = m - 1;
else
l = m + 1;
}

return l;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int[][] mat, int k) {
int left = mat;
int right = mat[mat.length - 1][mat.length - 1];
while (left < right) {
int mid = left + (right - left) / 2;
if (possible(mat, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean possible(int[][] mat, int k, int ele) {
int i = 0;
int j = mat.length - 1;
int count = 0;
while (i < mat.length && j >= 0) {
if (mat[i][j] > ele)
j--;
else {
count += (j + 1);
i++;
}
}
return count > k;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, matrix, n):
def possible(x):
# Is the number of elements y with
# y <= x greater than n?
c = len(matrix) - 1
count = 0
for row in matrix:
while c >= 0 and row[c] > x:
c -= 1
count += c + 1
return count > n

lo = matrix
hi = matrix[-1][-1]
while lo < hi:
mi = lo + hi >> 1
if not possible(mi):
lo = mi + 1
else:
hi = mi
return lo```
```

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element