Hackerrank: Grid Challenge

Given a squared sized grid of size in which each cell has a lowercase letter. Denote the character in the the row and in the th column as G[i][j].

You can perform one operation as many times as you like: Swap two column adjacent characters in the same row G[i][j] and G[i][j+1] for all valid i,j;

Is it possible to rearrange the grid such that the following condition is true?
G[i][j]<=G[i][2]<=….<=G[i]N] for 1<=i <=N
G[1][j]<=G[2][j]<=….<=G[N][j] for 1<=j<=N
In other words, is it possible to rearrange the grid such that every row and every column is lexicographically sorted?

Solution :
This is fairly easy to resolve.We can approach this problem by first sorting the rows, which implies the first condition is taken care of.Next we need to check if columns are sorted, if they are sorted the even second condition is true.
Below is the scala code for the same.

 

Leave a Reply

Your email address will not be published. Required fields are marked *