Sort Matrix Diagonally

📋

Problem

Imagine you have a spreadsheet where you want to sort each diagonal independently to better analyze trends along diagonals.

Given an m x n matrix mat, sort each matrix diagonal in ascending order and return the resulting matrix. A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end.

m == mat.lengthn == mat[i].length1 ≤ m, n ≤ 1001 ≤ mat[i][j] ≤ 100

Edge cases: Matrix with only one row → output is the same row sortedMatrix with only one column → output is the same column sortedMatrix where all elements are the same → output is identical to input

</>

IDE

def diagonalSort(mat: list[list[int]]) -> list[list[int]]:public int[][] diagonalSort(int[][] mat)vector<vector<int>> diagonalSort(vector<vector<int>>& mat)function diagonalSort(mat)

def diagonalSort(mat: list[list[int]]) -> list[list[int]]:
    # Write your solution here
    pass

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        // Write your solution here
        return mat;
    }
}

#include <vector>
using namespace std;

vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
    // Write your solution here
    return mat;
}

function diagonalSort(mat) {
    // Write your solution here
    return mat;
}

Common Bugs to Avoid

Wrong: Matrix with diagonals not sorted or partially sortedNot grouping elements by diagonal index (row - col) correctly or sorting only part of the diagonal✅ Group elements by (row - col) key, sort each group fully, then reassign elements along the diagonal

Wrong: Matrix unchanged for single row or single column inputsCode does not handle single row or single column edge cases properly✅ Ensure diagonal sorting logic works for single row/column by treating each diagonal correctly

Wrong: Matrix elements mixed between diagonalsIncorrect indexing or mixing elements from different diagonals during sorting or reassignment✅ Use (row - col) as key to separate diagonals and keep elements isolated per diagonal

Wrong: Partial sorting or greedy sorting of diagonalsApplying greedy or partial sorting instead of full sorting of each diagonal✅ Sort entire diagonal fully before placing elements back

Wrong: Time limit exceeded on large inputsUsing brute force or exponential complexity approach✅ Implement O(m*n*log(min(m,n))) approach using hash map grouping and sorting per diagonal

✓

Test Cases

Focus on boundary cases like single row or column matrices and identical elements.

Watch out for subtle bugs like off-by-one errors and mixing diagonals.

Optimize your solution to handle large inputs efficiently within time limits.

t1_01basic

Input{"mat":[[3,3,1,1],[2,2,1,2],[1,1,1,2]]}

