Show problems as
Classic problem #498MediumArrayMatrixSimulation

Diagonal Traverse

Real-world version: Slanted Sweep Readout
Tracked in this browser only
Read Diagonal Traverse on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A calibration rig stores its readings in a grid plate with m rows and n columns, where plate[i][j] is a signed offset in micrometres and may be negative.

The rig's arm does not read row by row. It groups the cells into sweeps: two cells belong to the same sweep when their row index and column index add up to the same total. The arm works through the sweeps in increasing order of that total, starting with the sweep whose total is 0.

Inside a sweep the arm alternates which way it travels. When the sweep's total is even, the arm reports its cells starting from the largest row index and working down to the smallest. When the total is odd, it reports them from the smallest row index up to the largest.

Return the offsets in the order the arm reports them.

Examples

Example 1

Input
plate = [[-4, 7, 2], [5, -1, 9]]
Output
[-4, 7, 5, -1, 2, 9]

Sweep 0 holds only -4. Sweep 1 has an odd total so it runs downward through 7 then 5. Sweep 2 is even and runs upward through -1 then 2, and sweep 3 finishes with 9.

Example 2

Input
plate = [[8], [-3], [6]]
Output
[8, -3, 6]

With a single column every sweep holds exactly one cell, so the direction never matters and the column is read top to bottom.

Example 3

Input
plate = [[9, -9]]
Output
[9, -9]

A single row also puts one cell in each sweep, so the readings come out left to right.

Constraints

  • m == plate.length
  • n == plate[i].length
  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • -10^5 <= plate[i][j] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def slanted_sweep_readout(plate: list[list[int]]) -> list[int]:
Java
public int[] slantedSweepReadout(int[][] plate)

More on the same topics