algoadvance

Leetcode 240. Search a 2D Matrix II

Problem Statement

Write an efficient algorithm to search for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending order from left to right.
• Integers in each column are sorted in ascending order from top to bottom.

Given the matrix and a target value, return true if the target is found in the matrix, and false otherwise.

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

Clarifying Questions

1. Are there any constraints on the values in the matrix?
   • Values are integers and both the rows and the columns of the matrix are sorted in ascending order.
2. What should be returned if the matrix is empty or dimensions are 0?
   • If the matrix or its dimensions are empty, the function should return false.
3. What is the expected size of the matrix?
   • The matrix dimensions can be up to 300 x 300.

Strategy

To efficiently search the matrix, leverage its sorted properties:

• Start the search from the top-right corner.
• Compare the current element with the target:
  • If it’s equal to the target, return true.
  • If it’s smaller than the target, move down to the next row.
  • If it’s larger than the target, move left to the previous column.
• Repeat until the element is found or the indices go out of bounds.

Code

public 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;
        int col = cols - 1; // start from the top-right corner
        
        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--; // move left
            } else {
                row++; // move down
            }
        }
        
        return false;
    }
}

Time Complexity

• Best Case: O(1) - if the target is found at the first position checked.
• Average Case: O(m + n) - where m is the number of rows and n is the number of columns.
• Worst Case: O(m + n) - if the algorithm exhaustively checks all the potential positions along the way to the bottom left corner.

Space Complexity

• Overall: O(1) - The algorithm uses constant extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?