Problem Description

Given a 2D matrix matrix where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom, determine whether a given target value exists in the matrix.

• Each row and each column is sorted in increasing order.
• Return true if target is found in the matrix, otherwise return false.
• Do not modify the matrix.

Example:

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
  

Thought Process

At first glance, one might think to search through every element in the matrix to find the target. However, that would be inefficient, especially for large matrices.

Since both rows and columns are sorted, we can leverage this property to eliminate large portions of the matrix at each step. Instead of checking every value, we can make smarter decisions about where to move next based on how the current value compares to the target.

The key is to find a starting point that allows us to eliminate either a row or a column at each step. This is much more efficient than brute-force search.

Solution Approach

We can efficiently search the matrix by starting from the top-right corner (or bottom-left corner). Here’s why:

• At the top-right corner, the number is the largest in its row and the smallest in its column.
• If the current number is greater than target, we can move left (eliminate the current column).
• If the current number is less than target, we move down (eliminate the current row).
• We repeat this process until we either find the target or go out of bounds.

Step-by-step Algorithm:

1. Start at the top-right corner of the matrix (row = 0, col = n-1).
2. While row is within bounds and col is within bounds, repeat:
• If matrix[row][col] == target, return true.
• If matrix[row][col] > target, decrement col (move left).
• If matrix[row][col] < target, increment row (move down).
3. If the loop ends without finding target, return false.

This approach ensures we never visit the same element twice, and at each step, we eliminate either a full row or a full column.

Example Walkthrough

Let’s use the sample 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
  

1. Start at (row=0, col=4): 15. 15 > 5, so move left to col=3.
2. matrix[0][3] = 11. 11 > 5, move left to col=2.
3. matrix[0][2] = 7. 7 > 5, move left to col=1.
4. matrix[0][1] = 4. 4 < 5, move down to row=1.
5. matrix[1][1] = 5. 5 == 5, found the target! Return true.

At each step, we eliminate a row or column, quickly homing in on the target.

Code Implementation

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        row, col = 0, cols - 1
        while row < rows and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        return False
      

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int rows = matrix.size();
        int cols = matrix[0].size();
        int row = 0, col = cols - 1;
        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) return true;
            else if (matrix[row][col] > target) col--;
            else row++;
        }
        return false;
    }
};
      

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int row = 0, col = cols - 1;
        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) return true;
            else if (matrix[row][col] > target) col--;
            else row++;
        }
        return false;
    }
}
      

var searchMatrix = function(matrix, target) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return false;
    let rows = matrix.length;
    let cols = matrix[0].length;
    let row = 0, col = cols - 1;
    while (row < rows && col >= 0) {
        if (matrix[row][col] === target) return true;
        else if (matrix[row][col] > target) col--;
        else row++;
    }
    return false;
};
      

Time and Space Complexity

• Brute-force approach: Checks every element, for m rows and n columns: O(mn) time, O(1) space.
• Optimized approach (this solution):
  • In the worst case, we move at most m + n steps (each step eliminates a row or column).
  • Time Complexity: O(m + n)
  • Space Complexity: O(1) (no extra data structures used)

The optimized approach is efficient and scales well even for large matrices.

Summary

By leveraging the sorted properties of the matrix, we avoid brute-force search and instead use a smart elimination strategy, starting from the top-right corner. At every step, we make a decision that removes an entire row or column from consideration, ensuring optimal efficiency. This approach is both elegant and practical, making it ideal for real-world applications where performance matters.