Snail Sort – {kata} – [arrays, matrix, traversal] – (medium)

Problem

Given an n x n array, return the array elements arranged from outermost elements to the middle element, traveling clockwise.

Examples

For better understanding, follow the numbers of the next array consecutively:

array = [[1,2,3],
         [8,9,4],
         [7,6,5]]
snail(array) #=> [1,2,3,4,5,6,7,8,9]

Source

kata kyu 4: https://www.codewars.com/kata/521c2db8ddc89b9b7a0000c1

Tags

ARRAYS, MATRIX, TRAVERSAL

Methodology

The goal is to traverse the matrix in a clockwise spiral order. We start from the top-left corner and move right, then down the right edge, then left along the bottom, and finally up the left edge. We continue this process, peeling off the outer layers, until all elements have been visited.

Detailed Steps:

  1. Top Row: Extract the top row from the matrix.
  2. Right Column: Extract the last element of each remaining row (now acting as the right column).
  3. Bottom Row: Extract the bottom row from the matrix in reverse order.
  4. Left Column: Extract the first element of each remaining row (now acting as the left column) in reverse order.

Repeat the process until the matrix is empty.

Other Caveats

  1. Handle edge cases where the matrix might become empty during traversal.

Solution


def snail(matrix):
    # Initialize the result list
    result = []

    # Continue until the matrix is empty
    while matrix:
        # Take the first row
        result += matrix[0]
        matrix.pop(0)

        if not matrix:
            break

        # Take the last element from each remaining row (right column)
        for row in matrix:
            result.append(row.pop(-1))

        if not matrix:
            break

        # Take the last row in reverse order
        result += matrix[-1][::-1]
        matrix.pop(-1)

        if not matrix:
            break

        # Take the first element from each remaining row (left column) in reverse order
        for i in range(len(matrix) - 1, -1, -1):
            result.append(matrix[i].pop(0))

    return result

Explanation

  • Top Row: We start by adding the entire top row to our result and then remove that row from the matrix.
  • Right Column: For each of the remaining rows, we take the last element and add it to our result, then remove that element from the row.
  • Bottom Row: We add the entire bottom row (in reverse order) to our result and then remove that row from the matrix.
  • Left Column: For each of the remaining rows, we take the first element and add it to our result, then remove that element from the row.
  • Repeat the process until the matrix is empty.

This method ensures that we traverse the matrix in a clockwise spiral order, efficiently handling the extraction of elements layer by layer.

By Hang

Leave a Reply

Your email address will not be published. Required fields are marked *