Search in a Row-wise and Column-wise Sorted Matrix

Given an M x N matrix where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom, write a function to search for a given element in the matrix. Return the coordinates of the element if found, otherwise return (-1, -1).

Input/Output Examples

plaintext
Example 1:
Input:
matrix = [
    [10, 20, 30, 40],
    [15, 25, 35, 45],
    [27, 29, 37, 48],
    [32, 33, 39, 50]]
target = 29
Output: (2, 1)
Explanation: The element 29 is located at row index 2 and column index 1.

Example 2:
Input:
matrix = [
    [10, 20, 30, 40],
    [15, 25, 35, 45],
    [27, 29, 37, 48],
    [32, 33, 39, 50] ]
target = 100
Output: (-1, -1)
Explanation: The element 100 is not found in the matrix.

Approach to Search in a Row-wise and Column-wise Sorted Matrix

  1. Start from the Top-Right Corner:
    • Begin searching from the element at the top-right corner of the matrix. This is because the top-right corner allows you to make decisions based on the sorted properties of both the rows and columns.
  2. Move Based on Comparison with Target:
    • If the current element is equal to the target, return its coordinates.
    • If the current element is greater than the target, move left to the previous column (because moving left gives smaller values).
    • If the current element is less than the target, move down to the next row (because moving down gives larger values).
  3. Stop if the Element is Not Found:
    • Continue the process until you move out of the matrix bounds. If the target is not found by then, return (-1, -1).

C++ Program to Search in a Row-wise and Column-wise Sorted Matrix

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to search for a target in a row-wise and column-wise sorted matrix
pair<int, int> searchMatrix(const vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return {-1, -1};

    int rows = matrix.size();
    int cols = matrix[0].size();
    int row = 0, col = cols - 1;

    while (row < rows && col >= 0) {
        if (matrix[row][col] == target) {
            return {row, col};
        } else if (matrix[row][col] > target) {
            col--;
        } else {
            row++;
        }
    }

    return {-1, -1};
}

int main() {
    vector<vector<int>> matrix = {
        {10, 20, 30, 40},
        {15, 25, 35, 45},
        {27, 29, 37, 48},
        {32, 33, 39, 50}
    };
    int target = 29;
    pair<int, int> result = searchMatrix(matrix, target);

    cout << "Target found at: (" << result.first << ", " << result.second << ")" << endl;
    return 0;
}

Java Program to Search in a Row-wise and Column-wise Sorted Matrix

java
public class SearchSortedMatrix {

    // Function to search for a target in a row-wise and column-wise sorted matrix
    public static int[] searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return new int[]{-1, -1};

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

        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return new int[]{row, col};
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }

        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {10, 20, 30, 40},
            {15, 25, 35, 45},
            {27, 29, 37, 48},
            {32, 33, 39, 50}
        };
        int target = 29;
        int[] result = searchMatrix(matrix, target);

        System.out.println("Target found at: (" + result[0] + ", " + result[1] + ")");
    }
}

Python Program to Search in a Row-wise and Column-wise Sorted Matrix

python
# Function to search for a target in a row-wise and column-wise sorted matrix
def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return -1, -1

    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1

    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return row, col
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1

    return -1, -1

# Example usage
if __name__ == "__main__":
    matrix = [
        [10, 20, 30, 40],
        [15, 25, 35, 45],
        [27, 29, 37, 48],
        [32, 33, 39, 50]
    ]
    target = 29
    result = search_matrix(matrix, target)
    print("Target found at:", result)
  • Time Complexity: O(M + N) where M is the number of rows and N is the number of columns, as each row or column is traversed at most once.
  • Space Complexity: O(1) since only a constant amount of extra space is used, regardless of the matrix size.

DSA

4762

471

Related Articles