498. Diagonal Traverse

MediumArrayMatrixSimulation
Leetcode Link

Problem Description

The problem provides us with an m x n matrix, named mat, and asks us to return an array of all the elements in the matrix arranged in a specific order. This order follows the diagonal patterns of the matrix. We start from the top-left corner, move diagonally up and to the right, and upon reaching the top or right boundary, we move to the next diagonal, which starts from the leftmost or bottommost element of the current boundary. The process continues until all elements are traversed. It is important to note that when moving along the diagonals, the order of traversal alternates. Diagonals that have a bottom-left to top-right orientation are traversed from top to bottom, while diagonals with a top-right to bottom-left orientation are traversed from bottom to top.

Intuition

The solution uses a single-pass algorithm that iterates over the potential starting points for each diagonal in the matrix. A crucial observation is that if you list the starting points, they follow the border of the matrix, first going downward along the left side and then going rightward along the bottom side. The total number of such diagonals would correspond to m + n - 1, considering every element of the first and last row and column except the bottom-right corner element, which is accounted for twice if we simply sum m and n.

The solution assigns two pointers (i and j) that represent the row and column positions, respectively. These pointers scan the matrix along the current diagonal. The direction of scanning alternates with each diagonal: if we're on an even-numbered diagonal (using 0-based indexing), the elements need to be appended in reverse, and for odd-numbered diagonals, the order is maintained as is. The result of each diagonal scan is then concatenated to build the final solution.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Solution Approach

The solution approach involves iterating through all the possible diagonals in the matrix. These diagonals are indexed by a variable called k which runs from 0 to m + n - 2 inclusive.

Here are the steps taken by the algorithm:

  1. A loop begins with k starting from 0 and running up to m + n - 1. Each iteration of this loop corresponds to a diagonal in the matrix.

  2. For each k, we determine the starting position (i, j) of the current diagonal. If k is less than n (number of columns), then i starts at 0 and j starts at k. Otherwise, when k is at least n, i starts at k - n + 1 and j starts at n - 1.

  3. A temporary list t is created to store the elements of the current diagonal. We use while loop to navigate through the diagonal and collect elements from mat[i][j] as long as i < m and j >= 0, incrementing i and decrementing j.

  4. The direction of iteration along the diagonal is important. After collecting elements in the temporary list, if k is even, the order of the elements is reversed (using t[::-1]), to adhere to the proper diagonal traversal sequence as specified by the problem.

  5. The elements in t (in the correct order) are then added to ans, which is the list that will ultimately be returned.

  6. After all iterations, ans contains all matrix elements in the desired diagonal order, and the list is returned.

This approach uses straightforward indexing to access the matrix elements and employs a list to collect the output. The conditional reversal of the temporary list accounts for the zigzag pattern of the traversal, alternating between diagonals. Such an approach is space-efficient since it does not require additional space proportional to the size of the matrix, besides the output list. It also traverses each element exactly once, making it time-efficient.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's walk through an example to illustrate the solution approach with a 3 x 4 matrix.

Given matrix mat:

11  2  3  4
25  6  7  8
39 10 11 12

We need to collect the elements in the matrix following a specific diagonal pattern:

  1. Start with k = 0, which corresponds to the first diagonal, which is just the element 1. Since k is even, we collect elements from top to bottom. Our answer list ans begins with [1].

  2. Move to k = 1, representing the second diagonal [2, 5]. k is odd, so we reverse the order when appending to ans. The answer list becomes [1, 5, 2].

  3. For k = 2, the diagonal is [3, 6, 9]. k is even, so append in original order: ans = [1, 5, 2, 3, 6, 9].

  4. k = 3 gives diagonal [4, 7, 10]. k is odd, so reverse it: ans = [1, 5, 2, 3, 6, 9, 10, 7, 4].

  5. For k = 4, the diagonal is [8, 11]. k is even: ans = [1, 5, 2, 3, 6, 9, 10, 7, 4, 8, 11].

  6. Finally, k = 5 corresponds to the last diagonal which is simply [12]. Since k is odd, it remains as is: ans = [1, 5, 2, 3, 6, 9, 10, 7, 4, 8, 11, 12].

