Print a given matrix in spiral form

 Problem


Given a 2D array, print it in spiral form.

Input:  {{1,    2,   3,   4},

              {5,    6,   7,   8},

             {9,   10,  11,  12},

            {13,  14,  15,  16 }}

Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 

Explanation: The output is a matrix in a spiral format. 




Input: { {1,   2,   3,   4,  5,   6},
           {7,   8,   9,  10,  11,  12},
          {13,  14,  15, 16,  17,  18}}

Expected output:
1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11

Explanation: The output is a matrix in a spiral format.


First, I considered solving this problem by defining the prescriptive rule on which direction to go and how much to go by observing the sample problem. However, I found that the code gets overly complicated if we go that path. 

I decided to think of this problem as the DPS problem where we search through the matrix in a specified direction until we reach the end before switching direction.

This made the problem much easier and I don't have to think about the corner case much.

This can be solved in $O(N * M)$ where N is the width of the matrix and M is the height of the matrix.

UPDATE (2023-03-03): solution in python


Practice statistics:
15 mins: to come up with the algorithm
28 mins: to write the code and review the code.



Comments

Post a Comment

Popular posts from this blog

Building the binary tree

Problem Given a list of child->parent relationships, build a binary tree out of it. All the element Ids inside the tree are unique.  Example:  Given the following relationships:  Child Parent IsLeft  15 20 true  19 80 true  17 20 false  16 80 false  80 50 false  50 null false  20 50 true  You should return the following tree:         50         /    \     20      80     /  \     /   \  15 17 19 16
Read more

Find the maximum number of bomb that can be detonated

  Problem You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb. The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range. You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range.  These bombs will further detonate the bombs that lie in their ranges. Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb. Input: bombs = [[2,1,3],[6,1,4]] Output: 2 Explanation: The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So...
Read more

Finding the magic index in array, A

Image
Problem A magic index in an array A [0. . .n-1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A. FOLLOW UP What if the values are not distinct?
Read more