Expected[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

⏱ Performance - must finish in 2000ms

Each diagonal is extracted, sorted, and placed back. For example, the diagonal starting at (0,0) is [3,2,1], sorted to [1,2,3].

💡 Focus on extracting and sorting each diagonal independently.

💡 Group elements by their diagonal index (row - col) and sort each group.

💡 After sorting, place elements back along each diagonal in order.

Why it failed: Failed to sort diagonals correctly; likely missed grouping by diagonal index or incorrect re-assignment. Fix by mapping elements by (row - col) and sorting each group before reassigning.

✓ Correctly sorts each diagonal independently and reconstructs the matrix.

t1_02basic

Input{"mat":[[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8]]}

Expected[[11,17,36,1,15,7],[23,25,31,44,52,69],[75,55,66,45,58,8]]

⏱ Performance - must finish in 2000ms

Sort each diagonal: e.g. diagonal starting at (0,1) is [25,17,31,45,58], sorted to [17,25,31,44,52,69] after placing back.

💡 Remember diagonals start from first row and first column cells.

💡 Sort each diagonal independently by collecting elements with same (row - col).

💡 Replace elements along diagonals in sorted order to reconstruct matrix.

Why it failed: Incorrect diagonal sorting or placement; possibly mixing diagonals or not sorting fully. Fix by ensuring each diagonal is sorted separately and reassigned correctly.

✓ Properly sorts all diagonals and reconstructs the matrix.

t2_01edge

Input{"mat":[[5,3,4,1,2]]}

Expected[[1,2,3,4,5]]

⏱ Performance - must finish in 2000ms

Single row matrix; sorting diagonals sorts the entire row ascending.

💡 Check behavior when matrix has only one row.

💡 Each diagonal in a single row is just one element; sorting diagonals means sorting the row.

💡 Sort the entire row as all diagonals are length 1 or more but overlap.

Why it failed: Fails single row case by not sorting the row correctly; fix by handling single row as a special case or general diagonal logic.

✓ Correctly sorts single row matrix diagonals.

t2_02edge

Input{"mat":[[7],[3],[5],[1]]}

Expected[[1],[3],[5],[7]]

⏱ Performance - must finish in 2000ms

Single column matrix; sorting diagonals sorts the entire column ascending.

💡 Check behavior when matrix has only one column.

💡 Each diagonal in a single column is just one element; sorting diagonals means sorting the column.

💡 Sort the entire column as all diagonals overlap vertically.

Why it failed: Fails single column case by not sorting the column correctly; fix by handling single column as a special case or general diagonal logic.

✓ Correctly sorts single column matrix diagonals.

t2_03edge

Input{"mat":[[9,9,9],[9,9,9],[9,9,9]]}

Expected[[9,9,9],[9,9,9],[9,9,9]]

⏱ Performance - must finish in 2000ms

All elements identical; sorting diagonals does not change matrix.

💡 Consider matrices where all elements are the same.

💡 Sorting identical elements should yield the same matrix.

💡 Ensure your code handles this without unnecessary changes.

Why it failed: Incorrectly modifies matrix with identical elements; fix by ensuring sorting stable and no unintended changes.

✓ Leaves identical elements matrix unchanged as expected.

t3_01corner

Input{"mat":[[4,3,2],[1,5,6],[7,8,9]]}

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

⏱ Performance - must finish in 2000ms

Diagonal starting at (0,1) is [3,6,9], sorted is [3,6,9]; no change. Tests if code mistakenly sorts incorrectly or mixes diagonals.

💡 Check if diagonals are correctly identified by (row - col).

💡 Verify that sorting does not mix elements from different diagonals.

💡 Ensure stable sorting and correct reassignment along diagonals.

Why it failed: Fails by mixing elements from different diagonals or sorting incorrectly; fix by grouping elements strictly by (row - col) and sorting each group separately.

✓ Correctly identifies and sorts each diagonal without mixing.

t3_02corner

Input{"mat":[[10,2,9],[1,5,6],[7,8,3]]}

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

⏱ Performance - must finish in 2000ms

Tests if code confuses 0/1 knapsack style greedy approach by sorting diagonals incorrectly; diagonal (0,2) is [9,6,3], sorted to [3,6,9].

💡 Avoid greedy assumptions; sort entire diagonal fully.

💡 Group elements by diagonal index and sort completely.

💡 Replace elements along diagonal in sorted order.

Why it failed: Fails by partial or greedy sorting of diagonals; fix by sorting entire diagonal fully before reassignment.

✓ Fully sorts each diagonal correctly.

t3_03corner

Input{"mat":[[5,4,3,2],[1,2,3,4],[9,8,7,6]]}

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

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in diagonal traversal; diagonal starting at (0,1) is [4,3,4], sorted to [2,3,4].

💡 Carefully handle indices when traversing diagonals.

💡 Ensure loop conditions correctly cover all diagonal elements.

💡 Check that reassignment matches sorted order exactly.

Why it failed: Fails due to off-by-one errors causing missing or extra elements in diagonals; fix loop conditions to traverse diagonals fully and correctly.

✓ Correctly traverses and sorts all diagonals without off-by-one errors.

t4_01performance

Input{"_description":"n=100 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix size 100x100; solution must run in O(m*n*log(min(m,n))) time within 2 seconds.

💡 Use efficient grouping by diagonal index and sorting.

💡 Avoid nested loops with exponential complexity.

💡 Use appropriate data structures to minimize overhead.

Why it failed: TLE due to exponential or inefficient complexity; fix by implementing O(m*n*log(min(m,n))) sorting per diagonal using hash map grouping.

✓ Solution runs within time limit using efficient diagonal sorting.

Practice

1. You are given a sorted array of integers and a quadratic function f(x) = ax² + bx + c. You need to return a sorted array of the values f(x) applied to each element x in the input array. Which approach guarantees an optimal O(n) time solution?

easy

A. Use two pointers at the start and end of the input array and fill the output array from the end or start depending on the sign of a, leveraging the parabola shape.

B. Use dynamic programming to store intermediate results and build the sorted transformed array incrementally.

C. Apply the quadratic function to each element and then sort the resulting array using a standard sorting algorithm.

D. Use a max-heap to insert transformed values and then extract them in sorted order.

Solution

1. Step 1: Understand the parabola shape

   The quadratic function forms a parabola. If a >= 0, the largest values are at the ends of the input array; if a < 0, the smallest values are at the ends.

2. Step 2: Use two pointers to fill output

   By comparing transformed values at both ends, we can fill the output array from the appropriate end in O(n) time without sorting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers leverage sorted input and parabola shape for linear time [OK]

Hint: Two pointers exploit parabola shape for O(n) [OK]

Common Mistakes:

• Assuming sorting is always needed after transformation
• Trying DP without leveraging input order

2. Consider the following buggy code snippet for finding missing ranges. Which line contains the subtle bug that causes missing ranges at the start of the interval to be ignored?

medium

A. Line with condition 'if pointer <= curr:' should be 'if pointer < curr:'

B. Line updating pointer to 'curr + 1' should be 'curr' instead

C. Line checking 'if idx == len(nums):' should check 'if idx > len(nums):'

D. Line appending missing range should format single numbers as 'start->end' always

Solution

1. Step 1: Identify condition for missing range detection

   The condition 'if pointer <= curr:' incorrectly includes the case pointer == curr, causing no gap detection before first element if pointer equals first number.

2. Step 2: Correct condition to 'if pointer < curr:'

   This ensures missing ranges are detected only when pointer is strictly less than current number, capturing missing numbers before first element.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes missing start ranges [OK]

Hint: Check strict inequality when detecting gaps [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect pointer update
• Wrong formatting of single numbers

3. What is the time complexity of the optimal counting sort based solution for the relative sort array problem, where n = length of arr1 and k = maximum value in arr1?

medium

A. O(n + k) because frequency counting and outputting are linear in n and k

B. O(n log n) due to sorting leftover elements

C. O(n * k) because nested loops iterate over arr1 and frequency array

D. O(k log k) due to sorting the frequency array keys

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies over arr1 is O(n), where n is arr1 length.

2. Step 2: Analyze output construction

   Outputting elements by iterating frequency array of size k is O(k). No sorting is done on leftover elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting sort runs in linear time relative to n and k [OK]

Hint: Counting sort is linear in input size and max value [OK]

Common Mistakes:

• Assuming leftover elements require sorting (O(n log n))
• Confusing nested loops causing O(n*k)
• Thinking frequency array keys need sorting

4. Suppose the input array can contain colors represented by integers 0, 1, 2, and 3, and you want to sort them in order (0 first, then 1, then 2, then 3) in one pass with constant extra space. Which modification to the Dutch National Flag algorithm is correct?

hard

A. Use counting sort instead, as the one-pass three-pointer approach cannot be directly extended to four colors.

B. Extend the algorithm by adding a fourth pointer and perform multiple passes to partition each color.

C. Modify the algorithm to use three pointers but with nested loops to handle the extra color.

D. Apply the Dutch National Flag algorithm twice: first to separate 0 and non-0, then on the non-0 part to separate 1, 2, and 3.

Solution

1. Step 1: Understand the limitation of Dutch National Flag algorithm

   It is designed specifically for three distinct values using three pointers.

2. Step 2: Consider extension to four colors

   Extending to four colors in one pass with constant space is non-trivial; the algorithm does not generalize easily.

3. Step 3: Identify correct approach

   Counting sort is a stable, simple approach for small fixed number of colors and works in O(n) time with O(1) space for fixed range.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting sort handles multiple colors easily; Dutch Flag is specialized for three [OK]

Hint: Dutch Flag is for 3 colors; counting sort handles more colors easily [OK]

Common Mistakes:

• Trying to add pointers and keep one-pass for 4 colors
• Assuming Dutch Flag generalizes directly
• Using nested loops that increase complexity

5. Suppose the input array can contain duplicate elements and you want to transform and return the sorted array of transformed values, but now you want to handle the case when a=0 (linear function). Which modification to the two-pointer approach is correct?

hard

A. Use the same two-pointer approach as for a ≠ 0, since the parabola shape logic still applies.

B. When a=0, use two pointers but fill the output array from left to right if b ≥ 0, else from right to left, to maintain sorted order.

C. When a=0, reverse the input array and apply the quadratic function, then merge results using two pointers.

D. When a=0, simply apply the linear function to each element and return the transformed array sorted, because two-pointer logic fails.

Solution

1. Step 1: Understand the linear case when a=0

   The function reduces to f(x) = bx + c, which is monotonic increasing if b ≥ 0, decreasing if b < 0.

2. Step 2: Adjust two-pointer approach accordingly

   If b ≥ 0, transformed array is sorted in same order as input; if b < 0, transformed array is sorted in reverse order. So fill output left to right or right to left accordingly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Handling a=0 separately preserves O(n) time and correctness [OK]

Hint: Linear function monotonicity dictates output order [OK]

Common Mistakes:

• Applying parabola two-pointer logic blindly when a=0
• Not handling direction of fill based on b sign