leetcode/
search_a_2d_matrix_ii.rs

1//! # 240. Search a 2D Matrix II
2//!
3//! Medium
4//!
5//! Write an efficient algorithm that searches for a value `target` in an `m x n` integer matrix `matrix`.
6//! This matrix has the following properties:
7//!
8//! Integers in each row are sorted in ascending from left to right.
9//!
10//! ## Examples
11//!
12//! - Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
13//! - Output: true
14//!
15//! - Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
16//! - Output: false
17//!
18//! ## Constraints
19//!
20//! - `m == matrix.length`
21//! - `n == matrix[i].length`
22//! - `1 <= n, m <= 300`
23//! - `-10^9 <= matrix[i][j] <= 10^9`
24//! - All the integers in each row are sorted in ascending order.
25//! - All the integers in each column are sorted in ascending order.
26//! - `-10^9 <= target <= 10^9`
27//! - Integers in each column are sorted in ascending from top to bottom.
28//!
29pub struct Solution;
30
31impl Solution {
32
33    /// O(m + n) time complexity
34    /// O(1) space complexity
35    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
36        let rows = matrix.len();
37        let cols = matrix[0].len();
38
39        let mut i = (rows - 1) as isize;
40        let mut j = 0;
41
42        while i >= 0 && j < cols {
43            let cur = matrix[i as usize][j];
44            if cur == target {
45                return true;
46            } else if target < cur {
47                i -= 1;
48            } else {
49                j += 1;
50            }
51        }
52
53        false
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test() {
63        let cases = vec![
64            (true, 16, vec![
65                vec![ 1,  3,  5,  7],
66                vec![10, 11, 16, 20],
67                vec![23, 30, 34, 50],
68                vec![60, 61, 62, 63],
69            ]),
70            (true, 20, vec![
71                vec![1,   3,   5, 7],
72                vec![10, 11, 16, 20],
73                vec![23, 30, 34, 50],
74                vec![60, 61, 62, 63],
75            ]),
76            (false, 20, vec![
77                vec![ 1,  4,  7, 11, 15],
78                vec![ 2,  5,  8, 12, 19],
79                vec![ 3,  6,  9, 16, 22],
80                vec![10, 13, 14, 17, 24],
81                vec![18, 21, 23, 26, 30]])
82        ];
83
84        for (expect, target, input) in cases {
85            assert_eq!(expect, Solution::search_matrix(input, target));
86        }
87    }
88}
leetcode/search_a_2d_matrix_ii.rs

leetcode/
search_a_2d_matrix_ii.rs
