Diagonal Traverse

Med

#0485Time: O(M * N). We iterate through the matrix once to populate the map (O(M*N)). Then, we iterate through the map's values to build the result. The total number of elements is M*N, and operations like reversing and adding them to the result list take O(M*N) time in total.Space: O(M * N), where M is the number of rows and N is the number of columns. This is because we store all the elements of the matrix in the `diagonals` map.5 companies

Data structures

Array Matrix

Companies

Roblox Zoho Nike Nykaa

Prompt

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

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

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 10⁴
1 <= m * n <= 10⁴
-10⁵ <= mat[i][j] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the observation that all elements on the same diagonal have a constant sum of their row and column indices (i + j). We can use this property to group elements by their diagonal. First, we iterate through the matrix and store each element in a hash map, where the key is the sum of indices i + j and the value is a list of elements on that diagonal. After grouping, we iterate through the diagonals in increasing order of their index sum. For diagonals with an even index sum, the traversal direction is up-right, so we reverse the corresponding list of elements. For odd index sums, the direction is down-left, and the order is already correct. We then append these lists in order to form the final result.

Algorithm

Initialize a map, diagonals, where the key is an integer representing the diagonal index (sum of row and column indices) and the value is a list of integers on that diagonal.
Iterate through the input matrix mat from row i = 0 to m-1 and column j = 0 to n-1.
For each element mat[i][j], calculate its diagonal index d = i + j.
Add the element mat[i][j] to the list associated with key d in the diagonals map. If the key doesn't exist, create a new list.
After populating the map, initialize an empty list resultList to store the final flattened elements.
Iterate through the diagonals by their index d from 0 up to m + n - 2.
For each diagonal d, retrieve the list of its elements from the map.
If the diagonal index d is even, the traversal is up-right. This means the elements should be in the reverse order of how they were added (which was top-to-bottom). Therefore, reverse the list of elements for this diagonal.
Append the elements of the (possibly reversed) list to resultList.
Finally, convert the resultList into an integer array and return it.

Walkthrough

