Sort Matrix Diagonally

▶

Steps

setup

Initialize matrix dimensions and diagonal map

We determine the number of rows (m) and columns (n) in the matrix and create an empty map to hold min-heaps for each diagonal key (row - column).

💡 Knowing matrix size and preparing the data structure for diagonals is essential before processing elements.

Line:

m, n = len(mat), len(mat[0])
diagonals = collections.defaultdict(list)

💡 The diagonal key is defined as row index minus column index, which uniquely identifies each diagonal.

fill_cells

Start first traversal: push element at (0,0) into diagonal heap

We push the element 3 at position (0,0) into the min-heap for diagonal key 0 (0 - 0 = 0).

💡 This step begins building the min-heap for the diagonal starting at (0,0).

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=0, j=0

💡 Elements on the same diagonal share the same key, so they go into the same heap.

fill_cells

Push element at (0,1) into diagonal heap

We push the element 3 at position (0,1) into the min-heap for diagonal key -1 (0 - 1 = -1).

💡 Each diagonal heap collects elements from its diagonal; this one is for the diagonal starting at (0,1).

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=0, j=1

💡 Different diagonals have different keys, so elements go into separate heaps.

fill_cells

Push element at (0,2) into diagonal heap

We push the element 1 at position (0,2) into the min-heap for diagonal key -2 (0 - 2 = -2).

💡 Continuing to build heaps for each diagonal by pushing elements.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=0, j=2

💡 Each diagonal heap will hold all elements from that diagonal for sorting.

fill_cells

Push element at (0,3) into diagonal heap

We push the element 1 at position (0,3) into the min-heap for diagonal key -3 (0 - 3 = -3).

💡 This diagonal has only one element so far, but it will be sorted similarly.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=0, j=3

💡 Even single-element diagonals are stored in heaps for uniform processing.

fill_cells

Push element at (1,0) into diagonal heap

We push the element 2 at position (1,0) into the min-heap for diagonal key 1 (1 - 0 = 1).

💡 Starting next row, new diagonal key 1 is created and element added.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=1, j=0

💡 Diagonal keys can be positive or negative depending on position.

fill_cells

Push element at (1,1) into diagonal heap

We push the element 2 at position (1,1) into the min-heap for diagonal key 0 (1 - 1 = 0).

💡 Diagonal key 0 already has elements; we add this one to the same heap.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=1, j=1

💡 All elements on diagonal key 0 are collected together for sorting.

fill_cells

Push element at (1,2) into diagonal heap

We push the element 1 at position (1,2) into the min-heap for diagonal key -1 (1 - 2 = -1).

💡 Adding to diagonal key -1 heap which already has one element.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=1, j=2

💡 Heaps grow as we add more elements from the same diagonal.

fill_cells

Push element at (1,3) into diagonal heap

We push the element 2 at position (1,3) into the min-heap for diagonal key -2 (1 - 3 = -2).

💡 Adding to diagonal key -2 heap which already has one element.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=1, j=3

💡 Heaps maintain order internally to allow efficient extraction of minimum.

fill_cells

Push element at (2,0) into diagonal heap

We push the element 1 at position (2,0) into the min-heap for diagonal key 2 (2 - 0 = 2).

💡 New diagonal key 2 is created and element added.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=2, j=0

💡 Diagonal keys cover all possible row-column differences.

fill_cells

Push element at (2,1) into diagonal heap

We push the element 1 at position (2,1) into the min-heap for diagonal key 1 (2 - 1 = 1).

💡 Adding to diagonal key 1 heap which already has one element.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=2, j=1

💡 Heaps accumulate all diagonal elements before sorting.

fill_cells

Push element at (2,2) into diagonal heap

We push the element 1 at position (2,2) into the min-heap for diagonal key 0 (2 - 2 = 0).

💡 Adding to diagonal key 0 heap which already has two elements.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=2, j=2

💡 All diagonal elements are collected before sorting.

fill_cells

Push element at (2,3) into diagonal heap

We push the element 2 at position (2,3) into the min-heap for diagonal key -1 (2 - 3 = -1).

💡 Adding to diagonal key -1 heap which already has two elements.

Line:

heapq.heappush(diagonals[i - j], mat[i][j])  # i=2, j=3

💡 All diagonal heaps are now fully built with their elements.

fill_cells

Start second traversal: replace element at (0,0) with smallest from diagonal heap

We pop the smallest element from diagonal heap key 0 and place it at position (0,0). The smallest is 1.

💡 This step begins placing sorted values back into the matrix diagonally.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=0, j=0

💡 Replacing elements in order ensures diagonals become sorted.

fill_cells

Replace element at (0,1) with smallest from diagonal heap

We pop the smallest element from diagonal heap key -1 and place it at position (0,1). The smallest is 1.

💡 Continuing to place sorted diagonal elements back into the matrix.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=0, j=1

💡 Each diagonal is sorted independently and replaced in matrix order.

fill_cells

Replace element at (0,2) with smallest from diagonal heap

We pop the smallest element from diagonal heap key -2 and place it at position (0,2). The smallest is 1.

💡 Placing next sorted element from diagonal -2.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=0, j=2

💡 Sorted values come from heaps in ascending order.

fill_cells

Replace element at (0,3) with smallest from diagonal heap

We pop the smallest element from diagonal heap key -3 and place it at position (0,3). The smallest is 1.

💡 Replacing last element in first row from diagonal -3 heap.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=0, j=3

💡 Even single-element diagonals are replaced correctly.

fill_cells

Replace element at (1,0) with smallest from diagonal heap

We pop the smallest element from diagonal heap key 1 and place it at position (1,0). The smallest is 1.

💡 Starting second row replacement from diagonal 1 heap.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=1, j=0

💡 Heaps ensure smallest elements come first for each diagonal.

fill_cells

Replace element at (1,1) with smallest from diagonal heap

We pop the smallest element from diagonal heap key 0 and place it at position (1,1). The smallest is 2.

💡 Continuing replacement for diagonal 0 heap.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=1, j=1

💡 Elements are placed back in sorted order along diagonals.

fill_cells

Replace element at (1,2) with smallest from diagonal heap

We pop the smallest element from diagonal heap key -1 and place it at position (1,2). The smallest is 2.

💡 Replacing element for diagonal -1 heap.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=1, j=2

💡 Heap pops ensure sorted order for diagonal elements.

fill_cells

Replace element at (1,3) with smallest from diagonal heap

We pop the smallest element from diagonal heap key -2 and place it at position (1,3). The smallest is 2.

💡 Replacing last element in second row from diagonal -2 heap.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=1, j=3

💡 All elements from heaps are placed back in sorted order.

fill_cells

Replace element at (2,0) with smallest from diagonal heap

We pop the smallest element from diagonal heap key 2 and place it at position (2,0). The smallest is 1.

💡 Starting last row replacement from diagonal 2 heap.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=2, j=0

💡 Each diagonal's elements are placed back in ascending order.

fill_cells

Replace element at (2,1) with smallest from diagonal heap

We pop the smallest element from diagonal heap key 1 and place it at position (2,1). The smallest is 2.

💡 Replacing element for diagonal 1 heap in last row.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=2, j=1

💡 Heap pops continue to provide sorted elements.

fill_cells

Replace element at (2,2) with smallest from diagonal heap

We pop the smallest element from diagonal heap key 0 and place it at position (2,2). The smallest is 3.

💡 Replacing last element for diagonal 0 heap.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=2, j=2

💡 Final element from diagonal 0 heap is placed, completing that diagonal's sorting.

fill_cells

Replace element at (2,3) with smallest from diagonal heap

We pop the smallest element from diagonal heap key -1 and place it at position (2,3). The smallest is 3.

💡 Replacing last element for diagonal -1 heap, completing all replacements.

Line:

mat[i][j] = heapq.heappop(diagonals[i - j])  # i=2, j=3

💡 All diagonals have been sorted and replaced in the matrix.

from typing import List
import collections
import heapq

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])  # STEP 1
    diagonals = collections.defaultdict(list)  # STEP 1
    # Build min-heaps for each diagonal
    for i in range(m):  # STEP 2-13
        for j in range(n):
            heapq.heappush(diagonals[i - j], mat[i][j])  # STEP 2-13
    # Replace elements by polling from heaps
    for i in range(m):  # STEP 14-25
        for j in range(n):
            mat[i][j] = heapq.heappop(diagonals[i - j])  # STEP 14-25
    return mat

# Driver code
if __name__ == '__main__':
    matrix = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
    print(diagonalSort(matrix))

📊

Sort Matrix Diagonally - Watch the Algorithm Execute, Step by Step

