Search In A Row Wise And Column Wise Sorted Matrix Leetcode

Searching efficiently within a structured dataset is a fundamental task in computer science. In this article, you will learn various approaches to find a target value in a matrix where elements are sorted both row-wise and column-wise.

Problem Statement

The challenge is to determine if a given target integer exists within an m x n matrix. This matrix has a specific property: each row is sorted in non-decreasing order from left to right, and each column is sorted in non-decreasing order from top to bottom. Such matrices are common in various data structures, including specialized database indexes or game board representations where values increase predictably.

Example

Consider the following 4x5 matrix and a target value 5:

[[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]]

In this case, the target 5 is present in the matrix, located at matrix[1][1]. If the target was 20, the output would indicate that it's not found.

Background & Knowledge Prerequisites

To understand the solutions presented, a basic understanding of the following concepts is helpful:

• Arrays and Matrices: How to declare, initialize, and access elements in 2D arrays.
• Looping Constructs: for and while loops for iteration.
• Conditional Statements: if-else for decision making.
• Binary Search: While not strictly required for all approaches, understanding its efficiency (logarithmic time complexity) is beneficial for one of the methods.

No special libraries or complex setups are required beyond standard C input/output.

Use Cases or Case Studies

This specific type of sorted matrix search has several practical applications:

• Database Indexing: Imagine a database table where data is indexed on two attributes, like (age, salary), and both are sorted. Efficiently finding records matching certain criteria would use a similar search pattern.
• Game Boards: In strategy games or puzzle games, if a board's state can be represented by values that increase predictably across rows and columns (e.g., pathfinding costs, resource levels), this search can quickly locate specific points.
• Image Processing: Certain image filters or analyses might generate matrices with these properties, where finding a pixel with a specific intensity could benefit from this algorithm.
• Sensor Data Analysis: If sensor readings are collected in a grid-like fashion and sorted by location and time, quickly querying for specific values becomes possible.
• Range Queries: Beyond just finding a single element, this pattern can be extended to find all elements within a certain range in such a matrix.

Solution Approaches

We will explore three distinct approaches to solve this problem, ranging from naive to highly optimized.

Approach 1: Brute Force Iteration

This is the simplest method, involving checking every element in the matrix.

• Summary: Iterate through each row and each column, comparing every element with the target.

// Brute Force Matrix Search
#include <stdio.h>
#include <stdbool.h> // For boolean type

// Function to search for target in matrix using brute force
bool searchMatrixBruteForce(int matrix[5][5], int rows, int cols, int target) {
    // Step 1: Iterate through each row
    for (int i = 0; i < rows; i++) {
        // Step 2: Iterate through each column in the current row
        for (int j = 0; j < cols; j++) {
            // Step 3: Compare current element with the target
            if (matrix[i][j] == target) {
                return true; // Target found
            }
        }
    }
    return false; // Target not found after checking all elements
}

int main() {
    int matrix[5][5] = {
        {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}
    };
    int rows = 5;
    int cols = 5;
    int target1 = 5;
    int target2 = 20;

    // Test with target1
    if (searchMatrixBruteForce(matrix, rows, cols, target1)) {
        printf("Target %d found in the matrix (Brute Force).\\n", target1);
    } else {
        printf("Target %d not found in the matrix (Brute Force).\\n", target1);
    }

    // Test with target2
    if (searchMatrixBruteForce(matrix, rows, cols, target2)) {
        printf("Target %d found in the matrix (Brute Force).\\n", target2);
    } else {
        printf("Target %d not found in the matrix (Brute Force).\\n", target2);
    }

    return 0;
}

Run

• Sample Output:

  Target 5 found in the matrix (Brute Force).
  Target 20 not found in the matrix (Brute Force).

• Stepwise Explanation:

1. Initialize two nested loops: an outer loop for rows (i) and an inner loop for columns (j).
2. For each element matrix[i][j], compare it with the target.
3. If a match is found, immediately return true.
4. If the loops complete without finding the target, return false.

Approach 2: Binary Search on Each Row

Leveraging the row-wise sorted property, we can apply binary search to each row.

• Summary: Iterate through each row and perform a binary search within that row for the target value.

// Binary Search on Each Row
#include <stdio.h>
#include <stdbool.h>

// Helper function for binary search on a 1D array
bool binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Prevent overflow
        if (arr[mid] == target) {
            return true;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return false;
}

// Function to search for target in matrix using binary search on each row
bool searchMatrixRowBinarySearch(int matrix[5][5], int rows, int cols, int target) {
    // Step 1: Iterate through each row
    for (int i = 0; i < rows; i++) {
        // Step 2: Perform binary search on the current row
        if (binarySearch(matrix[i], cols, target)) {
            return true; // Target found in this row
        }
    }
    return false; // Target not found in any row
}

