Place Pieces on a Grid
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given integers `n` and `m`, and an ordered list `figures` where each element is one of `"A"`, `"B"`, `"C"`, `"D"`, or `"E"`, construct an `n x m` integer matrix `grid`.
The grid starts with all values equal to `0`.
Each figure has a fixed shape described by a binary matrix, where `1` means the figure occupies that cell and `0` means empty space:
- `A = [[1]]`
- `B = [[1, 1, 1]]`
- `C = [[1, 1], [1, 1]]`
- `D = [[1, 0], [1, 1], [1, 0]]`
- `E = [[0, 1, 0], [1, 1, 1]]`
Process the figures in the given order. For the figure at index `i`:
1. Try all possible top-left placement positions in row-major order: `(0, 0)`, `(0, 1)`, ..., `(0, m - 1)`, `(1, 0)`, ... .
2. A placement is valid if every `1` cell of the figure:
- stays within the bounds of the grid, and
- overlaps only cells that are currently `0`.
3. Place the figure at the first valid position.
4. Fill every occupied cell of that placed figure with the value `i + 1`.
5. If the figure cannot be placed anywhere, skip it and leave the grid unchanged.
Return the final `grid`.
Figures cannot be rotated or reflected.
Quick Answer: This question evaluates spatial reasoning, matrix and array manipulation, collision detection, and stateful simulation skills required to implement ordered placement of shaped pieces on a grid.
Given integers n and m, and an ordered list figures where each element is one of "A", "B", "C", "D", or "E", construct an n x m integer matrix grid.
The grid starts filled with 0.
Each figure has a fixed shape:
- A = [[1]]
- B = [[1, 1, 1]]
- C = [[1, 1], [1, 1]]
- D = [[1, 0], [1, 1], [1, 0]]
- E = [[0, 1, 0], [1, 1, 1]]
Process the figures in the given order. For the figure at index i:
1. Try every top-left placement position in row-major order: (0, 0), (0, 1), ..., (0, m - 1), (1, 0), ... .
2. A placement is valid if every cell marked 1 in the figure stays inside the grid and overlaps only cells that are currently 0.
3. Place the figure at the first valid position.
4. Fill each occupied cell of that figure with the value i + 1.
5. If the figure cannot be placed anywhere, skip it.
Figures cannot be rotated or reflected. Return the final grid.
Constraints
- 1 <= n, m <= 100
- 0 <= len(figures) <= 1000
- Each element of figures is one of "A", "B", "C", "D", or "E"
Examples
Input: (3, 4, ["B", "A", "C"])
Expected Output: [[1, 1, 1, 2], [3, 3, 0, 0], [3, 3, 0, 0]]
Explanation: B is placed first at (0,0), A then fits at (0,3), and C fits next at (1,0).
Input: (2, 2, ["E", "A", "C"])
Expected Output: [[2, 0], [0, 0]]
Explanation: E cannot fit in a 2x2 grid, so it is skipped. A is the figure at index 1, so it writes value 2 at (0,0). C cannot be placed afterward because it would overlap that cell.
Input: (1, 3, [])
Expected Output: [[0, 0, 0]]
Explanation: There are no figures to place, so the grid remains all zeros.
Input: (4, 5, ["D", "E", "B", "A"])
Expected Output: [[1, 4, 0, 2, 0], [1, 1, 2, 2, 2], [1, 3, 3, 3, 0], [0, 0, 0, 0, 0]]
Explanation: D is placed at (0,0), E at (0,2), B at (2,1), and A takes the first remaining empty cell at (0,1).
Input: (3, 3, ["A", "A", "A", "B"])
Expected Output: [[1, 2, 3], [4, 4, 4], [0, 0, 0]]
Explanation: The three A pieces fill the top row from left to right, then B fits across the second row.
Hints
- Store each figure as a small set of occupied offsets (relative row and column positions) along with its height and width.
- For each figure, scan the grid from top-left to bottom-right and stop immediately when you find the first valid placement.