Zigzag Traverse

Tags

Zigzag Traverse

Category

Arrays

Difficulty

Hard

Problem Statement

Given a two-dimensional array (not necessarily square), traverse it in a zigzag (diagonal) order and return the elements as a one-dimensional list. The traversal starts at the top-left corner, moves diagonally down-left, then diagonally up-right, alternating direction with each diagonal, collecting all elements.

Intuition

The zigzag pattern alternates between moving diagonally down-left and diagonally up-right. At each boundary (top row, bottom row, left column, right column), we change direction. The trick is correctly handling the boundary transitions: when we hit a wall, we need to determine the next starting position for the opposite diagonal direction. The direction flips each time we reach a boundary.

Approach

  1. Start at position (0, 0) and set the initial direction to "going down."
  2. At each step, add the current element to the result.
  3. Determine the next position based on the current direction:
    • Going down (down-left diagonal): move to (row+1, col-1).
    • Going up (up-right diagonal): move to (row-1, col+1).
  4. Handle boundary conditions to adjust position and flip direction:
    • Going down and hit the bottom row: move right (col+1), flip direction.
    • Going down and hit the left column: move down (row+1), flip direction.
    • Going up and hit the right column: move down (row+1), flip direction.
    • Going up and hit the top row: move right (col+1), flip direction.
  5. Continue until all elements are visited.

Pseudocode

function zigzagTraverse(array):
    height = length(array) - 1
    width = length(array[0]) - 1
    result = []
    row = 0
    col = 0
    goingDown = true

    while row >= 0 and row <= height and col >= 0 and col <= width:
        result.append(array[row][col])

        if goingDown:
            if col == 0 or row == height:
                goingDown = false
                if row == height:
                    col++
                else:
                    row++
            else:
                row++
                col--
        else:
            if row == 0 or col == width:
                goingDown = true
                if col == width:
                    row++
                else:
                    col++
            else:
                row--
                col++

    return result

Time & Space Complexity

  • Time: O(n) where n is the total number of elements in the 2D array. Each element is visited exactly once.
  • Space: O(n) for the output array. The traversal itself uses O(1) auxiliary space.

Key Insights

  • The order of boundary checks matters. When at a corner (e.g., bottom-left), the row boundary takes priority over the column boundary for "going down," and vice versa for "going up."
  • There are only two directions, and each direction has exactly two boundary conditions to handle.
  • This pattern generalizes to any rectangular matrix, not just square ones.

Edge Cases

  • Single row matrix: the result is just the row in order.
  • Single column matrix: the result is just the column in order.
  • Single element matrix: return that single element.
  • 1xN or Nx1 matrices: the zigzag degenerates into a simple linear traversal.
  • Non-square matrices: boundary conditions must account for different heights and widths.

Linked mentions