DSA Series Day 24 Search a 2D Matrix in Java, Python and Rust

DSA Series Day 24: Search a 2D Matrix in Java, Python and Rust

Search a 2D Matrix is Day 24 of the Tekraze DSA series, and it takes yesterday’s plain binary search and runs it on a grid. In Day 23, Binary Search, we searched a sorted array. Today we use that exact idea on a matrix. Once you see the trick, a grid stops looking scary and starts looking like one long sorted list.

Also Read: Day 23, Binary Search, covers the template we reuse today.

What is the Search a 2D Matrix problem?

You get an m x n integer matrix where every row is sorted from left to right. The first number of each row is bigger than the last number of the row above it. Given a target, return true if it is in the matrix and false otherwise. Your solution must run in O(log(m * n)) time. This is LeetCode problem 74 if you want to submit your own version.

text

Input:  matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
Output: true

Input:  matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13
Output: false

How should you think about Search a 2D Matrix in plain words?

Read the matrix row by row, like lines in a book. Because each row starts where the last one ended, you get 1, 3, 5, 7, 10, 11, 16, 20, 23 and so on, one fully sorted list. So why not pretend it really is one list?

If we can turn a single position into a row and a column, plain binary search does the rest.

Glowing grid of numbers flattening into one sorted row, illustrating Search a 2D Matrix
DSA Series Day 24: Search a 2D Matrix in Java, Python and Rust 7

What does the brute force Search a 2D Matrix approach look like?

Check every cell until you find the target.

python

def search_brute(matrix, target):
    for row in matrix:
        for x in row:
            if x == target:
                return True
    return False

This takes O(m * n) time and O(1) space. It ignores all the sorting we were given, so it is far too slow for the O(log(m * n)) limit.

How do you get the optimal Search a 2D Matrix solution?

Treat the grid as a virtual array of length m * n. Set left = 0 and right = m * n - 1. For any middle index mid, the row is mid / n and the column is mid % n, where n is the number of columns. Compare that cell with the target and drop half the range, exactly like Day 23.

Walkthrough: searching for 13

The virtual array has 12 slots. Mid 5 maps to row 1, column 1, which is 11, so go right. Mid 8 maps to row 2, column 0, which is 23, so go left. Mid 6 is 16, so go left again. Now left is past right, the range is empty and we return false.

Time for Search a 2D Matrix is O(log(m * n)) because the range halves each step. Space is O(1) since we only store a few indexes. Some people binary search the rows first and then the columns. That is O(log m + log n), which is the same thing. If log time still feels fuzzy, our Big O helper post on time and space complexity breaks it down with charts.

DSA Series Day 24: Search a 2D Matrix in Java, Python and Rust 1
DSA Series Day 24: Search a 2D Matrix in Java, Python and Rust 8

Search a 2D Matrix solutions in Java, Python and Rust

Here is the same idea in all three languages. Each one is a few lines longer than plain binary search, and only the lookup line changes. The Java version uses a closed range like the one in the Java Arrays docs examples. Python has a built-in bisect module for 1D lists, but it does not take a 2D index, so we write the loop ourselves.

Search a 2D Matrix in Java

java

public class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int rows = matrix.length, cols = matrix[0].length;
        int left = 0, right = rows * cols - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = matrix[mid / cols][mid % cols];
            if (value == target) return true;
            if (value < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
    public static void main(String[] args) {
        int[][] m = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        check(searchMatrix(m, 3), true);
        check(searchMatrix(m, 13), false);
        check(searchMatrix(m, 1), true);
        check(searchMatrix(m, 60), true);
        check(searchMatrix(m, 0), false);
        check(searchMatrix(m, 99), false);
        check(searchMatrix(new int[][]{{5}}, 5), true);
        check(searchMatrix(new int[][]{{5}}, 4), false);
        check(searchMatrix(new int[][]{{1}, {3}}, 3), true);
        check(searchMatrix(new int[0][0], 1), false);
        System.out.println("All Java tests passed");
    }
    static void check(boolean got, boolean want) {
        if (got != want) throw new AssertionError("got " + got + " want " + want);
    }
}

Search a 2D Matrix in Python

python

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    while left <= right:
        mid = (left + right) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return True
        if value < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

if __name__ == "__main__":
    m = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
    assert search_matrix(m, 3) is True
    assert search_matrix(m, 13) is False
    assert search_matrix(m, 1) is True
    assert search_matrix(m, 60) is True
    assert search_matrix(m, 0) is False
    assert search_matrix(m, 99) is False
    assert search_matrix([[5]], 5) is True
    assert search_matrix([[5]], 4) is False
    assert search_matrix([[1], [3]], 3) is True
    assert search_matrix([], 1) is False
    print("All Python tests passed")

