Spiral Matrix

Hard Matrix

Return all elements of a matrix in spiral order by walking the shrinking top, right, bottom and left boundaries.

Sample input

[[1,2,3],[4,5,6],[7,8,9]]

Sample output

1 2 3 6 9 8 7 4 5

Solution

def spiral_order(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        if top <= bottom:
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    return result

print(*spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))

function spiralOrder(matrix) {
  const result = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let j = left; j <= right; j++) result.push(matrix[top][j]);
    top++;
    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
    right--;
    if (top <= bottom) {
      for (let j = right; j >= left; j--) result.push(matrix[bottom][j]);
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
      left++;
    }
  }
  return result;
}

console.log(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]).join(" "));

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
    static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) result.add(matrix[top][j]);
            top++;
            for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) result.add(matrix[bottom][j]);
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
                left++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(spiralOrder(matrix).stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

fun spiralOrder(matrix: Array<IntArray>): List<Int> {
    val result = mutableListOf<Int>()
    var top = 0
    var bottom = matrix.size - 1
    var left = 0
    var right = matrix[0].size - 1
    while (top <= bottom && left <= right) {
        for (j in left..right) result.add(matrix[top][j])
        top++
        for (i in top..bottom) result.add(matrix[i][right])
        right--
        if (top <= bottom) {
            for (j in right downTo left) result.add(matrix[bottom][j])
            bottom--
        }
        if (left <= right) {
            for (i in bottom downTo top) result.add(matrix[i][left])
            left++
        }
    }
    return result
}

fun main() {
    val matrix = arrayOf(intArrayOf(1, 2, 3), intArrayOf(4, 5, 6), intArrayOf(7, 8, 9))
    println(spiralOrder(matrix).joinToString(" "))
}

func spiralOrder(_ matrix: [[Int]]) -> [Int] {
    var result = [Int]()
    var top = 0, bottom = matrix.count - 1
    var left = 0, right = matrix[0].count - 1
    while top <= bottom && left <= right {
        var j = left
        while j <= right { result.append(matrix[top][j]); j += 1 }
        top += 1
        var i = top
        while i <= bottom { result.append(matrix[i][right]); i += 1 }
        right -= 1
        if top <= bottom {
            j = right
            while j >= left { result.append(matrix[bottom][j]); j -= 1 }
            bottom -= 1
        }
        if left <= right {
            i = bottom
            while i >= top { result.append(matrix[i][left]); i -= 1 }
            left += 1
        }
    }
    return result
}

print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]).map(String.init).joined(separator: " "))

List<int> spiralOrder(List<List<int>> matrix) {
  final result = <int>[];
  int top = 0, bottom = matrix.length - 1;
  int left = 0, right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (var j = left; j <= right; j++) result.add(matrix[top][j]);
    top++;
    for (var i = top; i <= bottom; i++) result.add(matrix[i][right]);
    right--;
    if (top <= bottom) {
      for (var j = right; j >= left; j--) result.add(matrix[bottom][j]);
      bottom--;
    }
    if (left <= right) {
      for (var i = bottom; i >= top; i--) result.add(matrix[i][left]);
      left++;
    }
  }
  return result;
}

void main() {
  print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]).join(' '));
}

#include <iostream>
#include <vector>
using namespace std;

vector<int> spiralOrder(const vector<vector<int>>& matrix) {
    vector<int> result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) result.push_back(matrix[top][j]);
        top++;
        for (int i = top; i <= bottom; i++) result.push_back(matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) result.push_back(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) result.push_back(matrix[i][left]);
            left++;
        }
    }
    return result;
}

int main() {
    vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    vector<int> res = spiralOrder(matrix);
    for (int i = 0; i < (int) res.size(); i++) {
        cout << res[i];
        if (i < (int) res.size() - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

#include <stdio.h>

int main() {
    int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int rows = 3, cols = 3;
    int top = 0, bottom = rows - 1, left = 0, right = cols - 1;
    int first = 1;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) {
            if (!first) printf(" ");
            printf("%d", matrix[top][j]);
            first = 0;
        }
        top++;
        for (int i = top; i <= bottom; i++) {
            if (!first) printf(" ");
            printf("%d", matrix[i][right]);
            first = 0;
        }
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                if (!first) printf(" ");
                printf("%d", matrix[bottom][j]);
                first = 0;
            }
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                if (!first) printf(" ");
                printf("%d", matrix[i][left]);
                first = 0;
            }
            left++;
        }
    }
    printf("\n");
    return 0;
}