Skills101
← All coding problems

K-th Smallest in a Sorted Matrix

mediumMatrix+20 XPTime limit 2s

In an n × n matrix every row and every column is sorted in non-decreasing order. Find the k-th smallest value among all n² cells (counting repeated values separately: in 1 1 2 the 2nd smallest is 1).

Input:

  • line 1: n k
  • next n lines: n integers each

Output: the k-th smallest value.

Constraints: 1 ≤ n ≤ 300, 1 ≤ k ≤ n², −10⁹ ≤ value ≤ 10⁹.

Think about it: binary search on the answer value, not on positions. For a guess mid, count how many cells are ≤ mid with a staircase walk (start at the top-right of the matrix, O(n) per count). The smallest mid whose count is at least k is the answer. A min-heap that pops k times also works.

Sample input 1

3 8
1 5 9
10 11 13
12 13 15

Sample output 1

13

Sample input 2

2 2
1 2
1 3

Sample output 2

1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.