hardHeap / Priority QueuePure DSA~40 min
Kth Smallest Latency In Sorted Grid
A latency matrix has each row and each column sorted ascending (rows by region, columns by hour). To set an SLA percentile, find the k-th smallest latency across the whole matrix.
Problem
Given an n×n matrix where each row and each column is sorted in ascending order, return the k-th smallest element in the matrix (in sorted order across all elements, counting duplicates).
Input
An n×n matrix (1 ≤ n ≤ 300) and an integer k (1 ≤ k ≤ n²).
Output
An integer: the k-th smallest matrix value.
Constraints
- Each row is sorted ascending; each column is sorted ascending
- 1 ≤ k ≤ n²
- Duplicates count toward k
Examples
Example 1
Input
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output
13
Sorted values: 1,5,9,10,11,12,13,13,15 — the 8th is 13.
Example 2
Input
matrix = [[-5]], k = 1
Output
-5
A single element is trivially the 1st smallest.