Watching each step of the extraction, sorting, and reinsertion makes it clear how the algorithm handles diagonals independently and why this approach is efficient.

setup

3

0

3

1

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: [[3,3,1,1],[2,2,1,2],[1,1,1,2]]

move_right

j

3

0

3

1

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3]}

move_right

i

3

0

j

3

1

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3],"-1":[3]}

move_right

i

3

0

3

1

j

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3],"-1":[3],"-2":[1]}

move_down

i

3

0

3

1

1

2

j

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3],"-1":[3],"-2":[1],"-3":[1]}

move_right

j

3

0

i

3

1

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3],"1":[2],"-1":[3],"-2":[1],"-3":[1]}

move_right

3

0

j

3

1

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3,2],"1":[2],"-1":[3],"-2":[1],"-3":[1]}

move_right

3

0

i

3

1

j

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3,2],"1":[2],"-1":[3,1],"-2":[1],"-3":[1]}

move_down

3

0

i

3

1

1

2

j

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3,2],"1":[2],"-1":[3,1],"-2":[1,2],"-3":[1]}

move_right

j

3

0

3

1

i

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3,2],"1":[2],"2":[1],"-1":[3,1],"-2":[1,2],"-3":[1]}

move_right

3

0

j

3

1

i

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3,2],"1":[2,1],"2":[1],"-1":[3,1],"-2":[1,2],"-3":[1]}

move_right

3

0

3

1

j

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3,2,1],"1":[2,1],"2":[1],"-1":[3,1],"-2":[1,2],"-3":[1]}

fill_cells

3

0

3

1

i

1

2

j

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: {"0":[3,2,1],"1":[2,1],"2":[1],"-1":[3,1,2],"-2":[1,2],"-3":[1]}

record

j

1

0

3

1

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,3,1,1],[2,2,1,2],[1,1,1,2]]

record

i

1

0

j

1

1

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,1,1,1],[2,2,1,2],[1,1,1,2]]

record

i

1

0

1

1

j

1

2

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,1,1,1],[2,2,1,2],[1,1,1,2]]

record

i

1

0

1

1

1

2

j

1

3

2

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,1,1,1],[2,2,1,2],[1,1,1,2]]

record

j

1

0

i

1

1

1

2

1

3

1

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,1,1,1],[1,2,1,2],[1,1,1,2]]

record

1

0

j

1

1

1

2

1

3

1

4

2

5

1

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,1,1,1],[1,2,1,2],[1,1,1,2]]

record

1

0

i

1

1

j

1

2

1

3

1

4

2

5

2

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,1,1,1],[1,2,2,2],[1,1,1,2]]

record

1

0

i

1

1

1

2

j

1

3

1

4

2

5

2

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,1,1,1],[1,2,2,2],[1,1,1,2]]

record

j

1

0

1

1

i

1

2

1

3

1

4

2

5

2

6

2

7

1

8

1

9

1

10

2

11

Result: [[1,1,1,1],[1,2,2,2],[1,1,1,2]]

record

1

0

j

1

1

i

1

2

1

3

1

4

2

5

2

6

2

7

1

8

2

9

1

10

2

11

Result: [[1,1,1,1],[1,2,2,2],[1,2,1,2]]

record

1

0

1

1

j

1

2

1

3

1

4

2

5

2

6

2

7

1

8

2

9

3

10

2

11

Result: [[1,1,1,1],[1,2,2,2],[1,2,3,2]]

record

1

0

1

1

i

1

2

j

1

3

1

4

2

5

2

6

2

7

1

8

2

9

3

10

3

11

Result: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Key Takeaways

✓ Each diagonal is identified by the key (row - column) and processed independently.

This insight is hard to see from code alone because the diagonal key calculation is subtle and not explicitly visualized.

✓ Using min-heaps for each diagonal allows efficient sorting and retrieval of the smallest elements.

Watching heaps fill and then pop elements clarifies how sorting is done without sorting the entire matrix.

✓ The two-pass traversal first builds heaps, then replaces matrix elements, ensuring diagonals are sorted in-place.

Seeing the pointer movements and heap operations step-by-step reveals the algorithm's structure and flow.

Practice

1. Given the following code for computing the h-index, what is the returned value when the input is [4, 1, 0, 5, 6]?

easy

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Sort citations descending

   Sorted list: [6,5,4,1,0]

