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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Spiral Matrix III

Number: 921

Difficulty: Medium

Paid? No

Companies: Google, Meta, Microsoft, Uber, Amazon, Dataminr

Problem Description

Given a rows x cols grid, you start at cell (rStart, cStart) facing east and need to traverse every cell in the grid by moving in a clockwise spiral pattern. Although the spiral path may temporarily go outside the grid boundaries, you must record only those positions that lie within the grid, ultimately covering all rows * cols cells.

Key Insights

  • Simulate the spiral movement by maintaining a direction (east, south, west, north) cycle.
  • The number of steps taken in a given direction increases by one after every two turns.
  • Even if the path moves outside of the grid boundaries, continue the simulation.
  • Record the coordinates when they fall within the grid until all cells have been covered.

Space and Time Complexity

Time Complexity: O(rows * cols) because each valid cell is processed, though additional moves outside the grid may occur but are bounded by a constant factor. Space Complexity: O(rows * cols) for storing the output list of coordinates.

Solution

The approach is to simulate the spiral traversal:

  1. Initialize the result list with the starting position and preset the direction sequence: east, south, west, north.
  2. Start with a step count of 1. For every two directional moves, increase the step count.
  3. For each direction, move the current step count amount of steps. After each move, check if the new position lies within the grid boundaries; if yes, add it to the result.
  4. Cycle through the four directions and continue the simulation until all grid cells are visited.
  5. The key trick is to adjust the movement pattern so that even when stepping outside the grid, the algorithm does not prematurely stop until the grid is fully covered.

Code Solutions

def spiralMatrixIII(rows, cols, rStart, cStart):
    # Initialize result with the starting position
    result = []
    result.append([rStart, cStart])
    
    # Direction vectors for east, south, west, and north respectively
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # Starting position and initial settings
    r, c = rStart, cStart
    # Steps to move in current direction, starting with 1 step
    steps = 1
    # Starting with east, index 0 in directions
    d = 0
    # Loop until all cells in the grid have been visited
    while len(result) < rows * cols:
        # For two turns, move for the current steps count
        for _ in range(2):
            # Retrieve the current direction vector
            dr, dc = directions[d]
            # Move 'steps' times in the current direction
            for _ in range(steps):
                r += dr  # Update row position
                c += dc  # Update column position
                # Check if the position is within grid boundaries
                if 0 <= r < rows and 0 <= c < cols:
                    result.append([r, c])
                # If we've visited all grid cells, return the result
                if len(result) == rows * cols:
                    return result
            # Change direction in a clockwise manner
            d = (d + 1) % 4
        # After two directions, increment the steps count
        steps += 1
    return result

# Example usage:
#print(spiralMatrixIII(5, 6, 1, 4))
← Back to All Questions