The final output is [1, 5, 2, 3, 6, 9, 10, 7, 4, 8, 11, 12], the matrix elements arranged in the desired diagonal order.

Through these steps, the solution iterates over each possible starting point for the diagonals, collects the elements in either forward or reverse order depending on the index of the diagonal, and constructs the output list efficiently. The k loop guarantees that we cover all possible diagonals in the matrix. The given solution is a simple yet effective means to convert 2-dimensional matrix traversal into a 1-dimensional list that preserves the diagonal ordering constraint.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
5        # Determine the number of rows and columns in the matrix.
6        num_rows, num_cols = len(matrix), len(matrix[0])
7      
8        # This is the list which will hold the elements in diagonal order.
9        diagonal_order = []
10      
11        # There will be (num_rows + num_cols - 1) diagonals to cover in the matrix.
12        for k in range(num_rows + num_cols - 1):
13          
14            # Temp list to store the elements of the current diagonal.
15            temp = []
16          
17            # Calculate the starting row index. It is 0 for the first 'num_cols' diagonals,
18            # otherwise we start at an index which goes down from 'num_rows - 1'.
19            row = 0 if k < num_cols else k - num_cols + 1
20          
21            # Calculate the starting column index. It is 'k' for the first 'num_cols' diagonals,
22            # otherwise we start at 'num_cols - 1' and go down.
23            col = k if k < num_cols else num_cols - 1
24          
25            # Fetch the elements along the current diagonal.
26            # Continue while 'row' is within the matrix row range and 'col' is non-negative.
27            while row < num_rows and col >= 0:
28                temp.append(matrix[row][col])
29                row += 1  # Move down to the next row.
30                col -= 1  # Move left to the next column.
31          
32            # Reverse every other diagonal's elements before appending it to the result list
33            # to get the right order.
34            if k % 2 == 0:
35                temp = temp[::-1]
36          
37            # Extend the main result list with the elements of the current diagonal.
38            diagonal_order.extend(temp)
39      
40        # Return the final result list.
41        return diagonal_order
42
1class Solution {
2    public int[] findDiagonalOrder(int[][] matrix) {
3        // matrix dimensions
4        int m = matrix.length;
5        int n = matrix[0].length;
6
7        // result array
8        int[] result = new int[m * n];
9
10        // index for the result array
11        int index = 0;
12
13        // temporary list to store diagonal elements
14        List<Integer> diagonal = new ArrayList<>();
15
16        // loop through each diagonal starting from the top-left corner moving towards the right-bottom corner
17        for (int diag = 0; diag < m + n - 1; ++diag) {
18            // determine the starting row index for the current diagonal
19            int row = diag < n ? 0 : diag - n + 1;
20          
21            // determine the starting column index for the current diagonal
22            int col = diag < n ? diag : n - 1;
23
24            // collect all the elements from the current diagonal
25            while (row < m && col >= 0) {
26                diagonal.add(matrix[row][col]);
27                ++row;
28                --col;
29            }
30
31            // reverse the diagonal elements if we are in an even diagonal (starting counting from 0)
32            if (diag % 2 == 0) {
33                Collections.reverse(diagonal);
34            }
35
36            // add the diagonal elements to the result array
37            for (int element : diagonal) {
38                result[index++] = element;
39            }
40
41            // clear the temporary diagonal list for the next iteration
42            diagonal.clear();
43        }
44        return result;
45    }
46}
47
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    std::vector<int> findDiagonalOrder(std::vector<std::vector<int>>& matrix) {
7        int rows = matrix.size(), columns = matrix[0].size();
8        std::vector<int> result;
9        std::vector<int> diagonalElements;
10      
11        // Iterate over all possible diagonals in the matrix
12        for (int diag = 0; diag < rows + columns - 1; ++diag) {
13            // Initialize row index (i) and column index (j) for the start of the diagonal
14            int i = diag < columns ? 0 : diag - columns + 1;
15            int j = diag < columns ? diag : columns - 1;
16          
17            // Collect all elements in the current diagonal
18            while (i < rows && j >= 0) {
19                diagonalElements.push_back(matrix[i++][j--]);
20            }
21          
22            // If the diagonal index is even, we need to reverse the diagonal elements
23            // to maintain the "zigzag" diagonal order
24            if (diag % 2 == 0) {
25                std::reverse(diagonalElements.begin(), diagonalElements.end());
26            }
27          
28            // Append the current diagonal's elements to the result vector
29            for (int value : diagonalElements) {
30                result.push_back(value);
31            }
32          
33            // Clear the diagonal elements vector for the next diagonal
34            diagonalElements.clear();
35        }
36      
37        // Return the final vector with all elements in diagonal order
38        return result;
39    }
40};
41
1function findDiagonalOrder(matrix: number[][]): number[] {
2    // Initialize the result array where diagonal elements will be stored.
3    const result: number[] = [];
4    // Determine the number of rows (m) and columns (n) in the matrix.
5    const numRows = matrix.length;
6    const numCols = matrix[0].length;
7    // Define the starting indices for matrix traversal.
8    let row = 0;
9    let col = 0;
10    // A boolean flag to determine the direction of traversal.
11    let isUpward = true;
12
13    // Continue traversing until the result array is filled with all elements.
14    while (result.length < numRows * numCols) {
15        if (isUpward) {
16            // Move diagonally up-right until the boundary is reached.
17            while (row >= 0 && col < numCols) {
18                result.push(matrix[row][col]);
19                row--;
20                col++;
21            }
22            // If we've exceeded the top row, reset to start from the next column.
23            if (row < 0 && col < numCols) {
24                row = 0;
25            }
26            // If we've exceeded the right-most column, move down to the next row.
27            if (col === numCols) {
28                row += 2;
29                col--;
30            }
31        } else {
32            // Move diagonally down-left until the boundary is reached.
33            while (row < numRows && col >= 0) {
34                result.push(matrix[row][col]);
35                row++;
36                col--;
37            }
38            // If we've exceeded the bottom row, reset to start from the next column.
39            if (row === numRows) {
40                row--;
41                col += 2;
42            }
43            // If we've exceeded the left-most column, move up to the next row.
44            if (col < 0) {
45                col = 0;
46            }
47        }
48        // Flip the direction for the next iteration.
49        isUpward = !isUpward;
50    }
51    // Return the array containing elements in diagonal order.
52    return result;
53}
54
Not Sure What to Study? Take the 2-min Quiz：

