Loading…

easyGreedySometimes asked

Grid Challenge

Q: How do you solve Grid Challenge using the Brute Force — Try Every Per-Row Permutation approach?

When to use it: Mention it to expose the search space, then collapse it with the 'sort each row' lemma. Brute force takes the problem at face value: 'rearrange characters within each row' means each row has `m!` possible orderings, and an arrangement of the whole grid picks one ordering per row. We'd enumerate all `(m!)ⁿ` combinations and, for each, test whether every column is non-decreasing top to bottom. **Why this is the literal reading.** The problem grants a freedom (permute within rows) and asks a yes/no question (can the columns be made sorted). The exhaustive way to answer is to try every legal arrangement and check the property. **Why it's impossible at scale.** With `m = 100` the per-row count `100!` is already larger than the number of atoms in the universe, and we raise that to the `n`-th power. No machine enumerates this. **The lemma that rescues us.** Claim: *if any combination of per-row permutations makes all columns non-decreasing, then sorting every row ascending also makes all columns non-decreasing.* Intuitively, sorting a row ascending only ever moves smaller characters left and larger ones right; doing this to every row preserves the existence of a valid column ordering. So we never need to search — one canonical arrangement (all rows ascending) is a valid witness whenever any witness exists. That turns `(m!)ⁿ` into a single sort per row. Time complexity: O((m!)ⁿ · n · m). Space complexity: O(n · m).

Greedy Algorithms · 18 of 23 · 8 min

Given a square grid of lowercase letters represented as n strings each of length n (more generally n rows of length m), determine whether the grid can be arranged so that both of the following hold:

1
Each row is sorted in non-decreasing (ascending) order, and
2
Each column is sorted in non-decreasing (top-to-bottom) order.

You may rearrange the characters within each row in any order, but you may not move characters between rows. Return "YES" if such an arrangement exists, otherwise "NO".

In plain English

Since we may freely permute the letters inside any row, the only way to satisfy 'rows sorted ascending' is to actually sort each row. The real question is whether, once every row is sorted ascending, the columns happen to be non-decreasing as well. If yes, the grid is feasible.

Examples

Example 1

Input: grid = ["ebacd", "fghij", "olmkn", "trpqs", "xywuv"]
Output: YES
Note: Sort each row → ["abcde", "fghij", "klmno", "pqrst", "uvwxy"]. Every column reads top-to-bottom as a,f,k,p,u … all non-decreasing.

Example 2

Input: grid = ["abc", "ade", "efg"]
Output: YES
Note: Rows already ascending. Columns: (a,a,e), (b,d,f), (c,e,g) — each non-decreasing → YES.

Example 3

Input: grid = ["zyx", "wvu"]
Output: NO
Note: Sort each row → ["xyz", "uvw"]. Column 0 is (x,u): u < x, so it decreases → NO.

Constraints

1 ≤ n ≤ 100 (number of rows)
Each row has the same length m (1 ≤ m ≤ 100)
All characters are lowercase English letters 'a'–'z'

Clarifying questions4First question: Can I rearrange characters across different rows?Explore questions

Q1.Can I rearrange characters across different rows?
No. Reordering is allowed only within a row. Characters stay in their original row.
Q2.Do rows have to be sorted, or just the columns?
Both. But because we control the row order completely, satisfying 'rows ascending' is free — sort them. The columns are what may or may not work out.
Q3.Is the grid always square?
The classic version is n × n, but the algorithm works for any n × m: sort each length-m row, then check the columns.
Q4.Are characters case-sensitive or include non-letters?
All lowercase English letters, so a direct character (ASCII) comparison is enough.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Sort the characters of each row independently in ascending order, then check that every COLUMN is non-decreasing top to bottom. If all columns pass, print 'YES'; otherwise 'NO'. The greedy claim — sorting each row is the best possible arrangement — is provably safe: if any per-row reordering makes the columns sorted, sorting each row ascending does too. O(n · m log m) from sorting the rows.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise sorting each row independently is not just a heuristic but provably optimal for making the columns sortable, and whether you implement the column check correctly.

