Diagonal Traverse II

Interview Problem Interview Medium Hash Map Matrix / Grid Hashing

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.findDiagonalOrder(nums). nums is a non-empty jagged list of rows. Visit diagonals in increasing row+column order and, within a diagonal, visit larger row indices first.

Starter code

class Solution:
    def findDiagonalOrder(self, nums):
        pass

Test cases

square

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

Wizard outline

Step 1: Initialize Solution.findDiagonalOrder
Replace the empty starter with the first real state owned by Solution.findDiagonalOrder. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the One Row case
Complete the readable core algorithm for one representative Interview case. Group cells by row+column and reverse each group to obtain bottom-to-top diagonal order.
Step 4: Harden the Square boundary
Repair the reviewed boundary and pass the complete submission contract. Cells share a traversal diagonal exactly when row+column matches. Iterating keys in increasing order gives diagonal order, and rows were appended top-to-bottom, so reversing each bucket gives the required bottom-to-top order.

Footguns and prerequisites

Rows can have different lengths, so rectangular boundary formulas are unsafe.
arrays strings two pointers sliding window
hashing and sets

Reviewed references

LeetCode 1424 — Diagonal Traverse II

Practice prerequisites

Track Previously Seen Values(opens in a new tab)
Track Previously Seen Values isolates before processing index i, seen contains exactly the distinct values from indices smaller than i. That focused state discipline is required when implementing diagonal traverse two as a complete Interview Problem.

Recommended approach and implementation

Append each value to a bucket keyed by row+column, then emit buckets by increasing key and reverse each bucket.

Why it works: Cells share a traversal diagonal exactly when row+column matches. Iterating keys in increasing order gives diagonal order, and rows were appended top-to-bottom, so reversing each bucket gives the required bottom-to-top order.

class Solution:
    def findDiagonalOrder(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        diagonals = {}
        maximum = 0
        for row, values in enumerate(nums):
            for column, value in enumerate(values):
                key = row + column
                diagonals.setdefault(key, []).append(value)
                maximum = max(maximum, key)
        output = []
        for key in range(maximum + 1):
            output.extend(reversed(diagonals.get(key, [])))
        return output