[LeetCode][74. Search a 2D Matrix] 6 Approaches: Brute Force, Row Search, Column Search, One Binary Search, 2D Coordinate Axis

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 5.6k 阅读时长 ≈ 5 分钟

By Long Luo

This article is the solution 6 Approaches: Brute Force, Row Search, Column Search, One Binary Search, 2D Coordinate Axis of Problem 74. Search a 2D Matrix.

Here are 6 approaches to solve this problem: Brute Force, Binary Search(Row), Binary Search(Column), One Binary Search and \(2D\) Coordinate Axis.

BF(2 Loops)

It’s easy to use \(2\) Loops to traverse the entire matrix to find the target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// BF
public static boolean searchMatrix_bf(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }

    return false;
}

Notice that the first integer of each row is greater than the last integer of the previous row.

We can optimize the code before.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// BF Opt
public static boolean searchMatrix_bf_opt(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
        return false;
    }

    for (int i = 0; i < row; i++) {
        if (target >= matrix[i][0] && target <= matrix[i][col - 1]) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(m \times n)\)
  • Space Complexity: \(O(1)\)

Find Row First, then Column Binary Search

We can scanning the rows of the matrix, If the \(\textit{target}\) is larger than the last element of this row, the target must not be in this row, but only in the lower row of the matrix.

If we find the row which the target may appears, search this row.

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
// Row Scan + Column BinarySearch
public static boolean searchMatrix_bs(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

    int row = matrix.length;
    int col = matrix[0].length;

    if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
        return false;
    }

    for (int i = 0; i < row; i++) {
        if (target >= matrix[i][0] && target <= matrix[i][col - 1]) {
            if (binarySearch(matrix[i], target) != -1) {
                return true;
            }
        }
    }

    return false;
}

public static int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] > target) {
            end = mid - 1;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            return mid;
        }
    }

    return -1;
}

Analysis

  • Time Complexity: \(O(m + logn)\)
  • Space Complexity: \(O(n)\)

2 Binary Search: Row and Column

Using the binary search on the elements of the first column of the matrix, find the last element that is not larger than the \(\textit{target}\), the \(\textit{target}\) may be located in the row.

Search the row where the target was located.

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
public static boolean searchMatrix_two_bs(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
        return false;
    }

    int rowIdx = binarySearchColumn(matrix, target);
    return binarySearchRow(matrix[rowIdx], target);
}

public static int binarySearchColumn(int[][] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (arr[mid][0] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

public static boolean binarySearchRow(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > target) {
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            return true;
        }
    }

    return arr[left] == target;
}

Analysis

  • Time Complexity: \(O(logm + logn)\)
  • Space Complexity: \(O(1)\)

One Binary Search

Merge the current row to the end of the previous row, we can get an ascending array, then we just use binary search algorithm to find the target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 1 Binary Search: from top left to bottom right
public static boolean searchMatrix_one_bs(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
        return false;
    }

    int left = 0;
    int right = row * col - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (matrix[mid / col][mid % col] == target) {
            return true;
        } else if (matrix[mid / col][mid % col] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(log{mn})\)
  • Space Complexity: \(O(1)\)

2D Coordinate Axis

The \(2D\) array increases from left to right and from top to bottom.

  1. Each column, all the numbers above are all smaller than it.
  2. Each row, the right of the number are all larger than it.

Therefore, the algorithm is as follows:

  1. From the bottom left corner of the \(2D\) array as the origin, take it as a \(2D\) coordinate axis;
  2. If the current number is larger than the \(\textit{target}\), moves up;
  3. If the current number is less than the \(\textit{target}\), move right.
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
// 2D Coordinate Axis
public static boolean searchMatrix_2d_axis(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
        return false;
    }

    int i = row - 1;
    int j = 0;

    while (i >= 0 && j < col) {
        int num = matrix[i][j];
        if (num > target) {
            i--;
        } else if (num < target) {
            j++;
        } else if (num == target) {
            return true;
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(m + n)\)
  • Space Complexity: \(O(1)\)

Reshape

It’s easy to reshape to \(1-D\) array in python, then search as a \(1-D\) array.

1
2
3
4
5
import numpy as np
class Solution(object):
    def searchMatrix(self, matrix, target):
        matrix = np.reshape(matrix, [1, -1])
        return target in matrix

Analysis

  • Time Complexity: \(O(mn+log{mn})\)
  • Space Complexity: \(O(mn)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