Matrix: Given a matrix, count the number of sorted rows

Problem Statement:

You are given a 2D matrix of size [n * m].

You need to count all the rows in a matrix that are sorted in either increasing order or decreasing order.

Example:

Input:

m = 4 n = 4

1 2 3 4 
9 8 7 6 
3 4 1 2
6 1 8 9

Output:

2

Solution Explanation:

For the solution, you need to traverse matrix 2 times:

1. Traverse the matrix from left side and count the rows that are increasing order.

2. Traverse the matrix from right side and count the rows that are increasing order.

Then add the count to get the solution.

Time Complexity: O(m*n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <unordered_map>
using namespace std;

#define MAX 100

int solution(int mat[][MAX], int r, int c)
{
    int result = 0; 
    for (int i=0; i<r; i++)
    {
        int j;
        for (j=0; j<c-1; j++)
            if (mat[i][j+1] <= mat[i][j])
                break;

        if (j == c-1)
            result++;
    }

    for (int i=0; i<r; i++)
    {

        int j;
        for (j=c-1; j>0; j--)
            if (mat[i][j-1] <= mat[i][j])
                break;

        if (c > 1 && j == 0)
            result++;
    }
    return result;
}

int main()
{
    int m = 4, n = 4;
    int mat[][MAX] = {{1, 2, 3, 4},
                      {9, 8, 7, 6},
                      {3, 4, 1, 2},
                      {6, 1, 8, 9}};

    cout << solution(mat, m, n);
    return 0;
}

Output

2