[Go] Array and string - Diagonal Traverse

My code

func findDiagonalOrder(mat [][]int) []int {
    m, n := len(mat), len(mat[0])

    result := make([]int, m*n)
    row, col, d := 0, 0, 1

    for i := 0; i < m*n; i++ {
        result[i] = mat[row][col]
        row -= d
        col += d

        if row >= m {
            row = m - 1
            col += 2
            d = -d
        }
        if col >= n {
            col = n - 1
            row += 2
            d = -d
        }
        if row < 0 {
            row = 0
            d = -d
        }
        if col < 0 {
            col = 0
            d = -d
        }

    }
    return result
}

• This code is like walking pattern.
• m will have row length and n will have column length.
• result will have size based on m*n size which is values qty.
• row and col will have 0 and d will have 1.
• d will be used as direction standard value.
• If out of bottom border (row >= m) then row = m - 1; col += 2; change walk direction.
• if out of right border (col >= n) then col = n - 1; row += 2; change walk direction.
• if out of top border (row < 0) then row = 0; change walk direction.
• if out of left border (col < 0) then col = 0; change walk direction.
• Otherwise, just go along with the current direction.
• Pattern is like this.
• when pointer is heading to right, row will decrease and column will increase.
• On the other hands,row will increase and column will decrease when pointer is heading to left.
• First is (0,0) and move to row - 1 and col +1
• But row is -1, so it needs for its direction to be changed.
• So row will be 0 and direction will be changed to opposite.
• When reach beyond left and top, it is just need to change direction and value 0.
• but when beyoud max bottom border, row will be m-1 and col + 2.
• in the same way, beyond max right border, col will be n -1 and row +2.

https://go.dev/play/p/gOud9v4ZQTD

sample 14 ms submission

func findDiagonalOrder(mat [][]int) []int {
    i, j, s:= 0, 0, 1
    width := len(mat[0])
    height := len(mat)
    length := width*height
    o := make([]int, length)
    for k := 0; k < length; k++ {
        o[k] = mat[j][i]
        i += s
        j -= s
        if s == 1 {
            if i == width {
                j += 2
                i--
                s = -1
            } else if j < 0 {
                j = 0
                s = -1
            }
        } else {
            if j == height {
                i += 2
                j--
                s = 1
            } else if i < 0 {
                i = 0
                s = 1
            }
        }
    }
    return o
}

• This code looks like somehow same with my code.
• j will be row and i will be column and s will be direction.
• width is column length and height is row length.
• length will be the total qty of values.
• o array will be made based on length.
• for loop will run until k reachs to length.
• From first If condition, when s is 1, pointer heads to the right.
• inside the if condition, when i is same with width(end of column), i will decrease -1 and row will be added by 2 and change direction.
• also else if shows that when j is less than 0, j will be 0 and direction will be changed to opposite.
• From else case of first if condition, when s is -1, pointer heads to the left.
• Inside the else condition, when j is same with height(end of row), j will decrease -1 and column will be added by 2 and change direction.
• also else if shows that when i is less then 0, i will be 0 and direction will be changed to opposite.

sample 15 ms submission

const (
    up = true
    down = false
)

func findDiagonalOrder(mat [][]int) []int {
    m := len(mat) // number of rows
    if m == 0 {
        return nil
    }
    n := len(mat[0]) // number of columns
    var i, j int // cell pointer
    dir := up
    res := []int{}
    for len(res) < m * n {
        // fmt.Println(i,j, dir)
        // capture the current cell
        res = append(res, mat[i][j])
        // move to the the next valid cell
        if dir == up {
            if valid(i-1, j+1, m, n) {
                // move diagonally up
                i--
                j++
            } else if valid(i, j+1, m, n) {
                // move right
                j++
                dir = down
            } else if valid(i+1, j, m, n) {
                // move down
                i++
                dir = down
            }
        } else {
            if valid(i+1, j-1, m, n) {
                // move diagonally down
                i++
                j--
            } else if valid(i+1, j, m, n) {
                // check down
                i++
                dir = up
            } else if valid(i, j+1, m, n) {
                // check right
                j++
                dir = up
            }
        }
    }
    return res
}

func valid(i int, j int, m int, n int) bool {
    if i < 0 || i >= m || j < 0 || j >= n {
        return false
    }
    return true
}

sample 16 ms submission

