Search in a 2D Matrix

Slug: sum-of-array-elements2502

Difficulty: School

Id: 702029

Topic Tags: Arrays, Data Structures

Company Tags: None

Summary

The problem is to search for an element in a sorted 2D matrix. The matrix is sorted row-wise and column-wise. You need to find the target element in the matrix by traversing through it.

Detailed Explanation

To solve this problem, we can start from the top-right corner of the matrix (i.e., the last element in each row) and move towards the left or down based on whether the current element is greater than, less than, or equal to the target element. This approach takes advantage of the fact that the matrix is sorted.

Here's a step-by-step breakdown of the solution:

1. Start from the top-right corner of the matrix.
2. Compare the current element with the target element.
3. If the current element is greater than the target element, move down to the next row (since the matrix is sorted column-wise).
4. If the current element is less than the target element, move left to the previous column (since the matrix is sorted row-wise).
5. Repeat steps 2-4 until you find the target element or reach a position where it's not present.

Time complexity: O(m + n), where m and n are the number of rows and columns in the matrix respectively. Space complexity: O(1), as we only need to keep track of the current row and column indices.

Optimized Solutions

Java

java
public int searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0) return -1;

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

    int start = 0;
    int end = rows * cols - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;
        int midVal = matrix[mid / cols][mid % cols];

        if (midVal == target) return mid;

        if (midVal < target) start = mid + 1;
        else end = mid - 1;
    }

    return -1;
}

Python

python
def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return -1

    rows = len(matrix)
    cols = len(matrix[0])

    start = 0
    end = rows * cols - 1

    while start <= end:
        mid = (start + end) // 2
        midVal = matrix[mid // cols][mid % cols]

        if midVal == target: return mid

        if midVal < target: start = mid + 1
        else: end = mid - 1

    return -1

C++

cpp
int searchMatrix(int** matrix, int rows, int cols, int target) {
    if (matrix == nullptr || rows == 0) return -1;

    int start = 0;
    int end = rows * cols - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;
        int midVal = matrix[mid / cols][mid % cols];

        if (midVal == target) return mid;

        if (midVal < target) start = mid + 1;
        else end = mid - 1;
    }

    return -1;
}

JavaScript

javascript
function searchMatrix(matrix, target) {
    if (!matrix || !matrix[0]) return -1;

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

    let start = 0;
    let end = rows * cols - 1;

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        let midVal = matrix[Math.floor(mid / cols)][mid % cols];

        if (midVal === target) return mid;

        if (midVal < target) start = mid + 1;
        else end = mid - 1;
    }

    return -1;
}