Trusted answers to developer questions
How to check if a given row is sorted in a matrix
abhilash
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
RELATED TAGS
matrix
data structures
communitycreator
CONTRIBUTOR
abhilash
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