Search a 2D Matrix in Rust

Rust indexes are usize, so the Rust version uses the half open range from Day 23, where right sits one past the end. That way mid - 1 never underflows. The Rust slice docs show the same half open idea behind binary_search.

rust

fn search_matrix(matrix: &[Vec<i32>], target: i32) -> bool {
    if matrix.is_empty() || matrix[0].is_empty() {
        return false;
    }
    let cols = matrix[0].len();
    let (mut left, mut right) = (0usize, matrix.len() * cols);
    while left < right {
        let mid = left + (right - left) / 2;
        let value = matrix[mid / cols][mid % cols];
        if value == target {
            return true;
        } else if value < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    false
}

fn main() {
    let m = vec![vec![1, 3, 5, 7], vec![10, 11, 16, 20], vec![23, 30, 34, 60]];
    assert!(search_matrix(&m, 3));
    assert!(!search_matrix(&m, 13));
    assert!(search_matrix(&m, 1));
    assert!(search_matrix(&m, 60));
    assert!(!search_matrix(&m, 0));
    assert!(!search_matrix(&m, 99));
    assert!(search_matrix(&[vec![5]], 5));
    assert!(!search_matrix(&[vec![5]], 4));
    assert!(search_matrix(&[vec![1], vec![3]], 3));
    assert!(!search_matrix(&[], 1));
    println!("All Rust tests passed");
}

Each program checks hits at the first, last and middle cells, misses below, above and between values, a single cell grid, a single column grid and an empty matrix. The Python version passes all ten checks when I run it.

search-a-2d-matrix-row-major-layout.webp
DSA Series Day 24: Search a 2D Matrix in Java, Python and Rust 9

What are the 6 tips and tricks for an easy Search a 2D Matrix solution?

Spot the pattern. A grid that reads as one sorted sequence row after row is just a sorted array wearing a costume.

Remember the mapping. Row is index / cols and column is index % cols. Always divide by the column count, not the row count.

Reuse your Day 23 template. Do not invent a new loop. Same left, right and mid, only the lookup changes.

Know the cousin problem. Search a 2D Matrix II only sorts rows and columns separately. There you start at the top right corner and step left or down in O(m + n).

Check the edge cases. Empty matrix, empty first row, a single row, a single column and targets outside the minimum and maximum.

Mention both approaches in interviews. Say the two step row then column approach out loud, then explain why the flattened view gives the same complexity with less code.

What are the common Search a 2D Matrix mistakes?

  • Using mid / rows instead of mid / cols for the row index, which breaks on non square grids.
  • Setting right = m * n with a closed range loop, which reads past the last cell.
  • Forgetting to check for an empty matrix before reading matrix[0].length.
  • Using the corner walk from Search a 2D Matrix II here. It works, but it is O(m + n) instead of O(log(m * n)).
  • Copying the grid into a real flat array first, which wastes O(m * n) space.

Where is the Search a 2D Matrix pattern used in the real world?

Flattening a 2D index into 1D is everywhere. Images store pixels in one long buffer and find pixel (row, col) with row * width + col. NumPy arrays use the same row major layout by default. Sorted data split into chunks, like log files or time series shards, can be searched as one range without loading everything.

Frequently asked questions

What is the Search a 2D Matrix problem?
You get a matrix where each row is sorted and each row starts after the previous row ends. You must say whether a target value exists in it in O(log(m * n)) time.

How do you convert a 1D index to a row and column?
For a matrix with n columns, row = index / n and column = index % n. This lets you binary search the matrix as if it were one sorted array.

What is the time complexity of Search a 2D Matrix?
The optimal solution runs in O(log(m * n)) time and O(1) extra space, because each step halves the virtual search range.

How is Search a 2D Matrix II different?
In Matrix II rows and columns are sorted separately, so the grid is not one sorted list. The usual approach starts at the top right corner and moves left or down in O(m + n) time.

Can I binary search rows first and then columns?
Yes. Find the row whose range holds the target, then binary search that row. It runs in O(log m + log n), which equals O(log(m * n)).

Conclusion

Search a 2D Matrix is binary search in a costume. Flatten the index, reuse the Day 23 loop and you are done. Next time Search a 2D Matrix shows up in an interview, you will know the trick. Today, try rewriting it with the row first approach, then compare how many more lines it takes.

Content Protection by DMCA.com
Spread the love
Scroll to Top
×