498. Diagonal Traverse #

Problem #

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

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

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

Explanation:

Note:

The total number of elements of the given matrix will not exceed 10,000.

Problem Statement #

Given a matrix containing M x N elements (M rows, N columns), return all elements in the matrix in diagonal traversal order, as shown in the figure below.

Note: The total number of elements in the given matrix will not exceed 100000.

Solution Approach #

Given a two-dimensional array, traverse the entire array in the manner shown in the figure.
This problem can be solved by simulation. Pay attention to boundary conditions: for example, the two-dimensional array is empty, the two-dimensional array degenerates into one row or one column, or degenerates into a single element. See the test cases for specific examples.
The key to solving the problem is determining the next position. Imagine the matrix as an X,Y coordinate axis. Then it can be divided into the following cases:
1. When traversing diagonally to the upper right, If the upper-right corner is within the coordinate axis, calculate normally, i.e., x+1 (move right along the X-axis), y-1 (move up along the Y-axis) If the upper-right corner is outside the coordinate axis, then the current position can only be on the first row X-coordinate axis or the last column Y-coordinate axis, i.e., determine in these two cases whether the X coordinate should move right or the Y coordinate should move up
2. Similarly, when traversing diagonally downward, If the lower-left corner is within the coordinate axis, calculate normally, i.e., x-1 (move right along the X-axis), y+1 (move down along the Y-axis) If the lower-left corner is outside the coordinate axis, then the current position can only be on the first column Y-coordinate axis or the last row X-coordinate axis, i.e., determine in these two cases whether the X coordinate should move left or the Y coordinate should move down

Code #


package leetcode

// Solution 1
func findDiagonalOrder1(matrix [][]int) []int {
	if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
		return nil
	}
	row, col, dir, i, x, y, d := len(matrix), len(matrix[0]), [2][2]int{
		{-1, 1},
		{1, -1},
	}, 0, 0, 0, 0
	total := row * col
	res := make([]int, total)
	for i < total {
		for x >= 0 && x < row && y >= 0 && y < col {
			res[i] = matrix[x][y]
			i++
			x += dir[d][0]
			y += dir[d][1]
		}
		d = (d + 1) % 2
		if x == row {
			x--
			y += 2
		}
		if y == col {
			y--
			x += 2
		}
		if x < 0 {
			x = 0
		}
		if y < 0 {
			y = 0
		}
	}
	return res
}

// Solution 2
func findDiagonalOrder(matrix [][]int) []int {
	if len(matrix) == 0 {
		return []int{}
	}
	if len(matrix) == 1 {
		return matrix[0]
	}
	// dir = 0 represents the direction from upper right to lower left, dir = 1 represents the direction from lower left to upper right, dir = -1 represents that the direction was changed last time
	m, n, i, j, dir, res := len(matrix), len(matrix[0]), 0, 0, 0, []int{}
	for index := 0; index < m*n; index++ {
		if dir == -1 {
			if (i == 0 && j < n-1) || (j == n-1) { // upper boundary and right boundary
				i++
				if j > 0 {
					j--
				}
				dir = 0
				addTraverse(matrix, i, j, &res)
				continue
			}
			if (j == 0 && i < m-1) || (i == m-1) { // left boundary and lower boundary
				if i > 0 {
					i--
				}
				j++
				dir = 1
				addTraverse(matrix, i, j, &res)
				continue
			}
		}
		if i == 0 && j == 0 {
			res = append(res, matrix[i][j])
			if j < n-1 {
				j++
				dir = -1
				addTraverse(matrix, i, j, &res)
				continue
			} else {
				if i < m-1 {
					i++
					dir = -1
					addTraverse(matrix, i, j, &res)
					continue
				}
			}
		}
		if i == 0 && j < n-1 { // upper boundary
			if j < n-1 {
				j++
				dir = -1
				addTraverse(matrix, i, j, &res)
				continue
			}
		}
		if j == 0 && i < m-1 { // left boundary
			if i < m-1 {
				i++
				dir = -1
				addTraverse(matrix, i, j, &res)
				continue
			}
		}
		if j == n-1 { // right boundary
			if i < m-1 {
				i++
				dir = -1
				addTraverse(matrix, i, j, &res)
				continue
			}
		}
		if i == m-1 { // lower boundary
			j++
			dir = -1
			addTraverse(matrix, i, j, &res)
			continue
		}
		if dir == 1 {
			i--
			j++
			addTraverse(matrix, i, j, &res)
			continue
		}
		if dir == 0 {
			i++
			j--
			addTraverse(matrix, i, j, &res)
			continue
		}
	}
	return res
}

func addTraverse(matrix [][]int, i, j int, res *[]int) {
	if i >= 0 && i <= len(matrix)-1 && j >= 0 && j <= len(matrix[0])-1 {
		*res = append(*res, matrix[i][j])
	}
}