Search a 2D Matrix II

Updated on 03 July, 2025
Search a 2D Matrix II header image

Problem Statement

The task is to develop an algorithm to efficiently search for a specified value, referred to as target, within a two-dimensional grid or matrix. This matrix is defined by dimensions m x n, where m represents the number of rows and n represents the number of columns. The unique characteristics of this matrix are as follows:

  • Each row contains integers arranged in an ascending order from left to right.
  • Each column also contains integers arranged in ascending order from top to bottom.

These properties can significantly aid in creating a more efficient search algorithm by leveraging the sorted nature of the matrix's rows and columns.

Examples

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
  • -109 <= matrix[i][j] <= 109
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -109 <= target <= 109

Approach and Intuition

To tackle the problem of searching in a matrix with both rows and columns sorted in ascending order, we can utilize a more strategic approach rather than a brute force search. Here, we will explore the intuitive "step-wise" approach:

  1. Start from a corner of the matrix. The top-right corner is often a good starting point because it allows you to move left if the current value is greater than the target or move down if the current value is less than the target.
  2. Compare the target with the element at the current position of the matrix:
    • If the target is equal to the element, return true.
    • If the target is less than the element, move one column to the left (i.e., decrease the column index).
    • If the target is greater than the element, move one row downwards (i.e., increase the row index).
  3. Continue this process until you either find the target or exhaust possible moves within the boundaries of the matrix (i.e., you can't move left or down anymore).
  4. If no matching element is found by the time you exit the loops, return false.

This step-wise search is efficient as each move makes a definite elimination of either a row or a column, reducing the search area with each step. Given the constraints that both m and n can be as large as 300, this efficient approach is permissible within these bounds, as each step logically reduces the problem size. Comparatively, employing straightforward linear or binary search techniques row-wise or column-wise may not fully utilize the sorted properties of both the rows and the columns simultaneously as effectively as the described approach.

Solutions

  • Java
java
class Solution {
    public boolean matrixSearch(int[][] grid, int key) {
        int i = grid.length - 1;
        int j = 0;
    
        while (i >= 0 && j < grid[0].length) {
            if (grid[i][j] > key) {
                i--;
            } else if (grid[i][j] < key) {
                j++;
            } else {
                return true;
            }
        }
    
        return false;
    }
}

This solution describes a method to search for a specific value in a 2D matrix which is sorted such that each row's elements and each column's elements are in ascending order. The Java implementation provided involves a function matrixSearch which utilizes an efficient searching mechanism taking advantage of the matrix's properties.

Strategically start the search from the bottom-left corner of the matrix:

  • Initialize two pointers: one (i) at the last row, and another (j) at the first column.

The search process involves the following steps:

  1. Compare the current element pointed at by grid[i][j] to the target value key.
  2. If the current element is greater than the target, move vertically upwards by decrementing i to possibly find a smaller element.
  3. If the current element is less than the target, move horizontally right by incrementing j to find a larger element.
  4. Repeat the process until either:
    • The element is found, in which case true is returned.
    • The search space is exhausted (i.e., i or j moves out of matrix bounds), and false is returned.

This method effectively reduces the search space with each comparison, leading to a time complexity better than a brute-force approach. Make sure the matrix adheres to the sorted property for correct function of the algorithm.

  • Python
python
class Solution:
    def findInMatrix(self, mtx: List[List[int]], val: int) -> bool:
        if not mtx or not mtx[0]:
            return False
    
        max_rows = len(mtx)
        max_cols = len(mtx[0])
    
        r = max_rows - 1
        c = 0
    
        while r >= 0 and c < max_cols:
            if mtx[r][c] > val:
                r -= 1
            elif mtx[r][c] < val:
                c += 1
            else:
                return True
    
        return False

To tackle the problem of searching a value in a 2-dimensional matrix where the matrix is sorted in a row-wise and column-wise manner, the provided Python code employs an efficient search strategy utilizing a two-pointer technique. Here's how the solution operates:

  • The function first checks if the matrix or its first row is empty, and if so, returns False as the value cannot be found.

  • The dimensions of the matrix are determined by calculating the number of rows and columns.

  • The search begins from the bottom-left corner of the matrix, initializing the row index to the last row (r = max_rows - 1) and the column index to the first column (c = 0).

  • A loop runs until the row or column indices go out of the matrix bounds:

    • If the current matrix element is greater than the target value, the search moves upwards by decrementing the row index (r -= 1).

    • Conversely, if the current matrix element is less than the target value, the search shifts to the right by incrementing the column index (c += 1).

    • If the matrix element matches the target value, True is returned, indicating that the value is found within the matrix.

  • If the loop terminates without finding the value, the function returns False, indicating that the value does not exist within the matrix.

This approach leverages the matrix's properties for a time-optimized search, reducing the average complexity compared to a naive search method.

Comments

No comments yet.