Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Kth Smallest Element in a Sorted Matrix

Medium
heapbinary-searchmatrix

Each row and each column of an n×n matrix is sorted ascending. Return the k-th smallest element in sorted order (not the k-th distinct value).

Input

  • Line 1: n n — the matrix dimensions
  • Next n lines: the matrix rows
  • Last line: the integer k

Output: the k-th smallest element.

Example 1
Input:
3 3
1 5 9
10 11 13
12 13 15
8
Output:
13

Sorted: 1 5 9 10 11 12 13 13 15 — the 8th is 13.

Example 2
Input:
1 1
-5
1
Output:
-5

Constraints

  • 1 ≤ n ≤ 300
  • -10^9 ≤ values ≤ 10^9
  • 1 ≤ k ≤ n²
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.