Search a 2D Matrix II

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.

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.