2. Step 2: Binary search on h from 0 to 5

   Check mid=2: count papers >=2 is 3 (6,5,4) ≥2 -> low=3; mid=4: count ≥4 is 3 -> low=5; mid=5: count ≥5 is 2 -> high=4; loop ends with high=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final h-index is 4 for this input [OK]

Hint: Count papers ≥ mid after sorting [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Not breaking early in count loop
• Returning low instead of high

2. Consider the following Python code for finding the maximum gap in a list of integers. What is the value of max_gap after the second iteration of the for-loop when the input is [3, 6, 9, 1]?

from typing import List

def maximumGap(nums: List[int]) -> int:
    if len(nums) < 2:
        return 0
    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0
    nums.sort()
    max_gap = 0
    for i in range(1, len(nums)):
        max_gap = max(max_gap, nums[i] - nums[i-1])
    return max_gap

print(maximumGap([3,6,9,1]))  # Output: ?

easy

A. 3

B. 5

C. 6

D. 8

Solution

1. Step 1: Sort the input array

   Input: [3,6,9,1] -> Sorted: [1,3,6,9]

2. Step 2: Trace max_gap updates in the loop

   Iteration 1 (i=1): max_gap = max(0, 3-1) = 2 Iteration 2 (i=2): max_gap = max(2, 6-3) = 3

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   max_gap after second iteration is 3 [OK]

Hint: Sort first, then scan adjacent differences [OK]

Common Mistakes:

• Off-by-one errors in loop
• Using unsorted array differences
• Confusing iteration indices

3. You are given a sorted list of unique integers and a range defined by lower and upper. You need to find all the missing continuous ranges within this interval that are not present in the list. Which algorithmic approach best guarantees an optimal solution in terms of time complexity?

easy

A. Sorting the list and then scanning linearly to find gaps

B. Using binary search to quickly locate missing ranges between elements

C. Dynamic programming to build missing ranges from subproblems

D. Greedy approach scanning the entire range and adding missing numbers one by one

Solution

1. Step 1: Understand problem constraints

   The problem requires finding missing ranges efficiently within a sorted list and a given interval.

2. Step 2: Identify approach that leverages sorted data

   Since the list is already sorted, scanning linearly to find gaps between consecutive elements is optimal and straightforward.

3. Step 3: Evaluate binary search approach

   Using binary search to locate missing ranges is unnecessary overhead because the list is sorted and unique; a linear scan suffices.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Linear scan over sorted unique list is O(n), optimal for this problem [OK]

Hint: Linear scan over sorted unique list is optimal for missing ranges [OK]

Common Mistakes:

• Assuming binary search is needed despite sorted input
• Confusing DP with range search
• Ignoring linear scan benefits

4. Consider the following Python code implementing the optimal approach for relative sorting. Given arr1 = [3,1,2,2] and arr2 = [2,3], what is the final returned list?

easy

A. [2, 3, 1, 2]

B. [3, 2, 2, 1]

C. [2, 2, 3, 1]

D. [1, 2, 2, 3]

Solution

1. Step 1: Build frequency array for arr1

   arr1 = [3,1,2,2], max_val=3, freq = [0,1,2,1] (indices 0 to 3)

2. Step 2: Construct result using arr2 order then leftovers

   Output elements for arr2: 2 appears twice -> [2,2], 3 appears once -> [2,2,3]. Leftover is 1 once -> [2,2,3,1]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency counts and order match output [OK]

Hint: Trace frequency array and output order carefully [OK]

Common Mistakes:

• Appending leftover elements before arr2 order
• Miscounting frequencies or off-by-one in freq array
• Mixing order of arr2 elements in output

5. What is the time complexity of the optimal approach that sorts the array and scans adjacent pairs to find the minimum absolute difference?

medium

A. O(n) because scanning adjacent pairs is linear

B. O(n²) because every pair is compared

C. O(n log n) due to sorting, scanning is O(n)

D. O(log n) because sorting uses divide and conquer

Solution

1. Step 1: Identify sorting cost

   Sorting an array of size n takes O(n log n) time.

2. Step 2: Identify scanning cost

   Scanning adjacent pairs is a single pass O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates total time -> O(n log n) [OK]

Hint: Sorting dominates; scanning is linear [OK]

Common Mistakes:

• Confusing scanning cost as sorting cost
• Assuming O(n) overall without sorting