Grid Challenge HackerRank Edge Case is not working

Question

I am currently practicing my HackerRank and problem-solving skills. I have the following question: Given a square grid of characters in the range ascii[a-z], rearrange elements of each row alphabetically, ascending. Determine if the columns are also in ascending alphabetical order, top to bottom. Return YES if they are or NO if they are not.

My solution works for the 11/12 test cases. It is the most efficient way to solve this but it is failing a specific edge case. I would appreciate someone that helps me identify this case and improve the code.

def gridChallenge(grid):
    last_string = ""
    
    for string in grid:
        string = ''.join(sorted(string))
        print(string)
        if string < last_string:
            return "NO"
        last_string = string

    return "YES"    

Answer 1

Where is your code failing?

Test Case 10 : Grid # 80

2
iv
sm

Expected Output

No, because although i is less than s but v is not less than m.

Your Output

Yes, because, you simply compare iv to sm; and indeed iv is less than sm.

So what to do?

Compare each column through these strings rather than comparing the entire strings themselves.

How do we do that?

• The first step requires sorting each row in grid, and appending them to another list called sorted_grid:

sorted_grid = []
for row in grid:
    sorted_row = sorted(row)
    sorted_grid.append(sorted_row)

• Now that we have a sorted_grid where each row is sorted, we need to check whether each column is sorted as well; which is the required task of this problem.

• To do that we unpack the sorted_grid using the * operator, and pass it to zip() function which would create a bunch of columns. We then convert each column to a list using the list() function. A one-liner would like this:

columns = [list(column) for column in zip(*sorted_grid)]

• Finally, we iterate over each column and each check if it is sorted, by comparing for equality against sorted(column). This check decides whether we must return "NO" or "YES". The complete code should look something like this:

def gridChallenge(grid):
    sorted_grid = []
    for row in grid:
        sorted_row = sorted(row)
        sorted_grid.append(sorted_row)
    possible = "YES"
    columns = [list(column) for column in zip(*sorted_grid)]
    for column in columns:
        if column != sorted(column):
            possible = "NO"
            break
    return possible