Search an element in a matrix

The problem, simply

You get a grid of numbers, a matrix with m rows and n columns. Every row goes up from left to right. Every column goes up from top to bottom. You also get one number, the target.

Say true if the target is somewhere in the grid, and false if it is not.

There is a stricter version of this grid too, where each row starts after the row above it ends, like the pages of a book. It has its own trick, shown in Way 3.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look at every box on the wall, one by one, until you find the target or run out of boxes.

1. For each row r, and each column c in that row:
2. If matrix[r][c] == target, say true.
3. If the loops end, say false.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int value : row) {
                if (value == target) return true;   // looked at every box until a match
            }
        }
        return false;
    }
}

How long it takes: in the worst case we look at every cell, O(m*n). Extra room: nothing, O(1). It ignores the sorted order completely. A better first step is a binary search in each row, O(m log n), but there is a way that uses both directions at once.

Way 2: the clever way

Stand at the top right corner. From there, moving left always makes the number smaller, and moving down always makes it bigger. So every comparison tells you which way to go.

1. Start at row = 0, col = n - 1.
2. If the number equals the target, say true.
3. If it is bigger than the target, the whole column below is bigger too. Move left: col--.
4. If it is smaller than the target, the whole row to the left is smaller too. Move down: row++.
5. If you walk off the grid, say false.

The grey cells in the animation are the boxes we never had to open.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;

        int m = matrix.length, n = matrix[0].length;
        int row = 0, col = n - 1;            // top right corner

        while (row < m && col >= 0) {
            int here = matrix[row][col];
            if (here == target) return true;
            if (here > target) col--;        // this column is all too big below here
            else row++;                      // this row is all too small left of here
        }
        return false;                        // walked off the grid
    }
}

How long it takes: each step removes one row or one column, and there are only m + n of those, so O(m + n). Extra room: two whole numbers, O(1).

The bottom left corner works too, with the moves flipped: too big means go up, too small means go right. The top left and bottom right corners do not work, because from there both moves go the same way and a comparison cannot pick one.

Way 3: when rows follow each other

Some interviewers mean a stricter grid: each row is sorted, and the first number of a row is bigger than the last number of the row above. Then the whole grid, read row after row, is one long sorted line. You can binary search that line without building it. Seat i of the line lives at matrix[i / n][i % n].

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int here = matrix[mid / n][mid % n];   // seat number to row and column
            if (here == target) return true;
            if (here < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
}

This takes O(log(m*n)) time and O(1) room. It does not work on the grid from Way 2, where a row can start smaller than the row above ends (look at 7 in row 3 of the first example).

Watch out for

• An empty matrix or an empty first row. Check before reading matrix[0].length.
• The loop must check both row < m and col >= 0 before reading a cell.
• Using the Way 3 binary search on a grid that is only sorted by rows and columns. It gives wrong answers.
• In Way 3, m * n can overflow an int for huge grids. Use long for the indexes then.

What interviewers ask next

• Return where the target is, not only true. Return new int[]{row, col} at the match and {-1, -1} at the end.
• Count how many numbers are less than or equal to x. Start at the bottom left. If the number is at most x, the whole column above it counts, so add row + 1 and move right; otherwise move up. This is O(m + n) and is the heart of the Kth smallest problem.
• Can you beat O(m + n) on a row and column sorted grid? Not in general. The cells on the diagonal from bottom left to top right can be in any order relative to each other, so you may need to check all of them.
• What if the grid is huge and wide, like m much smaller than n? Binary search each row, O(m log n), which beats O(m + n) when m is tiny.

Remember this

Grown-up words: the shoe wall is a row and column sorted matrix, the staircase walk is called staircase search or search space reduction, and reading the stricter grid as one long line is binary search over a flattened index.