A heap is a ...?

Time and Space Complexity

The given code snippet traverses through all the elements of a two-dimensional matrix mat of size m x n diagonally, collecting the elements of each diagonal and appending them to the final result in a specified order.

Time Complexity: O(m * n)

The time complexity of the code is determined by the number of iterations needed to traverse all the elements of the matrix. Since the matrix has m rows and n columns, there are m * n elements in total. The outer loop runs for m + n - 1 iterations, where each diagonal is processed. In each iteration of this loop, a while-loop runs, collecting elements along the current diagonal. Each element in the matrix is processed exactly once inside the nested while-loops. Thus, the total number of operations is proportional to the number of elements in the matrix, leading to a time complexity of O(m * n).

Space Complexity: O(min(m, n))

The space complexity of the code is primarily due to the auxiliary data structure t used for storing each diagonal before appending it to the result list ans. The length of a diagonal is at most min(m, n), because the diagonals are limited either by the number of rows or the number of columns. The reversing operation, t[::-1], creates a new list of the same size as t, and thus, the temporary space required is also in the order of min(m, n). Since the additional space needed is not dependent on the total number of elements but rather on the longer dimension of the input matrix, the space complexity is O(min(m, n)).

The result list ans grows to hold all m * n elements, but this does not contribute to space complexity in the analysis, as it is required to hold the output of the function. Hence, we only consider the additional space used by the algorithm beyond the output space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