algoadvance

Leetcode 498. Diagonal Traverse

Problem Statement

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

For example:

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

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

Clarifying Questions

  1. Q: Can we assume the input matrix is not empty? A: Yes, you can assume the matrix is non-empty.

  2. Q: Are the values in the matrix guaranteed to be integers? A: Yes, the values in the matrix are integers.

  3. Q: What should we return if the matrix is empty? A: Since the matrix is guaranteed to be non-empty, we do not need to handle this case.

Strategy

We can approach this problem by following these steps:

  1. Use two pointers r and c to keep track of the current row and column in the matrix.
  2. Use a variable up to determine the direction of traversal. If up is true, we move diagonally upwards; if up is false, we move diagonally downwards.
  3. Iterate over the elements and update the pointers based on the direction of traversal and boundary conditions.

The key is to understand and implement the boundary conditions when the traversal hits the edges of the matrix:

Code

Here is the Java implementation of the described algorithm:

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

        int rows = mat.length, cols = mat[0].length;
        int[] result = new int[rows * cols];

        int r = 0, c = 0;
        boolean up = true;

        for (int i = 0; i < result.length; i++) {
            result[i] = mat[r][c];
            
            if (up) {
                if (c == cols - 1) {
                    r++;
                    up = !up;
                } else if (r == 0) {
                    c++;
                    up = !up;
                } else {
                    r--;
                    c++;
                }
            } else {
                if (r == rows - 1) {
                    c++;
                    up = !up;
                } else if (c == 0) {
                    r++;
                    up = !up;
                } else {
                    r++;
                    c--;
                }
            }
        }

        return result;
    }
}

Time Complexity

The time complexity of this solution is O(m * n) where m is the number of rows and n is the number of columns in the matrix. This is because we are visiting each element of the matrix exactly once. The space complexity is O(m * n) for the result array which stores all the elements of the matrix in the required diagonal order.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI