medium Search a 2D Matrix II

Problem Statement

Given a 2D grid of size m x n matrix containing integers, and integer target, return true if target value exists in the matrix. Otherwise, return false.

The matrix has the following properties:

• Values in each column are sorted in non-decreasing order from top to bottom.
• Values in each row are sorted in non-decreasing order from left to right.

Examples

Example 1:

• Input: target = 5, matrix =

[[1,2,3],
 [4,5,6],
 [7,8,9]]

• Expected Output: true
• Justification: The number 5 is located in the second row and second column of the matrix, thus the output is true.

Example 2:

• Input: target = 19, matrix =

[[10,11,12,13],
 [11,12,13,17],
 [14,19,22,24],
 [22,23,24,25]]

• Expected Output: true
• Justification: 19 is present in the third row and second column, confirming its presence in the matrix.

Example 3:

• Input: target = 6, matrix =

[[1,3,5],
 [7,9,11],
 [13,15,17]]

• Expected Output: false
• Justification: 6 does not appear anywhere in the matrix, so the function should return false.

Solution

To solve this problem, we'll employ a strategic approach that leverages the sorted nature of the matrix to efficiently search for the target. Starting from the top-right corner of the matrix, we compare the target with the current element. If the target is larger, we move down a row, and if it's smaller, we move left a column. This process is repeated until the target is found or the limits of the matrix are exceeded.

This approach is effective because it eliminates one row or one column during each comparison, significantly reducing the search space. By starting at the top-right (or alternatively, bottom-left) corner, we can make a decision at each step that guides us closer to the target's location. This method is more efficient than linearly searching each row or column, or performing a binary search in each row or column, especially in large matrices.

Step-by-Step Algorithm

1. Initialization: Start by checking if the matrix is empty or has no rows/columns. If so, return false as the target cannot be found in an empty matrix.
2. Set Starting Point: Position yourself at the top right corner of the matrix. This is done by setting the row index to 0 (first row) and the column index to the index of the last column (matrix[0].length - 1).
3. Iterative Search:
   • While your current position is within the bounds of the matrix (row index is less than the number of rows and column index is non-negative):
     • Compare Target with Current Element: If the current element (the one at your position) equals the target, return true as the target has been found.
     • Move Downwards: If the current element is less than the target, move down one row to increase the value (since rows are sorted in ascending order). This is done by incrementing the row index.
     • Move Leftwards: If the current element is greater than the target, move left one column to decrease the value (since columns are sorted in ascending order). This is done by decrementing the column index.
4. Target Not Found: If the loop terminates without returning true, it means the target is not present in the matrix. Return false.

Algorithm Walkthrough

For the input matrix:

[[10,11,12,13],
 [11,12,13,17],
 [14,19,22,24],
 [22,23,24,25]]

target = 19

1. Initialization: The matrix is not empty, so we proceed.
2. Set Starting Point: Start at the top right corner, which is element 13 (row = 0, col = 3).
3. Iterative Search:
   • Step 1: 13 is less than 19, so move down to increase the value (row = 1, col = 3).
   • Step 2: Now at 17 (row = 1, col = 3), which is still less than 19. Move down again (row = 2, col = 3).
   • Step 3: Now at 24 (row = 2, col = 3), which is greater than 19. Move left to decrease the value (row = 2, col = 2).
   • Step 4: Now at 22 (row = 2, col = 2), which is still greater than 19. Move left again (row = 2, col = 1).
   • Step 5: Now at 19 (row = 2, col = 1), which equals the target. Return true.
4. Conclusion: The target 19 is found in the matrix, so the algorithm returns true.

Code

public class Solution {

  // Searches for target value in a matrix
  public boolean searchMatrix(int[][] matrix, int target) {
    if (
      matrix == null || matrix.length == 0 || matrix[0].length == 0
    ) return false;

    int row = 0;
    int col = matrix[0].length - 1;

    // Start from top right corner and move towards the target
    while (row < matrix.length && col >= 0) {
      if (matrix[row][col] == target) {
        // Target found
        return true;
      } else if (matrix[row][col] < target) {
        // Move down
        row++;
      } else {
        // Move left
        col--;
      }
    }

    // Target not found
    return false;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[][] matrix1 = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
    System.out.println(solution.searchMatrix(matrix1, 5)); // true

    // Example 2
    int[][] matrix2 = {
      { 10, 11, 12, 13 },
      { 11, 12, 13, 17 },
      { 14, 19, 22, 24 },
      { 22, 23, 24, 25 },
    };
    System.out.println(solution.searchMatrix(matrix2, 19)); // true

    // Example 3
    int[][] matrix3 = { { 1, 3, 5 }, { 7, 9, 11 }, { 13, 15, 17 } };
    System.out.println(solution.searchMatrix(matrix3, 6)); // false
  }
}

Complexity Analysis

• Time Complexity: The algorithm has a time complexity of , where m is the number of rows and n is the number of columns in the matrix. This is because, in the worst-case scenario, the algorithm will travel from the top-right corner to the bottom-left corner, traversing at most m + n - 1 elements.

• Space Complexity: The space complexity is as the algorithm only uses a constant amount of space regardless of the input size.