[LeetCode] 240. Search a 2D Matrix II

Problem

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.

Example 1:

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
Output: true

Example 2:

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
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• -10^9 <= target <= 10^9

---

Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int row = matrix.length - 1; -1 < row; row--)
            for (int col = matrix[0].length - 1; -1 < col; col--) {
                if (matrix[row][col] < target) break;
                else if (matrix[row][col] == target) return true;
            }
        return false;
    }
}
// 오른쪽 하단 모서리 부터 참조?

Explanation

• 배열 matrix 속에 target이 표함되어 있는지를 확인하기 위해 행렬 matrix의 모든 원소를 탐색해야 한다. 마지막 행부터 탐색을 시작하도록 한다.
• 행과 열 모두 오름차순으로 정렬되어 있기 때문에, 한 행에서 target보다 작은 원소를 발견하면 해당 행은 더이상 탐색할 필요가 없으므로 다음을 탐색할 행으로 넘어가도록 한다.
• 탐색 도중 target을 찾으면 true를 반환하고, 모든 탐색을 마친 뒤에도 target을 발견하지 못하면 false를 반환하도록 한다.

  for (int row = matrix.length - 1; -1 < row; row--)
            for (int col = matrix[0].length - 1; -1 < col; col--) {
                if (matrix[row][col] < target) break;
                else if (matrix[row][col] == target) return true;
            }
        return false;