Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Kth Smallest Element in Sorted Matrix
Bookmark
Input
Example 1 (3x3, k=8)
Example 2 (2x2, k=2)
4x4 matrix (k=5)
5x5 matrix (k=13)
Single element
Custom
matrix
=
[[1,5,9],[10,11,13],[12,13,15]]
,
k
=
8
k =
8
1
5
9
10
11
13
12
13
15
count cells ≤ mid in O(n), then shrink the value range
k =
8
1
5
9
10
11
13
12
13
15
count cells ≤ mid in O(n), then shrink the value range
k =
8
count =
0
/ need 8
1
5
9
10
11
13
12
13
15
r,c = 1,0
binary search on value
mid 8
1
low
15
high
12
>
8
→ move up a row
k =
8
count =
2
/ need 8
1
5
9
10
11
13
12
13
15
r,c = -1,2
binary search on value
mid 8
1
low
15
high
9
>
8
→ move up a row
k =
8
count =
0
/ need 8
1
5
9
10
11
13
12
13
15
r,c = 2,0
binary search on value
mid 12
9
low
15
high
walk from bottom-left, count cells ≤
12
k =
8
count =
5
/ need 8
1
5
9
10
11
13
12
13
15
r,c = 0,2
binary search on value
mid 12
9
low
15
high
13
>
12
→ move up a row
k =
8
1
5
9
10
11
13
12
13
15
binary search on value
mid 14
13
low
15
high
mid = (
13
+
15
) / 2 =
14
k =
8
count =
6
/ need 8
1
5
9
10
11
13
12
13
15
r,c = 1,2
binary search on value
mid 14
13
low
15
high
15
>
14
→ move up a row
k =
8
1
5
9
10
11
13
12
13
15
binary search on value
mid 13
13
low
14
high
mid = (
13
+
14
) / 2 =
13
k =
8
count =
6
/ need 8
1
5
9
10
11
13
12
13
15
r,c = 1,2
binary search on value
mid 13
13
low
14
high
15
>
13
→ move up a row
k =
8
1
5
9
10
11
13
12
13
15
binary search on value
13
low
13
high
8th smallest = 13
algo
master
.
io
Step:
Binary search on the answer's value, not its index
0 / 36
Input
Example 1 (3x3, k=8)
Example 2 (2x2, k=2)
4x4 matrix (k=5)
5x5 matrix (k=13)
Single element
Custom
matrix
=
[[1,5,9],[10,11,13],[12,13,15]]
,
k
=
8
0 / 36
algo
master
.
io
Step:
Binary search on the answer's value, not its index
