# #10 Array: Spiral Traverse

###### tags:`Array` `Medium`

<br>

## Issue


## Solutions

### Official

:::spoiler Solution 1
<br />

// O(n) time | O(n) space where n is the total number of elements in the array
function spiralTraverse (array) {
    const result = [];
    let startRow = 0, endRow = array.length - 1;
    let startCol = 0, endCol = array[0].length - 1;

    while (startRow <= endRow && startCol <= endCol) {
        for (let col = startCol; col <= endCol; col++) {
            result.push(array[startRow][col]);
        }

        for (let row = startRow + 1; row <= endRow; row++) {
            result.push(array[row][endCol]);
        }

        for (let col = endCol - 1; col >= startCol; col--) {
            // Handle the edge case when there's a single row
            // in the middle of the matrix. In this case, we don't
            // want to double-count the values in this row, which
            // we've already counted in the first for loop above.
            // See Test Case 8 for an example of this edge case.
            
            if (startRow === endRow) break;
            result.push(array[endRow][col]);
        }

        for (let row = endRow - 1; row > startRow; row--) {
            // Handle the edge case when there's a single column
            // in the middle of the matrix. In this case, we don't
            // want to double-count the values in this column, which
            // we've already counted in the second for loop above.
            // See Test Case 9 for an example of this edge case.
            
            if (startCol === endCol) break;
            result.push(array[row][startCol]);
        }

        startRow++;
        endRow--;
        startCol++;
        endCol--;
    }

    return result;
}

**Test case 8 mentioned above**

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

**Test case 9 mentioned above**

[
    [1, 2, 3],
    [12, 13, 4],
    [11, 14, 5],
    [10, 15, 6],
    [9, 8, 7]
]

* Third `for-loop` in second round of `while-loop` would run no round for conditional `!col >= startCol`

* Forth `for-loop` in second round of `while-loop` needs conditional `startCol === endCol` to break

**Employ some conditionals to deal with edge cases**

* Conditional `row > startRow` of forth `for-loop` to determine whether to keep iterating (without `===` like conditionals of other `for-loop`)
* Conditional `startRow === endRow` to break third`for-loop`
* Conditional `startCol === endCol` to break forth`for-loop`

:::

<br />

:::spoiler Solution 2
<br />

// O(n) time | O(n) space - where n is the total number of elements in the array
function spiralTraverse (array) {
    const result = [];
    spiralFill(array, 0, array.length - 1, 0, array[0].length - 1, result);
    return result;
}

function spiralFill(array, startRow, endRow, startCol, endCol, result) {
    if (startRow > endRow || startCol > endCol) return;

    for (let col = startCol; col <= endCol; col++) {
        result.push(array[startRow][col]);
    }
    
    for (let row = startRow + 1; row <= endRow; row++) {
        result.push(array[row][endCol]);
    }

    for (let col = endCol - 1; col >= startCol; col--) {
        // Handle the edge case when there's a single row
        // in the middle of the matrix. In this case, we don't
        // want to double-count the values in this row, which
        // we've already counted in the first for loop above.
        // See Test Case 8 for an example of this edge case.
        
        if (startRow === endRow) break;
        result.push(array[endRow][col]);
    }

    for (let row = endRow - 1; row > startRow; row--) {
        // Handle the edge case when there's a single column
        // in the middle of the matrix. In this case, we don't
        // want to double-count the values in this column, which
        // we've already counted in the second for loop above.
        // See Test Case 9 for an example of this edge case.
        
        if (startCol == endCol) break;
        result.push(array[row][startCol]);
    }

    spiralFill(array, startRow + 1, endRow - 1, startCol + 1, endCol - 1, result);
}

:::

### Everyone's

:::spoiler 東

// Time O(n) | Space O(n) - where n is the total amount of elemens in the array 
function spiralTraverse(array) {
  let topBound = 0;
  let bottomBound = array.length - 1;
  let leftBound = 0;
  let rightBound = array[0].length - 1;
  const result = [];

  while(topBound <= bottomBound && leftBound <= rightBound){
    for(let hIdx = leftBound; hIdx <= rightBound; hIdx++){
      result.push(array[topBound][hIdx]);
    }
    topBound++;


    for(let vIdx = topBound; vIdx <= bottomBound; vIdx++){
      result.push(array[vIdx][rightBound]);
    }
    rightBound--;

    if(topBound > bottomBound || leftBound > rightBound) return result;

    for(let hIdx = rightBound; hIdx >= leftBound; hIdx--){
      result.push(array[bottomBound][hIdx]);
    }
    bottomBound--;


    for(let vIdx = bottomBound; vIdx >= topBound; vIdx--){
      result.push(array[vIdx][leftBound]);
    }
    leftBound++;
  }
  return result;
}

:::

<br>

:::spoiler Hao

Check if need to keep traverse spirally and conduct different `for-loop` in order

/**
 * Time complexity: O(n) where n stands for array.length
 * Space complexity: O(n) where n stands for array.length
 */

