Kth Smallest Element in a Sorted Matrix
Find the k-th cheapest ticket in a price grid. matrix is a square grid of ticket prices. Moving right along a row or down a column, a price never drops. Imagine every price in one list from cheapest to dearest, repeats included, and return the k-th price in it, counting from 1. Two tickets with the same price take two places. Limits: matrix is n by n with 1 <= n <= 1200, each price is from -2000000000 to 2000000000, and 1 <= k <= n * n. Think about: halfway between two prices near two billion does not fit in a 32-bit int. Example: matrix = [[2,4,7],[3,6,8],[5,9,9]], k = 8 => 9 cheapest to dearest: 2, 3, 4, 5, 6, 7, 8, 9, 9 The 8th place is a 9, and so is the 9th: both nines count.
You're reading a grid of ticket prices that only goes up along every row and down every column, and you want the k-th cheapest price with repeats counted. Interviewers like it because that double ordering hints at something much faster than sorting everything, and there is more than one way in. The classic traps are counting repeated prices once and an overflow when you take the midpoint of two huge prices. Expect an n by n grid up to 1,200 by 1,200, with prices up to two billion in size.
Examples
You write
kth_smallest_in_sorted_matrix(matrix: List[List[int]], k: int)
Example 1
- Input
- matrix = [[2,4,7],[3,6,8],[5,9,9]], k = 8
- returns
- 9
Example 2
- Input
- matrix = [[5]], k = 1
- returns
- 5
Save this for your laptop
The editor and Run need a bigger screen. The link opens Kth Smallest Element in a Sorted Matrix ready to code. It is free, and the editor needs no account.
The pattern behind it
Binary Search
I reach for it when
- The input is sorted, or sorted and then rotated.
- You want a boundary: the first or last place something is true.
Say this before you type. Say the yes-or-no question, and which side each answer throws away.
All 18 Binary Search problemsHeaps
I reach for it when
- You need the k largest or k smallest items.
- You repeatedly take the best remaining item.
Say this before you type. Say what the heap holds, how big it stays, and what sits on top.
All 22 Heaps problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.