forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsearch_in_sorted_matrix.py
More file actions
46 lines (37 loc) · 1.14 KB
/
search_in_sorted_matrix.py
File metadata and controls
46 lines (37 loc) · 1.14 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Search in Sorted Matrix
Search for a key in a matrix that is sorted row-wise and column-wise
in non-decreasing order. Start from the bottom-left corner and move
up or right depending on the comparison.
Reference: https://leetcode.com/problems/search-a-2d-matrix-ii/
Complexity:
Time: O(m + n)
Space: O(1)
"""
from __future__ import annotations
def search_in_a_sorted_matrix(
mat: list[list[int]], rows: int, cols: int, key: int
) -> bool:
"""Search for a key in a row-wise and column-wise sorted matrix.
Args:
mat: Sorted matrix of size m x n.
rows: Number of rows.
cols: Number of columns.
key: Value to search for.
Returns:
True if the key is found, False otherwise.
Examples:
>>> search_in_a_sorted_matrix([[2, 5, 7], [4, 8, 13], [9, 11, 15]], 3, 3, 13)
True
>>> search_in_a_sorted_matrix([[2, 5, 7], [4, 8, 13], [9, 11, 15]], 3, 3, 6)
False
"""
i, j = rows - 1, 0
while i >= 0 and j < cols:
if key == mat[i][j]:
return True
if key < mat[i][j]:
i -= 1
else:
j += 1
return False