1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
3.1.
What is the preferred method to allocate a 2-d array dynamically?
3.2.
State the Time complexity for a complete traversal of a 2-d matrix?
3.3.
Why do we traverse the matrix from both left and right directions in this problem?
4.
Conclusion
Last Updated: Mar 27, 2024

# 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What is the preferred method to allocate a 2-d array dynamically?

A 2D array should be dynamically allocated in C++ using a single pointer.

### State the Time complexity for a complete traversal of a 2-d matrix?

Traversing a 2D array takes O (N * M) time, where N is the number of rows and M is the number of columns.

### Why do we traverse the matrix from both left and right directions in this problem?

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.

## Conclusion

This article extensively discussed the problem of counting the number of sorted rows either in increasing or decreasing order in a matrix and its time and space complexities.
Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Types of MatrixFind Good MatrixPrint MatrixBook Allocation Problem, Matrix is Symmetric.

Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! You can also check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problemsinterview experiences, and interview bundle.