I am currently practicing my HackerRank and problem-solving skills. I have the following question with a solution that 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.

Thank you!

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"    

CodePudding user response：

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

CodePudding user response：

Previous post works just fine and with detail explanations. Here is just an alternative approach which may help you understand the problem and improve the code better.

def gridChallenge(grid):
    sort_grid = [sorted(row) for row in grid]
        
    columns = [list(col) for col in zip(*sort_grid)]

    if all (col== sorted(col) for col in columns):  # every col is in sorted?
        return "YES"
    else:
        return "NO"