Trace Path

Problem Overview

The command string fixes the shape of the route.

Intuition

The command string fixes the shape of the route. Choosing a different start cell only slides that shape around the grid. So it is enough to walk the commands from a relative origin and remember the lowest and highest row and column that the walk touches, including the start. The route fits somewhere exactly when that box is no taller than n and no wider than m.

Algorithm

1Start the row and column offsets at 0, and start every bound at 0.
2For L decrease the column, for R increase it. For D decrease the row, and for U increase it.
3Update the minimum and maximum row and column after every command.
4Return true when the row span is at most n and the column span is at most m.

Example Walkthrough

Input: n = 2, m = 3, s = "LLRU"

1. The relative positions are (0, 0), (0, -1), (0, -2), (0, -1), and (1, -1).
2. Rows run from 0 to 1, a span of 2. Columns run from -2 to 0, a span of 3.
3. Both spans fit, so a start such as row 1, column 3 stays inside.

Output: true

Common Pitfalls

• D moves the row up and U moves it down. They are not the usual compass directions.
• The start position is part of the path. A command string of one move still has two positions.
• The span is the highest offset minus the lowest, plus one. Compare that height with n.
• Trying every start cell is correct but takes n times m times the string length.

Trace Path.java

Java

// Approach: The commands fix the shape of the path, and the start cell only
// shifts that shape. Track the row and column offsets of every position,
// including the start. The path fits in the grid exactly when the row span
// is at most n and the column span is at most m.
// Complexity: O(|s|) time, O(1) extra space.
class Solution {
    public boolean isPossible(int n, int m, String s) {
        int row = 0, col = 0;
        int minRow = 0, maxRow = 0, minCol = 0, maxCol = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case 'L': col--; break;
                case 'R': col++; break;
                case 'D': row--; break;
                default: row++; break;
            }
            if (row < minRow) minRow = row;
            else if (row > maxRow) maxRow = row;
            if (col < minCol) minCol = col;
            else if (col > maxCol) maxCol = col;
        }
        return maxRow - minRow < n && maxCol - minCol < m;
    }
}

Was this solution helpful?