Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Given a `n x n`

matrix where each of the rows and columns is sorted in ascending order, return the `k`

th smallest element in the matrix.

```
{
"matrix": [
[1, 3, 5],
[2, 3, 6],
[3, 3, 7]
],
"k": 5
}
```

Output:

```
3
```

```
{
"matrix": [
[2, 2],
[2, 3]
],
"k": 3
}
```

Output:

```
2
```

- Return the kth smallest element in the sorted order, not the kth distinct element.
- Find a solution with a memory complexity better than O(
`n`

^{2}).

Constraints:

- 1 <=
`n`

<= 300 - -10
^{5}<= any element of the matrix <= 10^{5} - All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
- 1 <=
`k`

<=`n`

^{2}

```
/*
Asymptotic complexity in terms of the number of rows \`M\`, the number of columns, \`N\` and
highest difference between the numbers in the matrix \`D\`:
* Time: O((M + N) * log(D)).
* Auxiliary space: O(1).
* Total space: O(M * N).
*/
int m, n;
int count_less_or_equal(vector<vector<int>> &matrix, int x) {
int cnt = 0, c = n - 1;
for (int r = 0; r < m; r++) {
while (c >= 0 && matrix[r][c] > x) c--;
cnt += (c + 1);
}
return cnt;
}
int get_kth_smallest(vector<vector<int>> &matrix, int k) {
m = matrix.size(), n = matrix[0].size();
int left = matrix[0][0], right = matrix[m-1][n-1];
int answer = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (count_less_or_equal(matrix, mid) >= k) {
answer = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
return answer;
}
```

We hope that these solutions to kth smallest element in a sorted matrix problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

Given a `n x n`

matrix where each of the rows and columns is sorted in ascending order, return the `k`

th smallest element in the matrix.

```
{
"matrix": [
[1, 3, 5],
[2, 3, 6],
[3, 3, 7]
],
"k": 5
}
```

Output:

```
3
```

```
{
"matrix": [
[2, 2],
[2, 3]
],
"k": 3
}
```

Output:

```
2
```

- Return the kth smallest element in the sorted order, not the kth distinct element.
- Find a solution with a memory complexity better than O(
`n`

^{2}).

Constraints:

- 1 <=
`n`

<= 300 - -10
^{5}<= any element of the matrix <= 10^{5} - All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
- 1 <=
`k`

<=`n`

^{2}

```
/*
Asymptotic complexity in terms of the number of rows \`M\`, the number of columns, \`N\` and
highest difference between the numbers in the matrix \`D\`:
* Time: O((M + N) * log(D)).
* Auxiliary space: O(1).
* Total space: O(M * N).
*/
int m, n;
int count_less_or_equal(vector<vector<int>> &matrix, int x) {
int cnt = 0, c = n - 1;
for (int r = 0; r < m; r++) {
while (c >= 0 && matrix[r][c] > x) c--;
cnt += (c + 1);
}
return cnt;
}
int get_kth_smallest(vector<vector<int>> &matrix, int k) {
m = matrix.size(), n = matrix[0].size();
int left = matrix[0][0], right = matrix[m-1][n-1];
int answer = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (count_less_or_equal(matrix, mid) >= k) {
answer = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
return answer;
}
```

We hope that these solutions to kth smallest element in a sorted matrix problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart