Spiral Array Output

I was asked this one during an interview and actually given a computer to develop it on. Since I suck at interviewing I wrote the slowest one humanly possible. I've coded 3 of 5 different solutions for this. Still working on the other 2 but have to start on something else. Will hopefully get back to it. The idea I have in mind should use less code and be just as fast if not faster than the offset method.

Back to Code Samples

public static class SpiralArrayOutput
{
private enum Direction : int
{
Right = 0
,Down
,Left
,Up
}

private struct Offset
{
public int Min;
public int Max;

public Offset(int min, int max)
{
this.Min = min;
this.Max = max;
}
}

//============================================================================
/// <summary>
/// Returns the values pulled from a square array in a spiral motion.
/// </summary>
/// <remarks>Speed index: 1.00. Doesn't use up a lot of memory, fast.
/// However it won't handle jagged arrays and doesn't allow the caller
/// to specify the spiral direction.</remarks>
/// <example>
/// For the following array:
/// 1, 2, 3
/// 4, 5, 6
/// 7, 8, 9
///
/// We'll receive:
/// 1, 2, 3, 6, 9, 8, 7, 4, 5
/// </example>
/// <param name="values">The square array to use.</param>
/// <returns>An array of integers pulled from the values array in a clockwise spiral.</returns>
//============================================================================
public static IEnumerable<int> UsingOffsets(int[][] values)
{
if (values == null)
{
return null;
}

List<int> result = new List<int>();

Offset horOffsets = new Offset(0, values[0].Length - 1);
Offset verOffsets = new Offset(0, values.Length - 1);

Direction curDir = Direction.Right;

while(horOffsets.Min <= horOffsets.Max || verOffsets.Min <= verOffsets.Max)
{
switch (curDir)
{
case Direction.Right:
for (int i = horOffsets.Min; i <= horOffsets.Max; i++)
{
result.Add(values[verOffsets.Min][i]);
}

verOffsets.Min++;
curDir = Direction.Down;
break;

case Direction.Down:
for (int i = verOffsets.Min; i <= verOffsets.Max; i++)
{
result.Add(values[i][horOffsets.Max]);
}
horOffsets.Max--;
curDir = Direction.Left;
break;

case Direction.Left:
for (int i = horOffsets.Max; i >= horOffsets.Min; i--)
{
result.Add(values[verOffsets.Max][i]);
}

verOffsets.Max--;
curDir = Direction.Up;
break;

case Direction.Up:
for (int i = verOffsets.Max; i >= verOffsets.Min; i--)
{
result.Add(values[i][horOffsets.Min]);
}

horOffsets.Min++;
curDir = Direction.Right;
break;
}
}

return result;
}

//============================================================================
/// <summary>
/// Returns the values pulled from a square array in a spiral motion.
/// </summary>
/// <remarks>Speed index: 1.34. But this one handles jagged arrays.</remarks>
/// <param name="values">The array to pull values from.</param>
/// <returns>An array of integers pulled from the values array in a clockwise spiral.</returns>
//============================================================================
public static IEnumerable<int> UsingOffsetsPlusJaggedCheck(int[][] values)
{
if (values == null)
{
return null;
}

List<int> result = new List<int>();

// Find the widest row.
int widestRow = 0;
foreach (int[] row in values)
{
if (row.Length > widestRow)
{
widestRow = row.Length;
}
}

// Get a quick lookup of right side offsets for the rows. This is more efficient for smaller sets. For huge sets
// we'd want to do the calculation in the direction handler. It'll slow it down, but save memory. Whatever trade-off
// you prefer.
List<int> rowRightSideOffsets = new List<int>(values.Length);
foreach (int[] row in values)
{
rowRightSideOffsets.Add(widestRow - row.Length);
}

Offset horOffsets = new Offset(0, widestRow - 1);
Offset verOffsets = new Offset(0, values.Length - 1);
int offsetRightPosition;

Direction curDir = Direction.Right;

while (horOffsets.Min <= horOffsets.Max || verOffsets.Min <= verOffsets.Max)
{
switch (curDir)
{
case Direction.Right:
if (values.Length > verOffsets.Min && values[verOffsets.Min] != null && values[verOffsets.Min].Length - rowRightSideOffsets[verOffsets.Min] > 0)
{
int maxHorizontal = horOffsets.Max - rowRightSideOffsets[verOffsets.Min];

for (int i = horOffsets.Min; i <= maxHorizontal; i++)
{
result.Add(values[verOffsets.Min][i]);
}
}

verOffsets.Min++;
curDir = Direction.Down;
break;

case Direction.Down:
if (values.Length > verOffsets.Min && values[verOffsets.Min] != null)
{
for (int i = verOffsets.Min; i <= verOffsets.Max; i++)
{
offsetRightPosition = horOffsets.Max - rowRightSideOffsets[i];

if (offsetRightPosition >= horOffsets.Min)
{
result.Add(values[i][offsetRightPosition]);
}
}
}
horOffsets.Max--;
curDir = Direction.Left;
break;

case Direction.Left:
offsetRightPosition = horOffsets.Max - rowRightSideOffsets[verOffsets.Max];

for (int i = offsetRightPosition; i >= horOffsets.Min; i--)
{
result.Add(values[verOffsets.Max][i]);
}

verOffsets.Max--;
curDir = Direction.Up;
break;

case Direction.Up:
offsetRightPosition = horOffsets.Min - rowRightSideOffsets[verOffsets.Max];

for (int i = verOffsets.Max; i >= verOffsets.Min; i--)
{
if (values[i].Length - rowRightSideOffsets[i] - horOffsets.Max >= 0)
{
result.Add(values[i][horOffsets.Min]);
}
}

horOffsets.Min++;
curDir = Direction.Right;
break;
}
}

return result;
}

//============================================================================
/// <summary>
/// </summary>
/// <remarks>Speed index: 3.766. Plus it's a memory hog. Plus it won't allow
/// setting spiral direction. Essentially evil. Had to try it.
/// </remarks>
/// <param name="values">The array to pull values from.</param>
/// <returns>An array of integers pulled from the values array in a clockwise spiral.</returns>
//============================================================================
public static IEnumerable<int> UsingNewArrayDestruction(int[][] values)
{
if (values == null)
{
return null;
}

List<int> result = new List<int>();

List<List<int>> copy = new List<List<int>>();

for (int i = 0; i < values.Length; i++ )
{
copy.Add(new List<int>(values[i].Length));
for (int j = 0; j < values[i].Length; j++)
{
copy[i].Add(values[i][j]);
}
}

Direction currentDirection = Direction.Right;

while (copy.Count > 0)
{
switch (currentDirection)
{
case Direction.Right:
if (copy[0] != null)
{
while (copy[0].Count > 0)
{
result.Add(copy[0][0]);
copy[0].RemoveAt(0);
}
}
copy.RemoveAt(0);
currentDirection = Direction.Down;
break;

case Direction.Down:
for (int i = 0; i < copy.Count; i++)
{
if (copy[i] != null)
{
result.Add(copy[i][copy[i].Count - 1]);
copy[i].RemoveAt(copy[i].Count - 1);

if (copy[i].Count == 0)
{
copy.RemoveAt(i--);
}
}
else
{
copy.RemoveAt(i--);
}
}
currentDirection = Direction.Left;
break;

case Direction.Left:
int rowToRemove = copy.Count - 1;
if (copy[rowToRemove] != null)
{
int rowOffset = copy[rowToRemove].Count - 1;

while (rowOffset >= 0)
{
result.Add(copy[rowToRemove][rowOffset]);
copy[rowToRemove].RemoveAt(rowOffset--);
}
}
copy.RemoveAt(rowToRemove);
currentDirection = Direction.Up;
break;

case Direction.Up:
for (int i = copy.Count - 1; i >= 0; i--)
{
if (copy[i] != null)
{
result.Add(copy[i][0]);
copy[i].RemoveAt(0);
if (copy[i].Count == 0)
{
copy.RemoveAt(i--);
}
}
else
{
copy.RemoveAt(i--);
}
}
currentDirection = Direction.Right;
break;
}
}

return result;
}
}

Back to Code Samples

GOOD NEWS!

My most recent contract is officially coming to an end so I'm back on the market!

This normally lasts for only 1 or 2 interviews, so if you want me, better move fast!

Use the Contact page to get me on your team!