Search a 2d matrix ii

Array Binary Search Divide and Conquer Matrix

56.9% acceptance

Jan 12, 2026

13066

230

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn search_matrix_ii(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    if matrix.is_empty() || matrix[0].is_empty() {
      return false;
    }
    
    let m = matrix.len();
    let n = matrix[0].len();
    let mut row = 0;
    let mut col = n - 1;
    
    while row < m {
      if matrix[row][col] == target {
        return true;
      } else if matrix[row][col] > target {
        if col == 0 {
          break;
        }
        col -= 1;
      } else {
        row += 1;
      }
    }
    
    false
  }
}