func findDiagonalOrder(mat [][]int) []int {
    if mat == nil || len(mat) == 0 {
        return []int{}
    }

    n := len(mat)
    m := len(mat[0])

    row, col := 0, 0
    direction := 1

    result := make([]int, n * m)
    r := 0

    for row < n && col < m {
        result[r] = mat[row][col]
        r++

        var newRow int
        if direction == 1 {
            newRow = row - 1 
        } else {
            newRow = row + 1
        }

        var newCol int
        if direction == 1 {
            newCol = col + 1
        } else {
            newCol = col - 1
        }

        if newRow < 0 || newRow == n || newCol < 0 || newCol == m {
            if direction == 1 {
                if col == m - 1 {
                    row += 1
                } else {
                    row += 0
                }

                if col < m - 1 {
                    col += 1
                } else {
                    col += 0
                }             
            } else {
                if row == n - 1 {
                    col += 1
                } else {
                    col += 0
                }

                if row < n - 1 {
                    row += 1
                } else {
                    row += 0
                }
            }

            direction = 1 - direction
        } else {
            row = newRow
            col = newCol
        }
    }

    return result
}

• This code handle edge case which is nill array or zero column.
• Also I don't know why m and n are swapped.
• row and col will be 0.
• direction will be 1.
• This code uses for loop until row and col are greater than n and m.
• Unlike the former example, code of allocation part is made by if condition.
• When direction is 1, it represents heading to right.
• When direction is 0, it represents heading to left.
• Second if condition checks if vewRow is less than 0 or same with maximum or vewCol is less than 0 or same with maximum.
• Based on this, if NewCol and NewRow is not normal, they will not return newRow and newCol.
• when newCol is m, it means it is beyond the array, so it checks direction first.
• when it is 1, col is m-1, it is already reached to maximum of column, so this will increase row and direction will be changed.
• Also when col is less than m-1, it will increase.

sample 19 ms submission

func findDiagonalOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return []int{}
    }
    bottom, right := len(matrix), len(matrix[0])
    retSlice := make([]int, 0, bottom*right)
    for row, column, up := 0, 0, true; ; {
        retSlice = append(retSlice, matrix[row][column])

        if (row == 0 || column == right-1) && up {
            if column < right-1 {
                column++
            } else if row < bottom-1 {
                row++
            } else {
                goto finish
            }
            up = !up
            continue
        } else if (row == bottom-1 || column == 0) && !up {
            if row < bottom-1 {
                row++
            } else if column < right-1 {
                column++
            } else {
                goto finish
            }
            up = !up
            continue
        }

        // normally do
        if up {
            row--
            column++
        } else {
            row++
            column--
        }
    }
finish:
    return retSlice
}

sample 20 ms submission & sample 6800 KB submission

func findDiagonalOrder(mat [][]int) []int {
    if mat == nil || len(mat) == 0 {
        return nil
    }
    m := len(mat)
    n := len(mat[0])
    out := []int{}
    idx := 0
    i := 0
    j := 0
    up := true
    for idx < m*n {
        out = append(out, mat[i][j])
        idx++

        if up {
            if j == n-1 {
                up = false
                i++
            } else if i == 0 {
                up = false
                j++
            }  else {
                i--
                j++
            }
        } else {

            if i == m-1 {
                up = true
                j++
            } else if j == 0 {
                up = true
                i++
            }  else {
                i++
                j--
            }

        }


    }


    return out
}

