3963. Create Grid With Exactly One Path

EasyView on LeetCode

Array Matrix String

Time: O(m + n)

Space: O(m + n)

Problem Overview

A right and down path branches whenever a cell has both an open cell to the right and an open cell below.

Intuition

A right and down path branches whenever a cell has both an open cell to the right and an open cell below. Closing every cell under the first row, except the last column, removes those branches. From the top left the only open moves are rightward along the first row. The only down move from that row is in the last column, and from there the only open moves are downward. That is one route. Every lower row is the same pattern, a wall of hashes with a dot at the end, so that string is built once and shared. A grid with a single row is just a line of dots.

Algorithm

1Build the first row as n dots.
2When there is only one row, return that row.
3Build one wall string of length n: a hash in every column except the last, which is a dot.
4Point every later row at that same string.

Example Walkthrough

Input: m = 3, n = 3

1.The first row is three dots.
2.The shared lower row is two hashes and a final dot, so the grid is "...", "##.", "##.".
3.A down step from the first row exists only in the last column, and the path then continues down to the bottom right.

Output: ["...","##.","##."]

Common Pitfalls

•A single row has no lower row to share. Returning n dots is the whole grid, and the only path is rightward.
•A single column is a stack of dots. The only path is downward, one cell at a time.
•Opening any extra cell in a lower row, left of the last column, creates a second way down from the first row.
•The lower rows share one string because those characters never change. The first row stays a separate string of dots.

3963.cs

// Approach: Open the first row and the last column, and wall off every
// other cell. The only right-and-down route runs across the top and then
// down the right edge. Every lower row is that same wall string, so it is
// built once and shared.
// Time: O(m + n) Space: O(m + n)

public class Solution
{
    public string[] CreateGrid(int m, int n)
    {
        string[] ans = new string[m];
        ans[0] = new string('.', n);
        if (m == 1)
            return ans;

        string rest = string.Create(n, n, static (span, cols) =>
        {
            span.Fill('#');
            span[cols - 1] = '.';
        });
        for (int i = 1; i < m; i++)
            ans[i] = rest;
        return ans;
    }
}

Was this solution helpful?