1class Solution {2    public int[] findDiagonalOrder(int[][] mat) {3        if (mat == null || mat.length == 0) {4            return new int[0];5        }6        int m = mat.length;7        int n = mat[0].length;8        // The maximum sum of indices is (m-1) + (n-1)9        Map<Integer, List<Integer>> diagonals = new HashMap<>();10 11        // Group elements by diagonal sum (i + j)12        for (int i = 0; i < m; i++) {13            for (int j = 0; j < n; j++) {14                int key = i + j;15                diagonals.putIfAbsent(key, new ArrayList<>());16                diagonals.get(key).add(mat[i][j]);17            }18        }19 20        List<Integer> resultList = new ArrayList<>();21        // Construct the result array by processing diagonals22        for (int key = 0; key <= (m - 1) + (n - 1); key++) {23            List<Integer> diagonal = diagonals.get(key);24            // For even-sum diagonals, traverse upwards (reverse order)25            if (key % 2 == 0) {26                Collections.reverse(diagonal);27            }28            resultList.addAll(diagonal);29        }30 31        // Convert List<Integer> to int[]32        int[] result = new int[m * n];33        for (int i = 0; i < resultList.size(); i++) {34            result[i] = resultList.get(i);35        }36        return result;37    }38}

Complexity

Time

O(M * N). We iterate through the matrix once to populate the map (O(M*N)). Then, we iterate through the map's values to build the result. The total number of elements is M*N, and operations like reversing and adding them to the result list take O(M*N) time in total.

Space

O(M * N), where M is the number of rows and N is the number of columns. This is because we store all the elements of the matrix in the `diagonals` map.

Trade-offs

Pros

The logic is straightforward and easy to reason about.
Separates the problem into two distinct steps: grouping and ordering.

Cons

Requires O(M * N) extra space to store all the matrix elements in an intermediate data structure, which is inefficient for large matrices.

A more efficient approach is to directly simulate the traversal path without using any extra space (besides the output array). We can iterate through the matrix, placing elements into our result array one by one. We maintain the current (row, col) position and determine the next move based on the current direction and boundary conditions. The direction of traversal (up-right or down-left) alternates. A clever way to manage the direction is by observing that the sum of indices row + col is even for all cells in up-right moving diagonals and odd for all cells in down-left moving diagonals. This simplifies the logic for determining the next move at each step.

Algorithm

Handle the edge case of an empty or null matrix.
Get the matrix dimensions, m and n.
Initialize an integer array result of size m * n to store the output.
Initialize the current position pointers row = 0 and col = 0.
Loop m * n times, once for each element in the matrix.
In each iteration, add the element mat[row][col] to the result array.
Determine the next position by checking the current direction, which can be inferred from the sum row + col.
If (row + col) is even, the direction is up-right:
- If at the right boundary (col == n - 1), move down to the next diagonal: row++.
- If at the top boundary (row == 0), move right to the next diagonal: col++.
- Otherwise, move diagonally up-right: row--, col++.
If (row + col) is odd, the direction is down-left:
- If at the bottom boundary (row == m - 1), move right to the next diagonal: col++.
- If at the left boundary (col == 0), move down to the next diagonal: row++.
- Otherwise, move diagonally down-left: row++, col--.
After the loop completes, return the result array.

Walkthrough

1class Solution {2    public int[] findDiagonalOrder(int[][] mat) {3        if (mat == null || mat.length == 0) {4            return new int[0];5        }6 7        int m = mat.length;8        int n = mat[0].length;9        int[] result = new int[m * n];10        int row = 0, col = 0;11 12        for (int i = 0; i < result.length; i++) {13            result[i] = mat[row][col];14            15            // Direction is up-right if (row + col) is even16            if ((row + col) % 2 == 0) { 17                if (col == n - 1) {18                    // Hit right wall, must move down19                    row++;20                } else if (row == 0) {21                    // Hit top wall, must move right22                    col++;23                } else {24                    // In-bounds, move up-right25                    row--;26                    col++;27                }28            } else { // Direction is down-left29                if (row == m - 1) {30                    // Hit bottom wall, must move right31                    col++;32                } else if (col == 0) {33                    // Hit left wall, must move down34                    row++;35                } else {36                    // In-bounds, move down-left37                    row++;38                    col--;39                }40            }41        }42        return result;43    }44}

Complexity

Time

O(M * N). We traverse each of the M * N elements of the matrix exactly once, and the work done at each step is constant.

Space

O(1). The space required for the output array is not considered extra space. The variables used for tracking position and dimensions take up constant space.

Trade-offs

Pros

Extremely space-efficient, using only O(1) extra space.
Solves the problem in a single pass over the matrix elements.

Cons

The logic for handling boundary conditions and direction changes can be complex and requires careful implementation to avoid errors.

Solutions

Solution

1class Solution {2public3  int[] findDiagonalOrder(int[][] mat) {4    int m = mat.length, n = mat[0].length;5    int[] ans = new int[m * n];6    int idx = 0;7    List<Integer> t = new ArrayList<>();8    for (int k = 0; k < m + n - 1; ++k) {9      int i = k < n ? 0 : k - n + 1;10      int j = k < n ? k : n - 1;11      while (i < m && j >= 0) {12        t.add(mat[i][j]);13        ++i;14        --j;15      }16      if (k % 2 == 0) {17        Collections.reverse(t);18      }19      for (int v : t) {20        ans[idx++] = v;21      }22      t.clear();23    }24    return ans;25  }26}

1class Solution {2public:3  vector<int> findDiagonalOrder(vector<vector<int>> &mat) {4    int m = mat.size(), n = mat[0].size();5    vector<int> ans;6    vector<int> t;7    for (int k = 0; k < m + n - 1; ++k) {8      int i = k < n ? 0 : k - n + 1;9      int j = k < n ? k : n - 1;10      while (i < m && j >= 0)11        t.push_back(mat[i++][j--]);12      if (k % 2 == 0)13        reverse(t.begin(), t.end());14      for (int &v : t)15        ans.push_back(v);16      t.clear();17    }18    return ans;19  }20};

1class Solution:2    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]: m, n = len(mat), len(mat[0]) ans = [] for k in range(m + n - 1): t = [] i = 0 if k < n else k - n + 1 j = k if k < n else n - 1 while i < m and j >= 0: t . append(mat[i][j]) i += 1 j -= 1 if k % 2 == 0: t = t[:: - 1] ans . extend(t) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem