Zigzag Board Adjacent Swaps
Uber● HardFULLTIMEPHONE SCREENProblem statement
An n x n board contains every integer from 1 through n^2 exactly once. The target board lists values in increasing zigzag row order: left to right on row 0, right to left on row 1, and so on.
Use the zigzag cells themselves as one path. For each target path position from first to last, locate its required value later on the path and repeatedly swap it with the preceding path cell until it reaches the target position.
Return the resulting deterministic swap sequence. Each swap is [row1, column1, row2, column2]. Consecutive path cells are always horizontally or vertically adjacent.
Function
zigzagSwaps(board: int[][]) → int[][]Examples
Example 1
board = [[1,3],[2,4]]return = [[1,0,1,1],[1,1,0,1]]Value 2 moves backward along the zigzag path from (1,0) to (1,1) and then to (0,1).
Example 2
board = [[1,2],[4,3]]return = []The board already matches increasing zigzag order.
Constraints
1 <= n = board.length = board[i].length <= 20.- The board contains every integer from
1throughn^2exactly once. - The returned sequence contains at most
n^2(n^2-1)/2swaps.