Topic 04 of 15
Matrix
A chocolate bar of squares.
A matrix is a grid, like a chocolate bar or a chess board. Every square has a row number and a column number. You walk it in rows, in columns, in spirals, or you use the order of a sorted grid to skip whole rows at once.
What you will be able to do
Row and column walksSpiral orderStaircase searchBinary search on valuesIn place rotation
0/10
Meet the matrix
01 / 04
A grid with 3 rows and 3 columns. Square (1, 2) means row 1, column 2.
- looking now
- done
- path
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Spiral traversal on a MatrixWalk around a grid like a snail shell: across the top, down the right, back along the bottom, up the left, then curl inward.Matrix simulation
- 02Search an element in a matrixFind a number in a grid that grows to the right and grows downward, by starting at the top right corner and walking down a staircase.Staircase search
- 03Find median in a row wise sorted matrixFind the middle number of a grid whose rows are sorted, by guessing a number and counting how many numbers are at most that guess.Binary search on the answer
- 04Find row with maximum no. of 1sIn a grid where every row is some 0s followed by some 1s, find the row with the most 1s by walking a staircase from the top right corner.Staircase search
- 05Print elements in sorted order using row-column wise sorted matrixPrint every number of a grid in sorted order by always taking the smallest front number among the rows, kept in a min heap.Heap of size k
- 06Maximum size rectangleFind the biggest rectangle made only of 1s in a grid, by turning each row into a skyline of towers and measuring it with a stack.Monotonic stack
- 07Find a specific pair in matrixFind the biggest jump from one cell to another cell that is strictly lower and strictly further right, using a table of the biggest number below and to the right.2D dynamic programming
- 08Rotate matrix by 90 degreesTurn a square grid a quarter turn clockwise without a second grid, by flipping it across its diagonal and then reversing every row.In-place matrix transform
- 09Kth smallest element in a row-column wise sorted matrixFind the kth smallest number in a grid sorted along rows and columns, by guessing a value and counting smaller numbers with a staircase walk.Binary search on the answer
- 10Common elements in all rows of a given matrixFind the numbers that show up in every row of a grid, in one pass, with a notebook that counts how many rows in a row each number has survived.Hash map counting