[Leetcode][240. Search a 2D Matrix II] 5 Approaches: BF, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis

发表于 2022-07-24 更新于 2022-11-16 分类于 Data Structures and Algorithms Waline：阅读次数：本文字数： 6.6k 阅读时长 ≈ 6 分钟

By Long Luo

This article is the solution 5 Approaches: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis of Problem 240. Search a 2D Matrix II.

Here shows 5 Approaches to slove this problem: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis.

Intuition

This problem is like 74. Search a 2D Matrix, we can refer to the solution 6 Approaches: Brute Force, Row Search, Column Search, One Binary Search, 2D Coordinate Axis.

Brute Force

Just scan the $\textit{matrix}$ to find the answer.

public static boolean searchMatrix_bf(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 (matrix[i][col - 1] < target) {
            continue;
        }

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

    return false;
}

Analysis

Time Complexity: $O(mn)$ .
Space Complexity: $O(1)$ .

Binary Search(Row)

Use Binary Search method in each Row to find the answer.

public boolean searchMatrix_bs_row(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 (matrix[i][col - 1] < target) {
            continue;
        }

        if (binarySearchRow(matrix[i], target)) {
            return true;
        }
    }

    return false;
}

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

    return false;
}

Analysis

Time Complexity: $O(min(M,N)(logM+logN))$ .
Space Complexity: $O(1)$ .

Binary Search(Diagonal, Row, Col)

This method is more difficult, we have to Binary Search method in each Diagonal, then each Row and each Column to find the answer.

public static boolean searchMatrix_bs_3d(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;
    }

    int index = diagonalBinarySearch(matrix, target);
    if (matrix[index][index] == target) {
        return true;
    }

    for (int i = 0; i <= index; i++) {
        boolean rowResult = rowBinarySearch(matrix, i, col - 1, target);
        boolean colResult = colBinarySearch(matrix, i, row - 1, target);
        if (rowResult || colResult) {
            return true;
        }
    }

    return false;
}

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

    return Math.min(left, minVal - 1);
}

public static boolean rowBinarySearch(int[][] matrix, int start, int end, int target) {
    int left = start;
    int right = end;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (matrix[start][mid] == target) {
            return true;
        } else if (matrix[start][mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return false;
}

public static boolean colBinarySearch(int[][] matrix, int start, int end, int target) {
    int left = start + 1;
    int right = end;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (matrix[mid][start] == target) {
            return true;
        } else if (matrix[mid][start] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return false;
}

Analysis

Time Complexity: $O(min(M,N)(logM+logN))$ .
Space Complexity: $O(1)$ .

Binary Search(Global)

Consider the $\textit{matrix}$ as a $1-D$ array, and the Binary Search the array.

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;
    }

    return searchMatrixHelper(matrix, 0, 0, col - 1, row - 1, col - 1, row - 1, target);
}

private static boolean searchMatrixHelper(int[][] matrix, int x1, int y1, int x2, int y2, int xMax, int yMax, int target) {
    if (x1 > xMax || y1 > yMax) {
        return false;
    }

    if (x1 == x2 && y1 == y2) {
        return matrix[y1][x1] == target;
    }
    int m1 = (x1 + x2) >>> 1;
    int m2 = (y1 + y2) >>> 1;
    if (matrix[m2][m1] == target) {
        return true;
    }
    if (matrix[m2][m1] < target) {
        // Right Up
        return searchMatrixHelper(matrix, m1 + 1, y1, x2, m2, x2, y2, target) ||
                // Left Down
                searchMatrixHelper(matrix, x1, m2 + 1, m1, y2, x2, y2, target) ||
                // Right Down
                searchMatrixHelper(matrix, m1 + 1, m2 + 1, x2, y2, x2, y2, target);

    } else {
        // Right Up
        return searchMatrixHelper(matrix, m1 + 1, y1, x2, m2, x2, y2, target) ||
                // Left Down
                searchMatrixHelper(matrix, x1, m2 + 1, m1, y2, x2, y2, target) ||
                // Left Up
                searchMatrixHelper(matrix, x1, y1, m1, m2, x2, y2, target);
    }
}

Analysis

Time Complexity: $O(mlogn)$ .
Space Complexity: $O(1)$ .

2D Coord Axis

The $2D$ array increases from left to right and from top to bottom.

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

Therefore, the algorithm is as follows:

From the bottom left corner of the $2D$ array as the origin, take it as a $2D$ coordinate axis;
If the current number is larger than the $\textit{target}$ , moves up;
If the current number is less than the $\textit{target}$ , move right.

public static boolean searchMatrix_coord_left(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;
    }

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

    return false;
}

Analysis

Time Complexity: $O(m + n)$ .
Space Complexity: $O(1)$ .

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. 😉😃💗