Search an element in a matrix

Problem Statement

Given an m x n matrix where each row and each column is sorted in ascending order, search for a target value and return whether it exists in the matrix.

Properties:

• Each row is sorted in ascending order (left to right)
• Each column is sorted in ascending order (top to bottom)

Example:

• Input: matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [7, 10, 13, 17]] target = 5
• Output: true
• Explanation: 5 exists in the matrix at position (1, 1)

Approach 1: Brute Force (Linear Search)

Intuition

Simply iterate through all elements in the matrix and check if any element equals the target.

Algorithm

1. Traverse each row of the matrix
2. For each row, traverse each column
3. If element equals target, return true
4. If no match found, return false

public class Solution {
    public boolean searchMatrixBrute(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length, n = matrix[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Complexity Analysis

• Time Complexity: O(m*n) - May need to check all elements
• Space Complexity: O(1) - Only using constant extra space

Approach 2: Binary Search on Each Row

Intuition

Since each row is sorted, we can apply binary search on each row to find the target.

Algorithm

1. For each row, apply binary search
2. If target is found in any row, return true
3. Return false if not found in any row

public class Solution {
    private boolean binarySearch(int[] row, int target) {
        int left = 0, right = row.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (row[mid] == target) return true;
            else if (row[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
    
    public boolean searchMatrixBinary(int[][] matrix, int target) {
        for (int[] row : matrix) {
            if (binarySearch(row, target)) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

• Time Complexity: O(m * log n) - Binary search on each of m rows
• Space Complexity: O(1) - Only using constant extra space

Approach 3: Staircase Search (Optimal)

Intuition

Start from the top-right corner (or bottom-left). From this position:

• If current element equals target, we found it
• If current element is greater than target, move left (smaller elements)
• If current element is less than target, move down (larger elements)

This works because the matrix is sorted both row-wise and column-wise.

Algorithm

1. Start from top-right corner (row = 0, col = n-1)
2. While within bounds:
   • If current element == target, return true
   • If current element > target, move left (col--)
   • If current element < target, move down (row++)
3. Return false if target not found

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length, n = matrix[0].length;
        int row = 0, col = n - 1;  // Start from top-right corner
        
        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;  // Move left
            } else {
                row++;  // Move down
            }
        }
        
        return false;
    }
    
    // Alternative: Start from bottom-left corner
    public boolean searchMatrixBottomLeft(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length, n = matrix[0].length;
        int row = m - 1, col = 0;  // Start from bottom-left corner
        
        while (row >= 0 && col < n) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                row--;  // Move up
            } else {
                col++;  // Move right
            }
        }
        
        return false;
    }
}

Complexity Analysis

• Time Complexity: O(m + n) - At most m + n steps (each step eliminates a row or column)
• Space Complexity: O(1) - Only using constant extra space

Variant: Strictly Sorted Matrix (Row-wise then Column-wise)

If the matrix is sorted such that the first element of each row is greater than the last element of the previous row, we can treat it as a 1D sorted array and use binary search.

Complexity: O(log(m*n)) time, O(1) space

Key Takeaways

1. Staircase search is the optimal approach for row-column sorted matrices
2. Starting from top-right or bottom-left allows eliminating one row/column per step
3. Starting from top-left or bottom-right doesn't work as both adjacent elements are either larger or smaller
4. For strictly sorted matrices (1D view), use pure binary search for O(log(m*n))
5. This technique is also called "Search Space Reduction"
6. The same approach works for finding count of elements less than or equal to target