Traverse 2D Array in Spiral pattern using recursion

Question

I am preparing for an interview and have been stuck on this question for quite some time now. Could anybody please help me with the code. If not complete then may be a snippet of it? Please..

Answer 1

What the code below essentially does is that it compartmentalizes the array into layers. So, all the outer elements i.e. first row, last column, last row, and first column, would constitute the first layer. The second layer would consist of all elements immediately inner to the first layer and so on.

After experimenting with several row and column number combinations I concluded that the number of layers is given by half of the number of rows or half of the number of columns, whichever is lesser (rounding up for decimals).

Calling shell() on every layer effectively allows you to traverse and array in spiral order.

import java.util.Scanner;

//program to input elements in spiral order 
public class spiral{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("enter number of rows");
        int m = sc.nextInt();
        System.out.println("enter number of columns");
        int n = sc.nextInt();
        int arr[][] = new int[m][n];
        /*
         * recursive approach is used here
         * shell() takes input for only the outer layer of the array
         * mid stores the number of layers, which is half of the number of rows or
         * columns whichever is lesser
         * calling shell() for each layer of the array effectively returns an array in
         * spiral order
         */

        int mid = arr.length > arr[0].length ? (int) Math.ceil(arr[0].length / 2) : (int) Math.ceil(arr.length / 2);

        for (int i = 0; i < mid; i++) {
            shell(arr, i, arr[0].length - i - 1, i, arr.length - i - 1);
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        sc.close();
    }

    // iterate through first row, last column, last row and first column in order
    public static void shell(int arr[][], int col_start, int col_end, int row_start, int row_end) {
        //Here I am taking input for the array. Whatever is inside each of 
        //these loops can be manipulated. 
        for (int i = col_start; i < col_end; i++) {
            arr[row_start][i] = new Scanner(System.in).nextInt();
        }
        for (int i = row_start; i < row_end; i++) {
            arr[i][col_end] = new Scanner(System.in).nextInt();
        }
        for (int i = col_end; i > col_start; i--) {
            arr[row_end][i] = new Scanner(System.in).nextInt();
        }
        for (int i = row_end; i > row_start; i--) {
            arr[i][col_start] = new Scanner(System.in).nextInt();
        }

    }
}

Answer 2

Python 2, prints a 2D nested list in clockwise direction, from the top left corner to the center:

>>> def clockwise(r):
...     return list(r[0]) + clockwise(list(reversed(zip(*r[1:])))) if r else []
... 
>>> a = [ 
...   [ 1,  2,  3], 
...   [ 5,  6,  7], 
...   [ 9, 10, 11]]
>>> clockwise(a)
[1, 2, 3, 7, 11, 10, 9, 5, 6]
>>> a = [ 
...   [ 1,  2,  3,  4], 
...   [ 5,  6,  7,  8], 
...   [ 9, 10, 11, 12],
...   [13, 14, 15, 16]]
>>> clockwise(a)
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

So what happens here? The argument to clockwise is a two-dimensional array r. We want to print its contents from left to right, clockwise. So if the two dimensional array is not empty, then we can print it's first element, which is the top row. Next, we want to print the last elements of the remaining rows (the numbers on the right). We don't want to repeat ourselves. So what we do, is to transform the remaining rows such that the next numbers to be printed are on the top row. We do this by transposing the remaining rows (so that they become columns) and then reversing them.

Perhaps the algorithm becomes clearer if I write it in Haskell:

import Data.List

clockwise :: [[a]] -> [a] 
clockwise (x:xs) = x ++ (clockwise $ reverse $ transpose $ xs) 
clockwise _      = []