Daily bit(e) of C++ | Spiral traversal
Daily bit(e) of C++ #189, Common interview problem: Spiral traversal.
Today we will look at a common C++ interview problem: Spiral traversal.
Given a grid of size m*n as std::vector<std::vector<int>>, return the elements of this grid in spiral traversal order.
That is, starting at row zero, column zero, repeat until all grid elements are traversed:
advance over columns
advance over rows
descend over columns
descend over rows
Note that the elements are numbered in order of traversal for demonstrative purposes only.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/rEv5bMz9v.
Solution
This problem is fairly straightforward but does require careful implementation.
Consider that once we complete one section of the traversal, we will never re-visit the corresponding row or column.
We can therefore achieve the spiral traversal by keeping track of the lower and upper bounds for the still-to-be-traversed rows and columns. Once we traverse one section of the spiral, we adjust the corresponding bound, ensuring the following traversal sections avoid this row or column.
