Robert Baindourov

NodeJS, ReactJS, ElectronJS - Web Software Architect

In this post, we explore a C++ solution to search for a value in a row-column sorted matrix. The matrix is sorted such that each row is sorted in ascending order from left to right, and the first element of any row is greater than or equal to the last element of the previous row.

Algorithm Steps

1. Row Selection: Since the entire matrix behaves like a flattened sorted array, we can identify which row the target number could possibly reside in. The target x must lie between the first and last element of that row: mat[i][0] <= x && mat[i][cols-1]>= x.
2. Binary Search: Once the target row is discovered, we run a standard binary search on that row to find the target.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
  public:
    bool searchMatrix(vector<vector<int>> &mat, int x) {
        vector<int>*row = nullptr;
        int rows = mat.size();
        int cols = mat[0].size();
        
        // Step 1: Find the candidate row
        for( int i = 0; i < rows; i++ ){
            if( mat[i][0] <= x && mat[i][cols-1] >= x ){
                row = &(mat[i]);
                break;
            }
        }
        
        if( row == nullptr ) return false;
        
        // Step 2: Binary Search lambda
        auto binarySearch = [row, x]( int low, int high ) -> bool{
            while( low <= high ){
                int mid = low + (high-low)/2;
                if( (*row)[mid] == x ){
                    return true;
                }else if((*row)[mid] < x ){
                    low =  mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return false;
        };   
        
        return binarySearch(0, cols -1 );
    }
};

Complexity

• Time Complexity: $O(R + log C)$ where $R$ is the number of rows and $C$ is the number of columns. Finding the row takes $O(R)$ linear scan, and binary search takes $O(log C)$. This can be optimized further to $O(log R + log C)$ by binary searching the rows.
• Space Complexity: $O(1)$ auxiliary space.