Grid Challenge – Hackerrank Challenge – Java Solution
This is the java solution for the Hackerrank problem – Grid Challenge – Hackerrank Challenge – Java Solution.
Source – Ryan Fehr’s repository.
//Problem: https://www.hackerrank.com/challenges/grid-challenge //Java 8 /* Initial Thoughts: If we sort each of the rows to be lexico. order then we just need to check if the columns are sorted. This works because the position of the letters in each row are fixed because they can only be swapped within their row, so there is only 1 solution to each row which in turn gives us only one solution to the grid, which we can then check Time Complexity: O(n*(n log (n))) Space Complexity: O(n^2) //We build a n*n grid to store the input */ import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner input = new Scanner(System.in); int T = input.nextInt(); StringBuilder output = new StringBuilder(""); for(int t = 0; t < T; t++){ int n = input.nextInt();input.nextLine(); char[][] grid = new char[n][n]; //Read in rows of grid and sort for(int i = 0; i < n; i++){ grid[i] = input.nextLine().toCharArray(); Arrays.sort(grid[i]); } if(checkColumns(grid)) output.append("YES\n"); else output.append("NO\n"); } System.out.print(output); } //Checks if grid columns are lexicographically ordered static boolean checkColumns(char[][] grid){ for(int i = 0; i < grid.length; i++){//column for(int j = 1; j < grid.length; j++){//row if(grid[j][i] < grid[j-1][i]) return false; } } return true; } }