Where candidates slip

Sorting the whole grid or sorting columns, or only checking adjacent characters within rows instead of verifying the columns after sorting.

How to stand out

Prove the greedy is safe: if some per-row reordering makes all columns non-decreasing, then replacing each row with its ascending sort preserves that, so the ascending-sort arrangement is a valid witness whenever one exists.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Per-Row Permutation	`O((m!)ⁿ · n · m)`	`O(n · m)`	Mention it to expose the search space, then collapse it with the 'sort each row' lemma.	Read
2	Greedy — Sort Each Row Ascending, Then Check Columns (Optimal)Optimal	`O(n · m log m)`	`O(n · m)`	The answer they want. Phrase it as 'sort every row, then a single pass verifies the columns'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewGrid of rowsEvery column non-decreasing?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Per-Row Permutation

TimeO((m!)ⁿ · n · m)SpaceO(n · m)

Mention it to expose the search space, then collapse it with the 'sort each row' lemma.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each row can be permuted in m! ways. A full arrangement is one permutation per row — how many combinations is that across n rows?

2Hint 2Explore hint

Enumerate every combination of per-row permutations, then check whether all columns are non-decreasing. Return YES if any combination works.

3Hint 3Explore hint

This is astronomically large — (m!)ⁿ. It's only useful to argue that we don't need it: a single canonical permutation (sort ascending) suffices.

A · Core idea

Brute force takes the problem at face value: 'rearrange characters within each row' means each row has m! possible orderings, and an arrangement of the whole grid picks one ordering per row. We'd enumerate all (m!)ⁿ combinations and, for each, test whether every column is non-decreasing top to bottom.

Why this is the literal reading. The problem grants a freedom (permute within rows) and asks a yes/no question (can the columns be made sorted). The exhaustive way to answer is to try every legal arrangement and check the property.

Why it's impossible at scale. With m = 100 the per-row count 100! is already larger than the number of atoms in the universe, and we raise that to the n-th power. No machine enumerates this.

The lemma that rescues us. Claim: if any combination of per-row permutations makes all columns non-decreasing, then sorting every row ascending also makes all columns non-decreasing. Intuitively, sorting a row ascending only ever moves smaller characters left and larger ones right; doing this to every row preserves the existence of a valid column ordering. So we never need to search — one canonical arrangement (all rows ascending) is a valid witness whenever any witness exists. That turns (m!)ⁿ into a single sort per row.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

grid = ["ba", "dc"]

[ba, dc]

col0 (b,d) ok, col1 (a,c) ok

Statevalid → YES

Final resultYES (and the all-ascending arrangement is one of the valid witnesses)

C · Code with teaching comments

