Sparse Canvas Paint History
Reported by candidates from Figma's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Figma flagged this one in September 2023, and it looks like a drawing problem but it isn't. Strip the canvas language and it's a hash map plus two stacks. Each paint is a history entry, undo pops it and restores the old color, redo pushes it back. If you've got an OA invite for Figma, expect this kind of design-flavored simulation instead of a graph or DP puzzle. The trap is in the rules: painting the same color still counts as an entry, and a new paint wipes redo. StealthCoder sits invisibly on your screen as a safety net if you blank mid-assessment, but the logic below is short enough to hold in your head.
The problem
Maintain a sparse two-dimensional canvas while processing operations in order. [1, x, y, color] paints coordinate (x, y). [2, x, y] reads that coordinate and appends its current color to the result. [3] undoes the most recent paint that has not already been undone. [4] redoes the most recently undone paint. An unpainted coordinate has color 0. Each paint is one history entry, including a paint that writes the current color. A new paint clears the redo history. Undo or redo does nothing when its corresponding history is empty. Return all colors produced by read operations, in operation order. Function processCanvas(operations: int[][]) → int[] Examples Example 1 operations = [[2,1,1],[1,1,1,5],[2,1,1],[3],[2,1,1],[4],[2,1,1]] return = [0,5,0,5] The first read sees the default color. Painting sets the color to 5; undo removes it, and redo restores it. Example 2 operations = [[1,2,3,7],[1,2,3,9],[2,2,3],[3],[2,2,3],[3],[2,2,3]] return = [9,7,0] Successive undos reveal the earlier color and then the unpainted state. Example 3 operations = [[1,0,0,1],[3],[1,1,1,2],[4],[2,0,0],[2,1,1]] return = [0,2] The second paint clears redo history, so the later redo cannot restore the first coordinate. Constraints 1 <= operations.length <= 200000. -10^9 <= x, y <= 10^9. 1 <= color <= 10^9 for every paint. Every operation has exactly the fields specified by its operation code.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Keep a dictionary keyed by (x, y) that maps to the current color, with 0 as the default via get. Keep an undo stack and a redo stack. On paint, record (x, y, oldColor, newColor) on the undo stack, set the new color, and clear the redo stack. Record it even if oldColor equals newColor, because the problem says every paint is one history entry. On undo, pop the entry, restore oldColor, and push it onto redo. On redo, pop it, reapply newColor, and push it back onto undo. Both are no-ops when the stack is empty. Reads are a single dictionary lookup. Total work is O(n). The common pitfall is storing only the new color, which makes undo impossible to restore correctly, or forgetting to clear redo on a fresh paint (Example 3). Coordinates reach 10^9, so never allocate a grid. If you freeze during the live OA, StealthCoder can hand you this structure as a hedge.
StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.
You can drill Sparse Canvas Paint History cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. If you're reading this with an OA window open, you're who this was built for.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Figma's OA.
Figma reuses patterns across OAs. If you're reading this with an OA window open, you're who this was built for. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Sparse Canvas Paint History FAQ
What is the real trick in this Figma OA problem?+
It's a hash map plus undo and redo stacks. Store the old and new color in each history entry so undo can restore exactly what was there. The huge coordinate range just means you can't use an array grid. Everything else is bookkeeping.
Why does painting the same color still matter?+
The statement says each paint is one history entry, even when it writes the current color. So an undo after a redundant paint undoes that paint and changes nothing visible. If you skip recording it, your undo count drifts and later reads come out wrong.
When does redo history get cleared?+
Any new paint clears the redo stack. Example 3 shows it: paint, undo, paint again, then redo does nothing. Undo and redo themselves don't clear anything, they just move entries between the two stacks.
What complexity should I aim for with 200000 operations?+
O(n) total, with O(1) per operation. Dictionary lookups and stack push or pop are all constant time. Anything that rescans history or rebuilds the canvas on each undo will be too slow at this input size.
How do I prepare for this in 48 hours?+
Write the solution once from scratch and trace all three examples by hand. Then test edge cases: undo on empty history, redo after a new paint, repeated same-color paints, and reading unpainted coordinates. Those cover nearly every bug this problem can produce.