How to check if a given row is sorted in a matrix

Problem overview

If you are given a mxn matrix and k, a number denoting the row number, how do you check whether the kth of the matrix is sorted in ascending order?

For example, consider the following matrix:

[1, 2, 3]
[-3, -5, 6]
[7, 8, 9]

When k=1 (first row), the row is sorted in ascending order. When k=2 (second row), the row is not sorted in ascending order.

Algorithm

The important point to note about matrices, is that a matrix is the stacking of one-dimensional arrays.

We can use the algorithm defined in this shot.

The steps of the algorithm are as follows:

  1. If the given row number, i.e.,k, is either greater than the number of rows or less than one (the first row), then there is no kth row in the given matrix.
  2. Start looping from the first element of the kth row.
  3. Compare every two elements.
    1. If the two elements are sorted, then move to the next element, i.e., i+1.
    2. Otherwise, it returns false, indicating the row is not sorted.
  4. The loop will eventually come to the end of the row when all the elements of the row are in sorted order.
  5. It will return true, indicating the kth row of the given matrix is sorted.

Implementation of the algorithm

import java.util.Arrays;
public class Main{
    private static boolean isSortedRow(int[] array, int n){
        if(n == 1 || n == 0) return true;
        for(int i = 1; i < n; i++){
            if(array[i] < array[i-1] ) return false;
        }
        return true;
    }
    private static void checkRowSorted(int[][] matrix, int k){
        int numRows = matrix.length;
        if(k < 1 || k > numRows){
            System.out.println("Unknown Row Given");
            return;
        }
        System.out.println("Row " + k + " of the above matrix is " + (isSortedRow(matrix[k-1], matrix[k-1].length)?"sorted":"not sorted"));
    }
    private static void printMatrix(int[][] matrix){
        for (int[] row : matrix)
            System.out.println(Arrays.toString(row));
    }
    public static void main(String[] args){
        int matrix[][] = {{1, 2, 3},
                {-3, -5, 6},
                {7, 8 , 9}};
        int k = 1;
        printMatrix(matrix);
        checkRowSorted(matrix, k);
        k = 2;
        checkRowSorted(matrix, k);
    }
}
kth row of matrix is sorted or not

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)