Count All Sorted Rows in a Matrix

Introduction

This blog covers a matrix problem. Matrices are one of the most important and often asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques. This blog tackles a coding task that involves 

counting the number of sorted rows in a matrix that is sorted either in strictly ascending or descending order.

Problem Statement

We are given a M x N  matrix in which some rows of the matrix are sorted in strictly non-decreasing order or strictly non-increasing order. We are expected to count the number of such rows present in the matrix.

Sample Examples

Input -1 

Output

4

Explanation

There are four different sorted rows in the matrix, either in ascending or descending order.

We will not count any other remaining rows.

Input -2 

Output

2

Explanation

There are two different sorted rows in the matrix, either in ascending or descending order.

We will not count any other remaining rows.

Approach

The approach for the above problem is quite simple and straightforward. We traverse the matrix two times, one from the left side to count strictly increasing rows and from the right side to count strictly decreasing ones.

Algorithm

1. Initialize a variable as a counter to count the total number of sorted rows in the matrix.

2. Start traversing the matrix from the left side to count all rows in strictly increasing order

and store the count in a result variable.

3. Start traversing the matrix from the right side to count all the rows in strictly decreasing order and store the count in a result variable.

4. Return the result variable.

Implementation

// Program to find number of sorted rows in a given n*m matrix
#include <bits/stdc++.h>
#define Maximum 100
using namespace std;

// Function for counting all sorted rows in a matrix
int sortCounter(int matrix[][Maximum], int row, int col)
{
    int counter = 0; // Initialize counter
   
     // Traverse from left side of matrix to
    // count all the increasing order rows in the matrix
    for (int i=0; i<row; i++)
    {
        int j;
        for (j=0; j<col-1; j++)
            if (matrix[i][j+1] <= matrix[i][j])
                break;
        if (j == col-1)
            counter++;
    }
    // Traverse from right side of matrix to
    // count all the increasing order rows in the matrix
    for (int i=0; i<row; i++)
    {
        int j;
        for (j=col-1; j>0; j--)
            if (matrix[i][j-1] <= matrix[i][j])
           break;
        if (col > 1 && j == 0)
            counter++;
    }
    return counter;
}

// Driver program
int main()
{
    int m = 3, n = 4;
    int matrix[][Maximum] = {{12, 13, 14, 15},
                           {69, 68, 67, 66},
                           {14, 17, 18, 11}};

   cout<<"The given matrix is:\n";
      for (size_t i = 0; i < m; i++)
      {
          for (int j = 0; j < n; j++)
          {
           cout<<matrix[i][j]<<" ";
          }
           cout<<endl;
      }
    cout << "The number of sorted rows is:"<< sortCounter(matrix, m, n);
    return 0;
}

Output

Time Complexity

The time complexity for the given approach is O(m*n) as we traverse the entire matrix to search for the sorted rows both in the left and right directions.

Space Complexity

The program's auxiliary space is O(1) because no additional data structure is involved.

Also see,  Rabin Karp Algorithm