Search a 2D Matrix (opens in a new tab) Medium

Problem

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

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example

Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] target = 3

Output: true

Summary

To solve this problem, we can treat the 2D matrix as a 1D sorted array and perform a binary search to find the target value. We can convert the 1D index to 2D row and column indices using simple arithmetic operations.

Solution

In TypeScript

function searchMatrix(matrix: number[][], target: number): boolean {
    const rows = matrix.length;
    const cols = matrix[0].length;
 
    let left = 0;
    let right = rows * cols - 1;
 
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midValue = matrix[Math.floor(mid / cols)][mid % cols];
 
        if (midValue === target) {
            return true;
        } else if (midValue < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
 
    return false;
}

In Python

def searchMatrix(matrix, target):
		rows = len(matrix)
		cols = len(matrix[0])
 
		left = 0
		right = rows * cols - 1
 
		while left <= right:
				mid = (left + right) // 2
				midValue = matrix[mid // cols][mid % cols]
 
				if midValue == target:
						return True
				elif midValue < target:
						left = mid + 1
				else:
						right = mid - 1
 
		return False

Step-by-step explanation

Determine the number of rows and columns in the matrix.

const rows = matrix.length;
const cols = matrix[0].length;

Initialize two pointers, left and right, to represent the start and end indices of the "flattened" matrix (if it were a 1D array).

let left = 0;
let right = rows * cols - 1;

Perform a binary search in the matrix, as if it was a 1D sorted array.

while (left <= right) {
    // Find the middle index in the "flattened" matrix
    const mid = Math.floor((left + right) / 2);
 
    // Convert the 1D mid index to 2D row and column indices
    const row = Math.floor(mid / cols);
    const col = mid % cols;
 
    // Get the value at the calculated 2D indices
    const midValue = matrix[row][col];
 
    // If the midValue is equal to the target, return true
    if (midValue === target) {
        return true;
    }
    // If the midValue is less than the target, update the left pointer to mid + 1
    else if (midValue < target) {
        left = mid + 1;
    }
    // If the midValue is greater than the target, update the right pointer to mid - 1
    else {
        right = mid - 1;
    }
}

If the binary search loop ends without finding the target value, return false.

return false;

By treating the 2D matrix as a 1D sorted array and using binary search, we can efficiently search for the target value in the matrix.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(log(m * n)), where m is the number of rows and n is the number of columns in the matrix. This is because we perform a binary search over the elements of the matrix, which takes logarithmic time in the total number of elements.

Space Complexity

The space complexity of this solution is O(1), as we only use a constant amount of additional space to store the row and column indices and the calculated mid value.

4. Time Based Key-Value Store 6. Find Minimum in Rotated Sorted Array