We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Spiral Matrix III

Difficulty: Medium

Problem Description

You start at the cell (rStart, cStart) of an rows x cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column. You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid's boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all rows * cols spaces of the grid. Return an array of coordinates representing the positions of the grid in the order you visited them.

Key Insights

  • The traversal follows a spiral pattern: right, down, left, and up repeatedly.
  • We can simulate the movement by maintaining a direction array and changing directions when boundaries are hit.
  • The grid can be considered infinite in terms of movement, allowing us to go out of bounds and come back.

Space and Time Complexity

Time Complexity: O(rows * cols)
Space Complexity: O(1) (ignoring the output space)

Solution

To solve the problem, we can use a simple simulation approach. We will maintain a list of coordinates that we visit in the order of traversal. We define possible movement directions as arrays (right, down, left, up) and iterate through the grid, adjusting our position and direction as needed. We will keep track of visited positions until we have covered all rows * cols spaces.

Code Solutions

def spiralMatrixIII(rows, cols, rStart, cStart):
    result = []
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up
    direction_index = 0
    steps = 1  # initial steps in the current direction
    total_steps = 0  # total steps taken

    while len(result) < rows * cols:
        # Each direction will have an increasing step count after two turns
        for _ in range(2):
            for _ in range(steps):
                if 0 <= rStart < rows and 0 <= cStart < cols:
                    result.append([rStart, cStart])
                # Move in the current direction
                rStart += directions[direction_index][0]
                cStart += directions[direction_index][1]
                
            direction_index = (direction_index + 1) % 4  # change direction
        steps += 1  # increase steps after completing two directions

    return result
← Back to All Questions