Spiral Matrix Algorithm

Question

I'm having trouble accounting for the odd input cases in the below problem:Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

My code works on all the bigger test cases, but fails for things like

[[6,9,7]]

and I'm not sure how to construct my code to handle these inputs. Anyone have ideas?

def spiral_order(matrix)
    return nil if matrix.nil? 
    return [] if matrix.empty?
    m = matrix.length - 1
    n = matrix.first.length - 1
    start_col = start_row = 0 
    end_col = n
    end_row = m
    visited = []
    iter = 0
    until start_row > end_row && start_col > end_col
        until iter > end_col
            visited << matrix[start_row][iter]
            iter+=1
        end
        start_row += 1
        iter = start_row

        until iter > end_row
            visited << matrix[iter][end_col]
            iter += 1
        end
        end_col -= 1
        iter = end_col

        until iter < start_col
            visited << matrix[end_row][iter]
            iter-=1
        end
        end_row -= 1
        iter = end_row

        until iter < start_row 
            visited << matrix[iter][start_col]
            iter -= 1
         end
         start_col += 1
         iter = start_col
    end

    visited
end

On the [6,9,7] I'm getting a nil error on line 17. I know the entire loop runs twice (this in itself shouldn't be the case because I'm incrementing the start limits and decrementing the end limits) but I'm struggling to create code that works for both regular inputs and the strange cases without throwing in a ton of conditionals to handle more unusual cases.

Will the matrix always be square? If so I would think you could use the enumeration options on array. For the following steps, print the value then delete/pop so that it is not used. 1) Values of top row 2) last item in each array starting on index 2. 3) bottom array using reverse_each 4) first item of each in reverse. — whodini9, Feb 20 '17 at 22:27
You're close. You need to add checks so that whenever you decrease the size of either dimension to zero (start_col == end_col, start_row == end_row) you break from the outer loop immediately. At present your code keeps trying to add elements that shouldn't be added. — Gene, Feb 20 '17 at 22:53
@Gene when end_row == start_row, that means that all elements outside of this final row have been visited. But if there's a differential between top_col and end_col, don't the elements in this column still have to be visited? That's what I thought.. so I didn't include that break statement — segue_segway, Feb 21 '17 at 03:05
Possible duplicate of [Matrix and algorithm "spiral"](http://stackoverflow.com/questions/8757514/matrix-and-algorithm-spiral) — m69's been on strike for years, Feb 21 '17 at 03:27
Sorry should have `start_col > end_col` and `start_row > end_row`. E.g. in your "bad" example, after you've visited the "top" row, which in this case is the only row, `start_row` is incremented, so `start_row > end_row`, which means you _should_ be done. The current algorithm doesn't stop, so it ultimately attempts to visit elements it shouldn't. — Gene, Feb 21 '17 at 03:31
If someone in this discussion down voted my answer I would appreciate an explanation. — moveson, Feb 21 '17 at 14:12
@Gene --> What's a good way to do that where I'm not sprinkling my code with a ton of conditionals? I get your point--that some loops are being accessed when they shouldn't be. I put that condition in the outer "until" loop, but how do I insert that condition in the code after each loop in a clean way? If you post your answer (and it works!) I'll certainly mark it. — segue_segway, Feb 21 '17 at 18:29
@Sunny thanks for letting me know. Is there a reason you don't want to use the code I suggested? It does everything you need and includes *no* conditionals. — moveson, Feb 21 '17 at 21:38

moveson · Answer 1 · 2017-02-22T21:33:40.190

This can be addressed using a much simpler set of code. Strip the top row from the matrix, rotate the matrix, repeat until empty.

def spiral_order(matrix)
  m = matrix.dup
  result = []
  until m.size < 1
    result << m.shift
    m = m.transpose.reverse
  end
  result.flatten
end

>> matrix = [[1,2,3],[4,5,6],[7,8,9]]
>> spiral_order(matrix)
=> [1, 2, 3, 6, 9, 8, 7, 4, 5]

>> matrix = [[6,9,7]]
>> spiral_order(matrix)
=> [6, 9, 7]

If you are working with large matrices and want to avoid multiple duplications, for a bit of added complexity you can do this:

def spiral_order(matrix)
  m = matrix.map(&:dup)
  result = []
  until m.size < 1
    result << m.shift
    result << m.map(&:pop)
    result << (m.pop || []).reverse
    result << m.map(&:shift).reverse
  end
  result.flatten.compact
end

The algorithm works like this: Line 2 deep-duplicates the matrix so the original passed in is untouched. Line 5 strips off the top row. Line 6 strips off the right column. Line 7 strips off the bottom row and reverses it. (The || [] ensures we don't call #reverse on a nil value.) Line 8 strips off the left column and reverses it. Lines 5-8 are repeated until the matrix is empty. At that point, Line 10 removes internal arrays and nils and returns the result.

I modified slightly to avoid mutating the matrix passed to the method. This algorithm works regardless of the dimensions and returns `[]` when passed an empty matrix `[[]]`. — moveson, Feb 20 '17 at 22:59

Spiral Matrix Algorithm

1 Answers1