Sparse Canvas Paint History
Figma● MediumFULLTIMEPHONE SCREENProblem statement
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^9for every paint.- Every operation has exactly the fields specified by its operation code.