Is Diagonal Traverse II easy or hard?

Diagonal Traverse II is generally classified as a Medium problem. The main challenge is recognizing the diagonal invariant r + c and handling the reversed order within each diagonal, especially with jagged arrays where row lengths differ.

Diagonal Traverse II Python/Java solution

In Python or Java, iterate through each row and column, push values into a map keyed by r + c, then iterate through diagonals in increasing order while reversing each stored list. This produces the required diagonal traversal in O(n) time.

How to solve Diagonal Traverse II in O(n)?

Use the property that elements on the same diagonal share the same r + c value. Traverse the matrix, push each value into a map keyed by r + c, and store them in insertion order. Reverse each diagonal list before appending it to the result to maintain the required bottom-to-top ordering.

What is the best approach for Diagonal Traverse II?

The optimal solution groups elements by the diagonal index r + c using a hash map. Iterate through every element, append it to the list for that diagonal, then output each diagonal in reverse order. This runs in O(n) time and O(n) space where n is the total number of elements.

Is Diagonal Traverse II asked at Google/Amazon/Meta?

Diagonal traversal and matrix indexing problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations that use diagonal grouping (r + c) or coordinate-based ordering are common in system design screening and algorithm rounds.

What data structure is used in Diagonal Traverse II?

The most common implementation uses a hash map where the key is the diagonal index r + c and the value is a list of elements on that diagonal. Arrays or vectors store the values, and the final traversal concatenates each diagonal in reverse order.

What is the time complexity of Diagonal Traverse II?

The optimal hash map grouping approach runs in O(n) time because each element is processed exactly once. Space complexity is O(n) to store diagonal groups before building the result. A sorting-based solution takes O(n log n) time due to sorting all elements.

Description Hints 2 Solution Video 31:46

1424. Diagonal Traverse II

Medium58.3% acceptance5 companies

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

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

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i].length <= 10⁵
1 <= sum(nums[i].length) <= 10⁵
1 <= nums[i][j] <= 10⁵

Asked at 5 companies

BP Liftoff Meta

Google Amazon

Topics

Hints open one at a time

Hint 1

Notice that numbers with equal sums of row and column indexes belong to the same diagonal.

Hint 2

Store them in tuples (sum, row, val), sort them, and then regroup the answer.

31:46

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

[[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]

Your code is saved on this device.Solution