Diagonal Traverse

Diagonal Traverse is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Set Matrix Zeroes (In-place Marking) subpattern.

Problem statement

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.

Topics and companies

Topics: nan.

Reported in interviews at Facebook, Amazon.

How to practise Diagonal Traverse on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(1) space.

Open Diagonal Traverse in the code editor, or read the Diagonal Traverse editorial for a worked solution with its approach and complexity analysis.

Where Diagonal Traverse sits in the DSA pattern sheet

• Array/Matrix Manipulation Patterns pattern guide
• Set Matrix Zeroes (In-place Marking) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Diagonal Traverse

Other problems that use the same Set Matrix Zeroes (In-place Marking) and Array/Matrix Manipulation Patterns techniques:

• Game of Life — Medium, same subpattern
• Set Matrix Zeroes — Medium, same subpattern
• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Find All Duplicates in an Array — Medium, same pattern
• Find All Numbers Disappeared in an Array — Easy, same pattern