Search

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.


 

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;

// The two arrays as explained in the algorithm

int[] result = new int[N*M];

int k = 0;

ArrayList<Integer> intermediate = new ArrayList<Integer>();

// We have to go over all the elements in the first

// row and the last column to cover all possible diagonals

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

// Clear the intermediate array every time we start

// to process another diagonal

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;

// Iterate until one of the indices goes out of scope

// Take note of the index math to go down the diagonal

while (r < N && c > -1) {

intermediate.add(matrix[r][c]);

++r;

--c;

}

// Reverse even numbered diagonals. The

// article says we have to reverse odd

// numbered articles but here, the numbering

// is starting from 0 :P

if (d % 2 == 0) {

Collections.reverse(intermediate);

}

for (int i = 0; i < intermediate.size(); i++) {

result[k++] = intermediate.get(i);

}

}

return result;

}

}




11 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.