FastPrepSpiral Order with Obstacles

Spiral Order with Obstacles

Temu logoTemu● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

You are given a nonempty rectangular integer matrix matrix. A cell containing -1 is an obstacle; every other cell contains a value to visit.

Start at matrix[0][0] facing right. Append the current cell's value to the output. Before every move:

  • Continue in the current direction when the next cell is inside the matrix, is not an obstacle, and has not been visited.
  • Otherwise, rotate clockwise and test the next direction. Rotate at most four times for one move.

The input guarantees that matrix[0][0] is not an obstacle and that this rule reaches every non-obstacle cell exactly once. Return the values in visit order.

Function

spiralOrderWithObstacles(matrix: int[][]) → int[]

Examples

Example 1

matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]return = [1,2,3,4,8,12,11,10,9,5,6,7]

Without obstacles, the walk follows the ordinary clockwise outer layer and then the remaining inner cells.

Example 2

matrix = [[1,2,3,4],[5,6,-1,7],[8,9,10,11],[12,13,14,15]]return = [1,2,3,4,7,11,15,14,13,12,8,5,6,9,10]

The center obstacle forces additional right turns before the walk reaches 9 and 10.

Example 3

matrix = [[1,-1,7],[2,-1,6],[3,4,5]]return = [1,2,3,4,5,6,7]

The first attempted right move is blocked, so the walk rotates downward and reaches the right column from below.

Constraints

  • 1 <= matrix.length and 1 <= matrix[0].length.
  • matrix is rectangular.
  • matrix.length * matrix[0].length <= 100000.
  • -10^9 <= matrix[r][c] <= 10^9.
  • -1 denotes an obstacle and is not used as a visitable value.
  • matrix[0][0] != -1.
  • The clockwise walk reaches every non-obstacle cell exactly once.

More Temu problems

See Temu hiring insights
public int[] spiralOrderWithObstacles(int[][] matrix) {
    // Write your code here.
}
matrix[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
expected[1,2,3,4,8,12,11,10,9,5,6,7]
Checking account…