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:
- 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 nokth row in the given matrix. - Start looping from the first element of the
kth row. - Compare every two elements.
- If the two elements are sorted, then move to the next element, i.e.,
i+1. - Otherwise, it returns
false, indicating the row is not sorted.
- If the two elements are sorted, then move to the next element, i.e.,
- The loop will eventually come to the end of the row when all the elements of the row are in sorted order.
- It will return
true, indicating thekth 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
TRENDING TOPICS
