Four-by-Four Boundary Grid
Susquehanna International Group (SIG)● MediumFULLTIMEOAProblem statement
Fill a 4 x 4 grid with values from 1 through 4. For this exercise, assume every row and every column contains each value exactly once. There are no additional 2 x 2 box constraints.
The values represent heights. Looking along a row or column from an edge, a height is visible only when it is larger than every height before it.
You receive a 4 x 4 matrix clues:
clues[0][c]is the number visible in columncfrom the top.clues[1][r]is the number visible in rowrfrom the right.clues[2][c]is the number visible in columncfrom the bottom.clues[3][r]is the number visible in rowrfrom the left.- A clue of
0imposes no condition. Row indices always run from top to bottom; column indices always run from left to right, including bottom and right clues.
Return the lexicographically smallest valid grid, comparing its values in row-major order. If no grid satisfies every nonzero clue, return an empty matrix [].
Function
solveBoundaryGrid(clues: int[][]) → int[][]Examples
Example 1
clues = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]return = [[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,2,1]]No boundary imposes a condition. The lexicographically first Latin grid is selected; no 2 x 2 box rule is applied.
Example 2
clues = [[2,2,3,1],[1,3,3,2],[3,2,1,2],[3,1,2,3]]return = [[2,3,1,4],[4,1,3,2],[3,4,2,1],[1,2,4,3]]All four sides constrain the grid. Each boundary entry is checked from its stated viewing direction.
Example 3
clues = [[1,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]return = []Both first two columns would have to begin with 4, which repeats 4 in the first row, so no grid exists.
Constraints
clues.length = 4and every row ofclueshas length4.0 <= clues[s][i] <= 4.- Clues may be incomplete or inconsistent.