class SpiralTraversor {
    dirs = ['COL_ASC', 'ROW_ASC', 'COL_DESC', 'ROW_DESC'];
    curDirIdx = -1;
    result = [];

    constructor(array) {
        this.array = array;
        this.startCol = 0;
        this.endCol = array[0].length - 1;
        this.startRow = 0;
        this.endRow = array.length - 1;
    }

    getCurDir() {
        this.curDirIdx += 1;
        if (this.curDirIdx === this.dirs.length) this.curDirIdx = 0;

        return this.dirs[this.curDirIdx];
    }

    visit(dir) {
        switch (dir) {
            case 'COL_ASC': {
                for (let col = this.startCol; col <= this.endCol; col += 1) {
                    this.result.push(this.array[this.startRow][col]);
                }

                this.startRow += 1;
                break;
            };

            case 'ROW_ASC': {
                for (let row = this.startRow; row <= this.endRow; row += 1) {
                    this.result.push(this.array[row][this.endCol]);
                }

                this.endCol -= 1;
                break;
            };

            case 'COL_DESC': {
                for (let col = this.endCol; col >= this.startCol; col -= 1) {
                    this.result.push(this.array[this.endRow][col]);
                }

                this.endRow -= 1;
                break;
            };

            case 'ROW_DESC': {
                for (let row = this.endRow; row >= this.startRow; row -= 1) {
                    this.result.push(this.array[row][this.startCol]);
                }

                this.startCol += 1;
                break;
            };
        }
    }

    shouldKeepVisit() {
        return this.startCol <= this.endCol && this.startRow <= this.endRow;
    }

    start() {
        while (this.shouldKeepVisit()) {
            this.visit(this.getCurDir());
        }
    }

    getResult() {
        return this.result;
    }
}

function spiralTraverse(array) {
    const spiralTraversor = new SpiralTraversor(array);
    spiralTraversor.start();

    return spiralTraversor.getResult();
}

:::

<br>

:::spoiler YC

/*
  time: O(n*m) - where n is the number of rows in a 2D array, m is the number of columns in a 2D array
  space: O(n*m) - where n is the number of rows in a 2D array, m is the number of columns in a 2D array
*/
function spiralTraverse(array) {
  let ans = [];
  let left = 0; 
  let right = array[0].length - 1;
  let top = 0;
  let bottom = array.length - 1;

  while(left <= right && top <= bottom){
    //top line
    for(let i = left; i <= right; i++){
      ans.push(array[top][i]);
    }
    top++;
    
    //right line
    for(let i = top; i <= bottom; i++){
      ans.push(array[i][right]);
    }
    right--;
    
    //bottom line
    if(left <= right && top <= bottom){
      for(let i = right; i >= left; i--){
        ans.push(array[bottom][i]);
      }
      bottom--;
    }

    //left line
    if(left <= right && top <= bottom){
      for(let i = bottom; i >= top; i--){
        ans.push(array[i][left]);
      }
      left++;
    }
  }
  return ans;
}

:::

<br>

:::spoiler 月薪

function spiralTraverse(array) {
    let top = 0, bottom = array.length - 1
    let left = 0, right = array[0].length - 1
    const ans = []

    while (left <= right && top <= bottom) {
        // Go Right
        for (let i = left; i <= right; i++) {
            ans.push(array[top][i])
        }
        top++
        // Go Down
        for (let i = top; i <= bottom; i++) {
            ans.push(array[i][right])
        }
        right--
        // Go Left
        for (let i = right; i >= left; i--) {
            ans.push(array[bottom][i])
        }
        bottom--
        // Go Top
        for (let i = bottom; i >= top; i--) {
            ans.push(array[i][left])
        }
        left++
    }
    return ans
}

:::

<br>

## Discussion
### Concept

**Example: Test case 9**

[
    [1, 2, 3],
    [12, 13, 4],
    [11, 14, 5],
    [10, 15, 6],
    [9, 8, 7]
]

#### Round of `for-loop` conducted

1 1 1
4 5 2
4 6 2
4 6 2
3 3 2

#### Write down the expected output in each round

// startCol, endCol, startRow, endRow
// 0, 3, 0, 3

// startCol +1 到 === endCol; 轉彎; startRow + 1; // 0, 1, 2, 3 => 1, 2, 3, 4
// 0, 3, 1, 3

// startRow +1 到 === endRow; 轉彎; endCol - 1 // 1, 2, 3 => 5, 6, 7
// 0, 2, 1, 3

// endCol - 1 到 === startCol; 轉彎; endRow - 1 // 2, 1, 0 => 8, 9 ,10
// 0, 2, 1, 2

// endRow - 1 到 === startRow; 轉彎; startCol + 1 // 2, 1 => 11, 12
// 1, 2, 1, 2

// startCol +1 到 === endCol; 轉彎; startRow + 1 // 1, 2 => 13, 14
// 1, 2, 2, 2

// startRow +1 到 === endRow; 轉彎; endCol - 1 // 2 => 15
// 1, 1, 2, 2

// endCol - 1 到 === startCol; 轉彎; endRow - 1 // 1 => 16
// 1, 1, 2, 1 => 不符, 結束