sample 21 ms submission`

func findDiagonalOrder(mat [][]int) []int {
    rows := len(mat)
    cols := len(mat[0])
    i, j := 0, 0
    var output []int

    count := 1
    for len(output) != rows*cols {
        diagonal := getDiagonal(mat, i, j)
        if count%2 != 0 {
            reverse(diagonal)
            output = append(output, diagonal...)
        } else {
            output = append(output, diagonal...)
        }

        if j != cols-1 {
            j++
        } else {
            i++
        }

        count++
    }

    return output

}

func getDiagonal(matrix [][]int, rows, cols int) []int {
    var diagonal []int
    i, j := rows, cols

    for j >= 0 && i < len(matrix) {
        diagonal = append(diagonal, matrix[i][j])
        i++
        j--
    }

    return diagonal
}

func reverse(slice []int) {
    for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
        slice[i], slice[j] = slice[j], slice[i]
    }
}

sample 22 ms submission

func findDiagonalOrder(mat [][]int) []int {
    m := len(mat)
    n := len(mat[0])

    nums := make([]int, m*n)

    dirs := [2][2]int{{-1, 1}, {1, -1}}
    dir := dirs[0]
    row, col := 0, 0

    for i := 0; i < m*n; i++ {
        nums[i] = mat[row][col]
        row, col = row+dir[0], col+dir[1]

        if col > n-1 { // right
            row, col = row+2, col-1
            dir = dirs[1]
        } else if row < 0 { // top
            row = row + 1
            dir = dirs[1]
        } else if row > m-1 { // bottom
            row, col = row-1, col+2
            dir = dirs[0]
        } else if col < 0 { // left
            col = col + 1
            dir = dirs[0]
        }
    }

    return nums
}

sample 6500 KB submission

func findDiagonalOrder(mat [][]int) []int {
    if len(mat) == 1 {
        return mat[0]
    }

    i, j := 0, 0
    result := make([]int, len(mat) * len(mat[0]))
    // direction
    up := true
    for k := 0; k < len(mat) * len(mat[0]); {
        if up {
            for i >= 0 && j < len(mat[0]) {
                result[k] = mat[i][j]
                i--
                j++
                k++
            }

            // Set i and j according to direction
            if i < 0 && j <= len(mat[0]) - 1 {
                i = 0;
            }
            if (j == len(mat[0])) {
                i+=2;
                j--;
            }
        } else {
            for j >= 0 && i < len(mat)  {
                result[k] = mat[i][j]
                i++
                j--
                k++
            }

            // Set i and j according to direction
            if j < 0 && i <= len(mat) - 1 {
                j = 0;
            }
            if (i == len(mat)) {
                j+=2;
                i--;
            }
        }
        // change direction
        up = !up
    }

    return result
}

sample 6900 KB submission

// 1 2 5 8 9 
// 3 4 1 2 5
// [1 2 3] 
// [4 5 6]
// [7 8 9]
// [0, 0]
// [1, 0], [0, 1]
// [2, 0], [1, 1], [0, 2]
// [2, 1], [1, 2]
// [2, 2]
//
// [1 5]
// [8 9]
func findDiagonalOrder(mat [][]int) []int {
    n := len(mat)
    m := len(mat[0])
    numDiagonals := n + m - 1
    ans := []int{}

    lastRow := 0
    numTimesOnLastRow := 0
    for i := 0; i < numDiagonals; i++ {
        curColumn := 0
        if lastRow == n-1 && numTimesOnLastRow >= 1 {
            curColumn += numTimesOnLastRow
        }
        curAns := []int{}
        for j := lastRow; j >= 0; j-- {
            curAns = append(curAns, mat[j][curColumn])
            curColumn++
            if curColumn >= m {
                break
            }
        }
        if i % 2 == 1 {
            reverse(curAns)
        }
        ans = append(ans, curAns...)

        lastRow += 1
        if lastRow >= n {
            lastRow = n-1
            numTimesOnLastRow += 1
        }
    }

    return ans
}

func reverse(arr []int) {
    n := len(arr)
    for i := 0; i < n / 2; i++ {
        arr[i], arr[n-i-1] = arr[n-i-1], arr[i]
    }
}

sample 7000 KB submission

/*

0: (0,0)
1: (0,1), (1,0)
2: (2,0), (1,1), (0,2)
3: (1,2),(2,1)
4: (2,2)

*/

func findDiagonalOrder(mat [][]int) []int {
    result := []int{}
    rowCount := len(mat)
    columnCount := len(mat[0])

    diagonalCount := rowCount + columnCount + 1

    for diagonal := 0; diagonal < diagonalCount; diagonal++ {
        if diagonal % 2 == 0 {
            // from bottom to up
            for col := max(0, diagonal - rowCount + 1); col < min(columnCount, diagonal + 1); col++ {
                row := diagonal - col
                result = append(result, mat[row][col])
            }            
        } else {
            // top down
            for row := max(0, diagonal - columnCount + 1); row < min (rowCount, diagonal + 1); row++ {
                col := diagonal - row
                result = append(result, mat[row][col])
           }
        }
    }

    return result
}

func min(first, second int) int {
    if first < second {
        return first
    }
    return second
}

func max(first, second int) int {
    if first > second {
        return first
    }
    return second
}