Reference implementation previewpublic String gridChallenge(List<String> grid) { int n = grid.size(); char[][] rows = new char[n][]; for (int i = 0; i < n; i++) { rows[i] = grid.get(i).toCharArray();Explore the full code

solution.javaJava

Brute Force — Try Every Per-Row Permutation — reference

2 teaching notes

1
public String gridChallenge(List<String> grid) {
2
    int n = grid.size();
3
    char[][] rows = new char[n][];
4
    for (int i = 0; i < n; i++) {
5
        rows[i] = grid.get(i).toCharArray();
6
    }
7
    return search(rows, 0) ? "YES" : "NO";
8
}
9
 
10
private boolean search(char[][] rows, int r) {
11
    if (r == rows.length) {
12
        for (int j = 0; j < rows[0].length; j++) {
13
            for (int i = 1; i < rows.length; i++) {
14
                // A column that decreases anywhere disqualifies this arrangement.
15
                if (rows[i][j] < rows[i - 1][j]) return false;
16
            }
17
        }
18
        return true;
19
    }
20
    // Generate all permutations of row r, recursing to the next row for each.
21
    return permuteRow(rows, r, 0);
22
}
23
 
24
private boolean permuteRow(char[][] rows, int r, int start) {
25
    if (start == rows[r].length) return search(rows, r + 1);
26
    for (int i = start; i < rows[r].length; i++) {
27
        char t = rows[r][start]; rows[r][start] = rows[r][i]; rows[r][i] = t;
28
        if (permuteRow(rows, r, start + 1)) return true;
29
        t = rows[r][start]; rows[r][start] = rows[r][i]; rows[r][i] = t;
30
    }
31
    return false;
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO((m!)ⁿ · n · m) timeO(n · m) spaceOpen the invariant and proofExplore the proof

The brute force's only value is revealing that the feasibility property is closed under sorting each row. Once you believe that lemma, the entire permutation search collapses to a single canonical arrangement.

ComplexityO((m!)ⁿ · n · m) time, O(n · m) space — There are m! permutations per row and n rows, so (m!)ⁿ combinations; verifying each scans the n×m grid. The exponential tower makes it infeasible past trivial sizes.

E · Edge cases and pitfalls3(m!)ⁿ blow-up — only runs for tiny grids; it's a thought experiment.Explore edge cases

Pitfalls

(m!)ⁿ blow-up — only runs for tiny grids; it's a thought experiment.
Forgetting characters stay within their original row.
Checking rows for sortedness but not the columns — the columns are the real test.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort Each Row Ascending, Then Check Columns (Optimal)

TimeO(n · m log m)SpaceO(n · m)

The answer they want. Phrase it as 'sort every row, then a single pass verifies the columns'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Rows can be freely permuted, so satisfying 'rows ascending' costs nothing — just sort them. What's left to verify?

2Hint 2Explore hint

After sorting each row ascending, the only thing that can still fail is a column decreasing somewhere. Check each column top to bottom.

3Hint 3Explore hint

If every adjacent pair grid[i][j] >= grid[i-1][j] holds for all columns, return YES; the first violation returns NO.

A · Core idea

Two phases. Phase 1: sort each row ascending. Since the problem lets us reorder characters within a row, and 'rows must be ascending' is one of the requirements, sorting each row is both required and free. Phase 2: verify columns. Walk every column top to bottom; if any grid[i][j] < grid[i-1][j], the column decreases and the grid is infeasible — return "NO". If all columns survive, return "YES".

Why sorting each row is safe — the exchange argument. Suppose some arrangement A (one permutation per row) makes all columns non-decreasing. Take any single row of A that isn't already ascending; it has two adjacent positions j and j+1 with A[i][j] > A[i][j+1]. Swap them. After the swap the row is 'more sorted', and crucially the columns are still valid: at column j the value only got smaller (helps the ≤ from above and still dominates below because the value that moved in came from a position that was already column-valid), and symmetrically at j+1. Repeating adjacent swaps (a bubble sort) turns every row ascending while preserving column validity at each step. Therefore, if any valid arrangement exists, the all-rows-ascending arrangement is valid too. So we lose nothing by committing to ascending rows — the greedy choice can never rule out a feasible grid.

Why we still must check columns. Sorting rows fixes the row requirement but says nothing about columns. ["zyx", "wvu"] sorts to ["xyz", "uvw"], yet column 0 reads x then u — a decrease. The column scan is the actual feasibility decision; the sort just puts us in the only arrangement worth testing.

Why top-to-bottom adjacent comparison suffices. Non-decreasing down a column is a transitive chain: if every consecutive pair satisfies ≥, the whole column is sorted. We never need to compare non-adjacent rows.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

grid = ["ebacd", "fghij", "olmkn", "trpqs", "xywuv"]

Array state

i=1

f ≥ a ✓

[0]

i ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Greedy — Sort Each Row Ascending, Then Check Columns (Optimal) — optimal

4 teaching notes

1
public String gridChallenge(List<String> grid) {
2
    int n = grid.size();
3
    char[][] rows = new char[n][];
4
    for (int i = 0; i < n; i++) {
5
        rows[i] = grid.get(i).toCharArray();
6
        // Sort each row ascending — the free, canonical arrangement of its characters.
7
        Arrays.sort(rows[i]);
8
    }
9
    int m = rows[0].length;
10
    // Outer loop walks each column independently.
11
    for (int j = 0; j < m; j++) {
12
        for (int i = 1; i < n; i++) {
13
            // A single top-to-bottom decrease means no valid arrangement exists.
14
            if (rows[i][j] < rows[i - 1][j]) {
15
                // Fail fast on the first violating column.
16
                return "NO";
17
            }
18
        }
19
    }
20
    return "YES";
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n · m log m) timeO(n · m) spaceOpen the invariant and proofExplore the proof

The freedom 'permute within rows' has a unique canonical resolution: sort ascending. Recognising that a search over arrangements has one dominating representative — and proving it with a swap argument — is the reusable skill. After that, the problem is a trivial monotonicity scan.

ComplexityO(n · m log m) time, O(n · m) space — Sorting n rows of length m is O(n · m log m) and dominates; the column scan is O(n · m). We store the mutable sorted rows → O(n · m) space.

E · Edge cases and pitfalls6single row ["cba"] — Sort to "abc"; with one row there are no column comparisons → YES.Explore edge cases

Edge cases handled

single row ["cba"]Sort to "abc"; with one row there are no column comparisons → YES.
single column ["b", "a"]Rows sort trivially; column reads b,a which decreases → NO.
all identical letters ["aa", "aa"]Sorting is a no-op; every column is constant (non-decreasing) → YES.

Pitfalls

Sorting the entire flattened grid instead of each row separately.
Checking only rows after sorting and forgetting the column scan.
Comparing non-adjacent rows — adjacent comparisons already cover the whole column by transitivity.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String gridChallenge(List<String> grid) { int n = grid.size(); char[][] rows = new char[n][]; for (int i = 0; i < n; i++) { rows[i] = grid.get(i).toCharArray();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the column verification

Sorting rows satisfies only the row requirement. Without the column scan, a grid like ["zyx","wvu"] would be wrongly accepted.

Explore the code comparison

Don't write this

rows = [sorted(row) for row in grid]
return "YES"

Write this instead

rows = [sorted(row) for row in grid]
for j in range(len(rows[0])):
    for i in range(1, len(rows)):
        if rows[i][j] < rows[i - 1][j]:
            return "NO"
return "YES"

Sorting the grid as one flat list

Characters may only move within their own row. Flattening and sorting the whole grid moves characters across rows, which is illegal.

Explore the code comparison

Don't write this

char[] all = String.join("", grid).toCharArray();
Arrays.sort(all);
// reshape and check — WRONG: characters crossed row boundaries

Write this instead

for (int i = 0; i < n; i++) {
    rows[i] = grid.get(i).toCharArray();
    Arrays.sort(rows[i]);
}

Comparing within a row instead of down a column

After sorting, rows are trivially non-decreasing. The real condition couples rows together, so you must compare grid[i][j] against grid[i-1][j] down each column.

Explore the code comparison

Don't write this

for row in rows:
    for j in range(1, len(row)):
        if row[j] < row[j - 1]:
            return "NO"

Write this instead

for j in range(len(rows[0])):
    for i in range(1, len(rows)):
        if rows[i][j] < rows[i - 1][j]:
            return "NO"

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy normalisation: sort each row ascending, then verify columns

Code pattern to memorize

for each row: sort its characters ascending
for each column j:
    for each row i from 1:
        if grid[i][j] < grid[i-1][j]: return "NO"
return "YES"

Rules to remember

1Sort the letters within each row ascending — rows may be freely rearranged, that's the whole point.
2After sorting rows, the columns must be non-decreasing top to bottom; check grid[i][j] >= grid[i-1][j].
3You may NOT reorder rows or columns as units — only the characters inside each row.
4Sorting each row ascending is the unique best try: if any arrangement sorts the columns, the all-rows-ascending one does too.
5Compare characters directly (lexicographic / ASCII). All-lowercase input means a plain char comparison works.

Use this pattern when

Each row/group can be internally reordered and you must satisfy a cross-group monotonic property
A 2-D feasibility check where rows are independent but columns couple them
You suspect 'sort each part, then verify the global condition' collapses the search
The condition is monotonic so the sorted arrangement dominates

Choose another pattern when

Rows must keep their original character order → it's a pure verification, no sorting allowed
You can permute columns too → a different (harder) matching problem
Cells carry weights and you optimise a sum → not a yes/no feasibility check
The monotonic direction differs per column → re-derive whether a single sort suffices

Interview takeaway

When each row can be permuted independently and you need columns to be sorted, the greedy normal form is 'sort every row ascending'. The exchange argument proves it dominates every other per-row arrangement — a clean example of reducing a search over permutations to a single canonical choice.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternGreedy normalisation under per-row freedom: when each row can be permuted independently and you must satisfy a cross-row monotonic property, sorting every row ascending is the dominating canonical arrangement. Prove it with a bubble-swap exchange argument, then the problem reduces to a single column-monotonicity scan.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Anagram
Coming soon
Sorting-as-normalisation appears again: sort both strings and compare.
Group Anagrams
Coming soon
Use the sorted form of each string as a canonical key.
Minimum Number of Swaps to Sort
Coming soon
Quantify how far a row is from sorted instead of just sorting it.
Set Matrix Zeroes
Coming soon
Another row/column coupling problem on a 2-D grid.

Same pattern

←

Greedy Florist

Continue · Next problem

Jim and the Orders

easyGreedySometimes asked

Grid Challenge

Greedy Algorithms · 18 of 23 · 8 min

1
Each row is sorted in non-decreasing (ascending) order, and
2
Each column is sorted in non-decreasing (top-to-bottom) order.

You may rearrange the characters within each row in any order, but you may not move characters between rows. Return "YES" if such an arrangement exists, otherwise "NO".

In plain English

Examples

Example 1

Input: grid = ["ebacd", "fghij", "olmkn", "trpqs", "xywuv"]
Output: YES
Note: Sort each row → ["abcde", "fghij", "klmno", "pqrst", "uvwxy"]. Every column reads top-to-bottom as a,f,k,p,u … all non-decreasing.

Example 2

Input: grid = ["abc", "ade", "efg"]
Output: YES
Note: Rows already ascending. Columns: (a,a,e), (b,d,f), (c,e,g) — each non-decreasing → YES.

Example 3

Input: grid = ["zyx", "wvu"]
Output: NO
Note: Sort each row → ["xyz", "uvw"]. Column 0 is (x,u): u < x, so it decreases → NO.

Constraints

1 ≤ n ≤ 100 (number of rows)
Each row has the same length m (1 ≤ m ≤ 100)
All characters are lowercase English letters 'a'–'z'

Clarifying questions4First question: Can I rearrange characters across different rows?Explore questions

Q1.Can I rearrange characters across different rows?
No. Reordering is allowed only within a row. Characters stay in their original row.
Q2.Do rows have to be sorted, or just the columns?
Both. But because we control the row order completely, satisfying 'rows ascending' is free — sort them. The columns are what may or may not work out.
Q3.Is the grid always square?
The classic version is n × n, but the algorithm works for any n × m: sort each length-m row, then check the columns.
Q4.Are characters case-sensitive or include non-letters?
All lowercase English letters, so a direct character (ASCII) comparison is enough.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise sorting each row independently is not just a heuristic but provably optimal for making the columns sortable, and whether you implement the column check correctly.

Where candidates slip

Sorting the whole grid or sorting columns, or only checking adjacent characters within rows instead of verifying the columns after sorting.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Per-Row Permutation	`O((m!)ⁿ · n · m)`	`O(n · m)`	Mention it to expose the search space, then collapse it with the 'sort each row' lemma.	Read
2	Greedy — Sort Each Row Ascending, Then Check Columns (Optimal)Optimal	`O(n · m log m)`	`O(n · m)`	The answer they want. Phrase it as 'sort every row, then a single pass verifies the columns'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Per-Row Permutation

TimeO((m!)ⁿ · n · m)SpaceO(n · m)

Mention it to expose the search space, then collapse it with the 'sort each row' lemma.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each row can be permuted in m! ways. A full arrangement is one permutation per row — how many combinations is that across n rows?

2Hint 2Explore hint

Enumerate every combination of per-row permutations, then check whether all columns are non-decreasing. Return YES if any combination works.

3Hint 3Explore hint

This is astronomically large — (m!)ⁿ. It's only useful to argue that we don't need it: a single canonical permutation (sort ascending) suffices.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

grid = ["ba", "dc"]

[ba, dc]

col0 (b,d) ok, col1 (a,c) ok

Statevalid → YES

Final resultYES (and the all-ascending arrangement is one of the valid witnesses)

C · Code with teaching comments

solution.javaJava

Brute Force — Try Every Per-Row Permutation — reference

2 teaching notes

1
public String gridChallenge(List<String> grid) {
2
    int n = grid.size();
3
    char[][] rows = new char[n][];
4
    for (int i = 0; i < n; i++) {
5
        rows[i] = grid.get(i).toCharArray();
6
    }
7
    return search(rows, 0) ? "YES" : "NO";
8
}
9
 
10
private boolean search(char[][] rows, int r) {
11
    if (r == rows.length) {
12
        for (int j = 0; j < rows[0].length; j++) {
13
            for (int i = 1; i < rows.length; i++) {
14
                // A column that decreases anywhere disqualifies this arrangement.
15
                if (rows[i][j] < rows[i - 1][j]) return false;
16
            }
17
        }
18
        return true;
19
    }
20
    // Generate all permutations of row r, recursing to the next row for each.
21
    return permuteRow(rows, r, 0);
22
}
23
 
24
private boolean permuteRow(char[][] rows, int r, int start) {
25
    if (start == rows[r].length) return search(rows, r + 1);
26
    for (int i = start; i < rows[r].length; i++) {
27
        char t = rows[r][start]; rows[r][start] = rows[r][i]; rows[r][i] = t;
28
        if (permuteRow(rows, r, start + 1)) return true;
29
        t = rows[r][start]; rows[r][start] = rows[r][i]; rows[r][i] = t;
30
    }
31
    return false;
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO((m!)ⁿ · n · m) timeO(n · m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3(m!)ⁿ blow-up — only runs for tiny grids; it's a thought experiment.Explore edge cases

Pitfalls

(m!)ⁿ blow-up — only runs for tiny grids; it's a thought experiment.
Forgetting characters stay within their original row.
Checking rows for sortedness but not the columns — the columns are the real test.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort Each Row Ascending, Then Check Columns (Optimal)

TimeO(n · m log m)SpaceO(n · m)

The answer they want. Phrase it as 'sort every row, then a single pass verifies the columns'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Rows can be freely permuted, so satisfying 'rows ascending' costs nothing — just sort them. What's left to verify?

2Hint 2Explore hint

After sorting each row ascending, the only thing that can still fail is a column decreasing somewhere. Check each column top to bottom.

3Hint 3Explore hint

If every adjacent pair grid[i][j] >= grid[i-1][j] holds for all columns, return YES; the first violation returns NO.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

grid = ["ebacd", "fghij", "olmkn", "trpqs", "xywuv"]

Array state

i=1

f ≥ a ✓

[0]

i ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Greedy — Sort Each Row Ascending, Then Check Columns (Optimal) — optimal

4 teaching notes

1
public String gridChallenge(List<String> grid) {
2
    int n = grid.size();
3
    char[][] rows = new char[n][];
4
    for (int i = 0; i < n; i++) {
5
        rows[i] = grid.get(i).toCharArray();
6
        // Sort each row ascending — the free, canonical arrangement of its characters.
7
        Arrays.sort(rows[i]);
8
    }
9
    int m = rows[0].length;
10
    // Outer loop walks each column independently.
11
    for (int j = 0; j < m; j++) {
12
        for (int i = 1; i < n; i++) {
13
            // A single top-to-bottom decrease means no valid arrangement exists.
14
            if (rows[i][j] < rows[i - 1][j]) {
15
                // Fail fast on the first violating column.
16
                return "NO";
17
            }
18
        }
19
    }
20
    return "YES";
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n · m log m) timeO(n · m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6single row ["cba"] — Sort to "abc"; with one row there are no column comparisons → YES.Explore edge cases

Edge cases handled

single row ["cba"]Sort to "abc"; with one row there are no column comparisons → YES.
single column ["b", "a"]Rows sort trivially; column reads b,a which decreases → NO.
all identical letters ["aa", "aa"]Sorting is a no-op; every column is constant (non-decreasing) → YES.

Pitfalls

Sorting the entire flattened grid instead of each row separately.
Checking only rows after sorting and forgetting the column scan.
Comparing non-adjacent rows — adjacent comparisons already cover the whole column by transitivity.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the column verification

Sorting rows satisfies only the row requirement. Without the column scan, a grid like ["zyx","wvu"] would be wrongly accepted.

Explore the code comparison

Don't write this

rows = [sorted(row) for row in grid]
return "YES"

Write this instead

rows = [sorted(row) for row in grid]
for j in range(len(rows[0])):
    for i in range(1, len(rows)):
        if rows[i][j] < rows[i - 1][j]:
            return "NO"
return "YES"

Sorting the grid as one flat list

Characters may only move within their own row. Flattening and sorting the whole grid moves characters across rows, which is illegal.

Explore the code comparison

Don't write this

char[] all = String.join("", grid).toCharArray();
Arrays.sort(all);
// reshape and check — WRONG: characters crossed row boundaries

Write this instead

for (int i = 0; i < n; i++) {
    rows[i] = grid.get(i).toCharArray();
    Arrays.sort(rows[i]);
}

Comparing within a row instead of down a column

After sorting, rows are trivially non-decreasing. The real condition couples rows together, so you must compare grid[i][j] against grid[i-1][j] down each column.

Explore the code comparison

Don't write this

for row in rows:
    for j in range(1, len(row)):
        if row[j] < row[j - 1]:
            return "NO"

Write this instead

for j in range(len(rows[0])):
    for i in range(1, len(rows)):
        if rows[i][j] < rows[i - 1][j]:
            return "NO"

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy normalisation: sort each row ascending, then verify columns

Code pattern to memorize

for each row: sort its characters ascending
for each column j:
    for each row i from 1:
        if grid[i][j] < grid[i-1][j]: return "NO"
return "YES"

Rules to remember

1Sort the letters within each row ascending — rows may be freely rearranged, that's the whole point.
2After sorting rows, the columns must be non-decreasing top to bottom; check grid[i][j] >= grid[i-1][j].
3You may NOT reorder rows or columns as units — only the characters inside each row.
4Sorting each row ascending is the unique best try: if any arrangement sorts the columns, the all-rows-ascending one does too.
5Compare characters directly (lexicographic / ASCII). All-lowercase input means a plain char comparison works.

Use this pattern when

Each row/group can be internally reordered and you must satisfy a cross-group monotonic property
A 2-D feasibility check where rows are independent but columns couple them
You suspect 'sort each part, then verify the global condition' collapses the search
The condition is monotonic so the sorted arrangement dominates

Choose another pattern when

Rows must keep their original character order → it's a pure verification, no sorting allowed
You can permute columns too → a different (harder) matching problem
Cells carry weights and you optimise a sum → not a yes/no feasibility check
The monotonic direction differs per column → re-derive whether a single sort suffices

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Anagram
Coming soon
Sorting-as-normalisation appears again: sort both strings and compare.
Group Anagrams
Coming soon
Use the sorted form of each string as a canonical key.
Minimum Number of Swaps to Sort
Coming soon
Quantify how far a row is from sorted instead of just sorting it.
Set Matrix Zeroes
Coming soon
Another row/column coupling problem on a 2-D grid.

Same pattern

←

Greedy Florist

Continue · Next problem

Jim and the Orders