int main() {
    int matrix[5][5] = {
        {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}
    };
    int rows = 5;
    int cols = 5;
    int target1 = 5;
    int target2 = 20;

    // Test with target1
    if (searchMatrixRowBinarySearch(matrix, rows, cols, target1)) {
        printf("Target %d found in the matrix (Binary Search per Row).\\n", target1);
    } else {
        printf("Target %d not found in the matrix (Binary Search per Row).\\n", target1);
    }

    // Test with target2
    if (searchMatrixRowBinarySearch(matrix, rows, cols, target2)) {
        printf("Target %d found in the matrix (Binary Search per Row).\\n", target2);
    } else {
        printf("Target %d not found in the matrix (Binary Search per Row).\\n", target2);
    }

    return 0;
}

Run

• Sample Output:

  Target 5 found in the matrix (Binary Search per Row).
  Target 20 not found in the matrix (Binary Search per Row).

• Stepwise Explanation:

1. Define a helper function binarySearch that takes a 1D array, its size, and the target, returning true if found, false otherwise.
2. In searchMatrixRowBinarySearch, loop through each row of the matrix.
3. For each row, call binarySearch with that row and the target.
4. If binarySearch returns true for any row, immediately return true from the main function.
5. If all rows are checked and the target isn't found, return false.

Approach 3: Optimal Two-Pointer Search (Matrix Staircase Search)

This approach leverages both the row-wise and column-wise sorted properties to eliminate rows and columns efficiently. It starts from a corner (typically top-right or bottom-left) and moves towards the target.

• Summary: Start from the top-right corner. If the current element is equal to the target, return true. If it's less than the target, move down (increment row) because all elements to its left in the current row are smaller. If it's greater than the target, move left (decrement column) because all elements below it in the current column are larger.

// Optimal Matrix Search
#include <stdio.h>
#include <stdbool.h>

// Function to search for target in matrix using optimal two-pointer approach
bool searchMatrixOptimal(int matrix[5][5], int rows, int cols, int target) {
    // Step 1: Start from the top-right corner
    int row = 0;
    int col = cols - 1;

    // Step 2: Continue as long as we are within matrix bounds
    while (row < rows && col >= 0) {
        // Step 3: Compare current element with target
        if (matrix[row][col] == target) {
            return true; // Target found
        } else if (matrix[row][col] < target) {
            // Step 4: If current element is too small, move down to a larger row
            row++;
        } else { // matrix[row][col] > target
            // Step 5: If current element is too large, move left to a smaller column
            col--;
        }
    }
    return false; // Target not found
}

int main() {
    int matrix[5][5] = {
        {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}
    };
    int rows = 5;
    int cols = 5;
    int target1 = 5;
    int target2 = 20;

    // Test with target1
    if (searchMatrixOptimal(matrix, rows, cols, target1)) {
        printf("Target %d found in the matrix (Optimal).\\n", target1);
    } else {
        printf("Target %d not found in the matrix (Optimal).\\n", target1);
    }

    // Test with target2
    if (searchMatrixOptimal(matrix, rows, cols, target2)) {
        printf("Target %d found in the matrix (Optimal).\\n", target2);
    } else {
        printf("Target %d not found in the matrix (Optimal).\\n", target2);
    }

    return 0;
}

Run

• Sample Output:

  Target 5 found in the matrix (Optimal).
  Target 20 not found in the matrix (Optimal).

• Stepwise Explanation:

1. Initialize two pointers: row to 0 (first row) and col to cols - 1 (last column). This places the starting point at the top-right corner.
2. Enter a while loop that continues as long as row is within bounds (< rows) and col is within bounds (>= 0).
3. Inside the loop, compare matrix[row][col] with the target:
   • If matrix[row][col] == target, the target is found, return true.

1. If the loop finishes without finding the target (i.e., row goes out of bounds or col goes out of bounds), return false.

Conclusion

We've explored different strategies for searching in a row-wise and column-wise sorted matrix. While a brute-force approach is simple to implement, its time complexity is high. Leveraging binary search on each row offers an improvement. The most efficient method, the two-pointer staircase search, cleverly uses the dual-sorted property to eliminate entire rows or columns in each step, resulting in a significantly faster solution.

Summary

• Problem: Find a target in a matrix sorted both row-wise and column-wise.
• Brute Force: Checks every element, O(m\*n) time complexity.
• Binary Search per Row: Applies binary search to each row, O(m \* log n) time complexity.
• Optimal Two-Pointer (Staircase) Search: Starts from a corner (e.g., top-right) and moves by eliminating rows or columns, O(m + n) time complexity, which is generally the most efficient.
• Key Insight: The optimal approach efficiently narrows down the search space by exploiting the unique sorting properties of the matrix.