498.Diagonal-Traverse

498. Diagonal Traverse

题目地址

https://leetcode.com/problems/diagonal-traverse/

题目描述

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.

代码

Approach #1 Diagonal Iteration and Reversal

class Solution {
  public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0)        return new int[0];

    int N = matrix.length;
    int M = matrix[0].length;

    int[] result = new int[N * M];
    int k = 0;
    ArrayList<Integer> intermediate = new ArrayList<Integer>();

    for (int d = 0; d < N + M - 1; d++) {
      intermediate.clear();

     // We need to figure out the "head" of this diagonal
     // The elements in the first row and the last column
     // are the respective heads.
      int r = d < M ? 0 : d - M + 1;
      int c = d < M ? d : M - 1;

      while (r < N && c > -1) {
        intermediate.add(matrix[r][c]);
        r++;
        c--;
      }

      if (d % 2 == 0) { // adjust directions
        Collections.reverse(intermediate);
      }

      // added to result
      for (int i = 0; i < intermediate.size(); i++) {
        result[k++] = intermediate.get(i);
      }
    }

    return result;
  }
}

Approach #2 Simulation

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {

        // Check for empty matrices
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }

        // Variables to track the size of the matrix
        int N = matrix.length;
        int M = matrix[0].length;

        // Incides that will help us progress through 
        // the matrix, one element at a time.
        int row = 0, column = 0;

        // As explained in the article, this is the variable
        // that helps us keep track of what direction we are
        // processing the current diaonal
        int direction = 1;

         // The final result array
        int[] result = new int[N*M];
        int r = 0;

        // The uber while loop which will help us iterate over all
        // the elements in the array.
        while (row < N && column < M) {

            // First and foremost, add the current element to 
            // the result matrix. 
            result[r++] = matrix[row][column];

            // Move along in the current diagonal depending upon
            // the current direction.[i, j] -> [i - 1, j + 1] if 
            // going up and [i, j] -> [i + 1][j - 1] if going down.
            int new_row = row + (direction == 1 ? -1 : 1);
            int new_column = column + (direction == 1 ? 1 : -1);

            // Checking if the next element in the diagonal is within the
            // bounds of the matrix or not. If it's not within the bounds,
            // we have to find the next head. 
            if (new_row < 0 || new_row == N || new_column < 0 || new_column == M) {

                // If the current diagonal was going in the upwards
                // direction.
                if (direction == 1) {

                    // For an upwards going diagonal having [i, j] as its tail
                    // If [i, j + 1] is within bounds, then it becomes
                    // the next head. Otherwise, the element directly below
                    // i.e. the element [i + 1, j] becomes the next head
                    row += (column == M - 1 ? 1 : 0) ;
                    column += (column < M - 1 ? 1 : 0);

                } else {

                    // For a downwards going diagonal having [i, j] as its tail
                    // if [i + 1, j] is within bounds, then it becomes
                    // the next head. Otherwise, the element directly below
                    // i.e. the element [i, j + 1] becomes the next head
                    column += (row == N - 1 ? 1 : 0);
                    row += (row < N - 1 ? 1 : 0);
                }

                // Flip the direction
                direction = 1 - direction;        

            } else {

                row = new_row;
                column = new_column;
            }
        }
        return result;      
    }
}