Sort Matrix Diagonally

🎯

Sort Matrix Diagonally

mediumSORT_SEARCHAmazonGoogle

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

💡 This problem is about sorting elements along diagonals of a matrix, which is tricky because diagonals are not contiguous rows or columns. Beginners often struggle to identify and isolate these diagonals for sorting.

📋

Problem Statement

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

💡

Example

Input"[[3,3,1,1],[2,2,1,2],[1,1,1,2]]"

Output[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

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].

• Matrix with only one row → output is the same row sorted
• Matrix with only one column → output is the same column sorted
• Matrix where all elements are the same → output is identical to input
• Matrix with maximum size 100x100 → should complete efficiently

⚠️

Common Mistakes

Not correctly identifying diagonal keys (row - col)

Sorting wrong elements together or missing diagonals

✅ Use (row - col) as the unique diagonal identifier consistently

Sorting diagonals but writing back in wrong order

Matrix ends up incorrectly sorted or corrupted

✅ Ensure to write back elements in the same order they were extracted

Using reverse sorting but popping from front instead of end

Index errors or incorrect element placement

✅ If sorting descending, pop from end; if ascending, pop from front

Ignoring edge cases like single row or column matrices

Code may crash or produce wrong output on minimal inputs

✅ Test and handle matrices with 1 row or 1 column explicitly

Using inefficient sorting repeatedly inside loops

Time limit exceeded on larger inputs

✅ Group elements first, then sort once per diagonal

🧠

Brute Force (Extract and Sort Each Diagonal Separately)

💡 This approach helps beginners understand the problem by directly extracting each diagonal, sorting it, and putting it back, without any optimization.

Intuition

Each diagonal can be identified by its starting point on the first row or first column. Extract all elements along that diagonal, sort them, then write them back.

Algorithm

1. Identify all diagonals by their starting points on the first row and first column.
2. For each diagonal, extract all elements into a list.
3. Sort the list.
4. Put the sorted elements back into their diagonal positions in the matrix.

💡 The challenge is correctly identifying and iterating over diagonals, which are not straightforward like rows or columns.

</>

Code

from typing import List

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    # Function to sort one diagonal starting at (r, c)
    def sort_diagonal(r, c):
        diagonal = []
        i, j = r, c
        while i < m and j < n:
            diagonal.append(mat[i][j])
            i += 1
            j += 1
        diagonal.sort()
        i, j = r, c
        for val in diagonal:
            mat[i][j] = val
            i += 1
            j += 1
    # Sort diagonals starting from first row
    for col in range(n):
        sort_diagonal(0, col)
    # Sort diagonals starting from first column (excluding [0,0])
    for row in range(1, m):
        sort_diagonal(row, 0)
    return mat

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

Line Notes

m, n = len(mat), len(mat[0])Determine matrix dimensions for boundary checks

def sort_diagonal(r, c):Helper function to isolate and sort one diagonal

while i < m and j < n:Traverse the diagonal until hitting matrix boundary

diagonal.sort()Sort the extracted diagonal elements in ascending order

for val in diagonal:Put sorted values back into the matrix along the diagonal

for col in range(n):Start sorting diagonals from each column in the first row

for row in range(1, m):Start sorting diagonals from each row in the first column, skipping (0,0) to avoid duplication

import java.util.*;

public class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        // Sort one diagonal starting at (r, c)
        for (int col = 0; col < n; col++) {
            sortDiagonal(mat, 0, col, m, n);
        }
        for (int row = 1; row < m; row++) {
            sortDiagonal(mat, row, 0, m, n);
        }
        return mat;
    }

    private void sortDiagonal(int[][] mat, int r, int c, int m, int n) {
        List<Integer> diagonal = new ArrayList<>();
        int i = r, j = c;
        while (i < m && j < n) {
            diagonal.add(mat[i][j]);
            i++;
            j++;
        }
        Collections.sort(diagonal);
        i = r;
        j = c;
        for (int val : diagonal) {
            mat[i][j] = val;
            i++;
            j++;
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
        int[][] sorted = sol.diagonalSort(matrix);
        for (int[] row : sorted) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

int m = mat.length, n = mat[0].length;Get matrix dimensions for boundary checks

for (int col = 0; col < n; col++)Iterate over first row columns to start diagonals

for (int row = 1; row < m; row++)Iterate over first column rows to start diagonals, skip (0,0)

while (i < m && j < n)Traverse diagonal until boundary

Collections.sort(diagonal);Sort the diagonal elements

for (int val : diagonal)Write sorted values back into matrix diagonal

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        for (int col = 0; col < n; ++col) {
            sortDiagonal(mat, 0, col, m, n);
        }
        for (int row = 1; row < m; ++row) {
            sortDiagonal(mat, row, 0, m, n);
        }
        return mat;
    }

private:
    void sortDiagonal(vector<vector<int>>& mat, int r, int c, int m, int n) {
        vector<int> diagonal;
        int i = r, j = c;
        while (i < m && j < n) {
            diagonal.push_back(mat[i][j]);
            i++;
            j++;
        }
        sort(diagonal.begin(), diagonal.end());
        i = r; j = c;
        for (int val : diagonal) {
            mat[i][j] = val;
            i++;
            j++;
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> matrix = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
    vector<vector<int>> sorted = sol.diagonalSort(matrix);
    for (auto &row : sorted) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

int m = mat.size(), n = mat[0].size();Get matrix dimensions for boundary checks

for (int col = 0; col < n; ++col)Start diagonals from first row columns

for (int row = 1; row < m; ++row)Start diagonals from first column rows, skip (0,0)

while (i < m && j < n)Traverse diagonal until matrix boundary

sort(diagonal.begin(), diagonal.end());Sort the diagonal elements

for (int val : diagonal)Write sorted values back into matrix diagonal

var diagonalSort = function(mat) {
    const m = mat.length, n = mat[0].length;
    const sortDiagonal = (r, c) => {
        const diagonal = [];
        let i = r, j = c;
        while (i < m && j < n) {
            diagonal.push(mat[i][j]);
            i++;
            j++;
        }
        diagonal.sort((a,b) => a - b);
        i = r; j = c;
        for (const val of diagonal) {
            mat[i][j] = val;
            i++;
            j++;
        }
    };
    for (let col = 0; col < n; col++) {
        sortDiagonal(0, col);
    }
    for (let row = 1; row < m; row++) {
        sortDiagonal(row, 0);
    }
    return mat;
};

// Driver code
const matrix = [[3,3,1,1],[2,2,1,2],[1,1,1,2]];
console.log(diagonalSort(matrix));

Line Notes

const m = mat.length, n = mat[0].length;Get matrix dimensions for boundary checks

const sortDiagonal = (r, c) => {Helper function to extract and sort one diagonal

while (i < m && j < n)Traverse diagonal until matrix boundary

diagonal.sort((a,b) => a - b);Sort diagonal elements numerically ascending

for (const val of diagonal)Write sorted values back into matrix diagonal

for (let col = 0; col < n; col++)Start diagonals from first row columns

for (let row = 1; row < m; row++)Start diagonals from first column rows, skip (0,0)

⏱

Complexity

TimeO(m * n * log(min(m, n)))

SpaceO(min(m, n))

We extract and sort each diagonal. There are roughly m + n diagonals, each up to length min(m, n). Sorting each diagonal costs O(k log k), k ≤ min(m,n). Total is O(m*n*log(min(m,n))).

💡 For a 100x100 matrix, this means sorting about 200 diagonals each up to length 100, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach is straightforward and accepted for the problem constraints, making it a solid first solution.

🧠

Using Hash Map to Group Diagonals and Sort

💡 This approach groups all elements by their diagonal keys using a hash map, then sorts each group once, improving code clarity and avoiding repeated extraction.

Intuition

Each diagonal can be identified by the difference (row - column). Group all elements by this key, sort each group, then write back using the same key.

Algorithm

1. Create a hash map where keys are (row - column) and values are lists of elements on that diagonal.
2. Traverse the matrix once to populate the map.
3. Sort each list in the map.
4. Traverse the matrix again, replacing elements with sorted values from the map.

💡 This approach separates data collection and writing back, making the code easier to reason about.

</>

Code

from typing import List
import collections

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    diagonals = collections.defaultdict(list)
    # Collect elements by diagonal key
    for i in range(m):
        for j in range(n):
            diagonals[i - j].append(mat[i][j])
    # Sort each diagonal
    for key in diagonals:
        diagonals[key].sort(reverse=True)  # reverse for efficient pop from end
    # Write back sorted elements
    for i in range(m):
        for j in range(n):
            mat[i][j] = diagonals[i - j].pop()
    return mat

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

Line Notes

diagonals = collections.defaultdict(list)Initialize map to group diagonal elements by key

for i in range(m):Traverse rows to collect elements

diagonals[i - j].append(mat[i][j])Group elements by diagonal key (row - col)

diagonals[key].sort(reverse=True)Sort each diagonal descending for efficient pop from end

mat[i][j] = diagonals[i - j].pop()Replace matrix element with sorted diagonal element

import java.util.*;

public class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        // Collect elements by diagonal key
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = i - j;
                map.putIfAbsent(key, new PriorityQueue<>());
                map.get(key).offer(mat[i][j]);
            }
        }
        // Write back sorted elements
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = i - j;
                mat[i][j] = map.get(key).poll();
            }
        }
        return mat;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
        int[][] sorted = sol.diagonalSort(matrix);
        for (int[] row : sorted) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();Map diagonal keys to min-heaps for sorted order

map.putIfAbsent(key, new PriorityQueue<>());Initialize priority queue if key not present

map.get(key).offer(mat[i][j]);Add element to corresponding diagonal heap

mat[i][j] = map.get(key).poll();Replace matrix element with smallest element from heap

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> map;
        // Collect elements by diagonal key
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                map[i - j].push(mat[i][j]);
            }
        }
        // Write back sorted elements
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] = map[i - j].top();
                map[i - j].pop();
            }
        }
        return mat;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> matrix = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
    vector<vector<int>> sorted = sol.diagonalSort(matrix);
    for (auto &row : sorted) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

unordered_map<int, priority_queue<int, vector<int>, greater<int>>> map;Map diagonal keys to min-heaps for sorted order

map[i - j].push(mat[i][j]);Add element to corresponding diagonal min-heap

mat[i][j] = map[i - j].top();Replace matrix element with smallest element from heap

map[i - j].pop();Remove used element from heap

var diagonalSort = function(mat) {
    const m = mat.length, n = mat[0].length;
    const map = new Map();
    // Collect elements by diagonal key
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const key = i - j;
            if (!map.has(key)) map.set(key, []);
            map.get(key).push(mat[i][j]);
        }
    }
    // Sort each diagonal
    for (const key of map.keys()) {
        map.get(key).sort((a,b) => a - b);
    }
    // Write back sorted elements
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const key = i - j;
            mat[i][j] = map.get(key).shift();
        }
    }
    return mat;
};

// Driver code
const matrix = [[3,3,1,1],[2,2,1,2],[1,1,1,2]];
console.log(diagonalSort(matrix));

Line Notes

const map = new Map();Map diagonal keys to arrays for grouping elements

map.get(key).push(mat[i][j]);Add element to corresponding diagonal group

map.get(key).sort((a,b) => a - b);Sort each diagonal group ascending

mat[i][j] = map.get(key).shift();Replace matrix element with sorted diagonal element

⏱

Complexity

TimeO(m * n * log(min(m, n)))

SpaceO(m * n)

Grouping all elements by diagonal keys costs O(m*n). Sorting each diagonal costs O(k log k), total O(m*n*log(min(m,n))). Using heaps or arrays increases space to O(m*n).

💡 This approach uses extra space to store all elements grouped by diagonal, which is acceptable for matrix sizes up to 100x100.

Interview Verdict: Accepted

This approach is clean and efficient, often preferred for clarity and ease of implementation.

🧠

In-place Sorting Using Priority Queues per Diagonal

💡 This approach uses priority queues (min-heaps) to sort diagonals on the fly, combining grouping and sorting with efficient retrieval.

Intuition

Use a min-heap for each diagonal key to store elements. Insert all elements, then overwrite matrix by polling from heaps, ensuring sorted order without extra sorting calls.

Algorithm

1. Create a map from diagonal keys (row - column) to min-heaps.
2. Traverse the matrix, pushing each element into its diagonal's min-heap.
3. Traverse the matrix again, replacing each element by polling from its diagonal's min-heap.

💡 This approach avoids explicit sorting calls by leveraging heap properties for sorting.

</>

Code

from typing import List
import collections
import heapq

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

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

Line Notes

import heapqImport heapq for efficient min-heap operations

heapq.heappush(diagonals[i - j], mat[i][j])Push element into min-heap for its diagonal

heapq.heappop(diagonals[i - j])Pop smallest element from min-heap to place back

diagonals = collections.defaultdict(list)Initialize map with lists to be used as heaps

import java.util.*;

public class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        // Build min-heaps for each diagonal
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = i - j;
                map.putIfAbsent(key, new PriorityQueue<>());
                map.get(key).offer(mat[i][j]);
            }
        }
        // Replace elements by polling from heaps
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = i - j;
                mat[i][j] = map.get(key).poll();
            }
        }
        return mat;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
        int[][] sorted = sol.diagonalSort(matrix);
        for (int[] row : sorted) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();Map diagonal keys to min-heaps for dynamic sorting

map.putIfAbsent(key, new PriorityQueue<>());Initialize min-heap if absent

map.get(key).offer(mat[i][j]);Add element to min-heap for diagonal

mat[i][j] = map.get(key).poll();Replace matrix element with smallest from min-heap

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> map;
        // Build min-heaps for each diagonal
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                map[i - j].push(mat[i][j]);
            }
        }
        // Replace elements by polling from heaps
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] = map[i - j].top();
                map[i - j].pop();
            }
        }
        return mat;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> matrix = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
    vector<vector<int>> sorted = sol.diagonalSort(matrix);
    for (auto &row : sorted) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

unordered_map<int, priority_queue<int, vector<int>, greater<int>>> map;Map diagonal keys to min-heaps for sorting

map[i - j].push(mat[i][j]);Add element to min-heap for diagonal

mat[i][j] = map[i - j].top();Replace matrix element with smallest from min-heap

map[i - j].pop();Remove used element from min-heap

var diagonalSort = function(mat) {
    const m = mat.length, n = mat[0].length;
    const map = new Map();
    // Build min-heaps for each diagonal
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const key = i - j;
            if (!map.has(key)) map.set(key, []);
            map.get(key).push(mat[i][j]);
        }
    }
    // Convert arrays to min-heaps
    for (const key of map.keys()) {
        map.set(key, map.get(key).sort((a,b) => a - b));
    }
    // Replace elements by polling from heaps
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const key = i - j;
            mat[i][j] = map.get(key).shift();
        }
    }
    return mat;
};

// Driver code
const matrix = [[3,3,1,1],[2,2,1,2],[1,1,1,2]];
console.log(diagonalSort(matrix));

Line Notes

const map = new Map();Map diagonal keys to arrays for grouping elements

map.get(key).push(mat[i][j]);Add element to diagonal group

map.set(key, map.get(key).sort((a,b) => a - b));Sort each diagonal group ascending to simulate min-heap

mat[i][j] = map.get(key).shift();Replace matrix element with smallest from sorted group

⏱

Complexity

TimeO(m * n * log(min(m, n)))

SpaceO(m * n)

Building heaps and polling elements costs O(m*n*log(min(m,n))). Space is O(m*n) for storing all elements in heaps.

💡 This approach is efficient and uses data structures to maintain sorted order dynamically.

Interview Verdict: Accepted

This is a clean and efficient approach often preferred in interviews for its use of priority queues.

📊

All Approaches - One-Glance Tradeoffs

💡 The hash map grouping approach (Approach 2) is recommended for most interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m * n * log(min(m, n)))	O(min(m, n))	No	N/A	Good to mention for intuition; rarely coded fully
2. Hash Map Grouping and Sorting	O(m * n * log(min(m, n)))	O(m * n)	No	N/A	Preferred approach to code in interviews
3. Priority Queues per Diagonal	O(m * n * log(min(m, n)))	O(m * n)	No	N/A	Good alternative; shows knowledge of heaps

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then move to optimized approaches. Practice coding and explaining each step clearly.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach: extracting and sorting each diagonal separately.Explain the grouping by diagonal key (row - col) to simplify sorting.Discuss using priority queues to maintain sorted order dynamically.Code the chosen approach carefully, then test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify diagonals, manipulate matrix indices, and implement sorting efficiently. Clear communication and handling edge cases are critical.

Common Follow-ups

• What if the matrix is very large? → Discuss time and space tradeoffs.
• Can you sort diagonals in descending order? → Modify sorting criteria.
• How to do this in-place without extra space? → Discuss complexity and feasibility.
• What if the matrix is sparse? → Consider data structures for sparse data.

💡 These follow-ups test your adaptability and deeper understanding of the problem constraints and variations.

🔍

Pattern Recognition

When to Use

1) Problem involves sorting or processing diagonals of a matrix. 2) Need to sort elements along diagonals independently. 3) Diagonals identified by row-column difference. 4) Output requires matrix with sorted diagonals.

Signature Phrases

'sort each matrix diagonal''diagonal line of cells starting from top row or left column'

NOT This Pattern When

Problems that sort rows or columns independently without diagonal grouping

Similar Problems

Sort Characters By Frequency - sorting by custom keysGroup Anagrams - grouping elements by keysSort Colors - sorting with constraints

Practice

1. You are given a list of non-negative integers and need to arrange them such that they form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Sort the numbers as strings using a custom comparator that compares concatenations.

B. Use a greedy approach that always picks the largest number first.

C. Generate all permutations of the numbers and select the maximum concatenation.

D. Apply dynamic programming to build the largest number from subproblems.

Solution

1. Step 1: Understand problem constraints

   The problem requires ordering numbers to maximize concatenated value, which is not solved by simple numeric or lexicographic sorting.

2. Step 2: Identify correct approach

   Sorting with a custom comparator comparing concatenations (a+b vs b+a) ensures correct relative order for maximum combined number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Custom comparator sorting is the standard optimal approach [OK]

Hint: Largest number needs custom string concatenation sort [OK]

Common Mistakes:

• Assuming numeric sort or lexicographic sort suffices

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. Given the following code and input nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5, what is the final returned array?

easy

A. [3, 9, 33, 15]

B. [33, 15, 9, 3]

C. [3, 9, 15, 33]

D. [15, 3, 9, 33]

Solution

1. Step 1: Compute transformed values

   For nums = [-4, -2, 2, 4], quad(x) = x² + 3x + 5: -4 -> 16 -12 + 5 = 9 -2 -> 4 -6 + 5 = 3 2 -> 4 + 6 + 5 = 15 4 -> 16 + 12 + 5 = 33

2. Step 2: Two pointers fill from end

   a >= 0, so fill result from end: Compare left_val=9 and right_val=33 -> 33 > 9, place 33 at result[3] Move right pointer left Next compare 9 and 15 -> 15 > 9, place 15 at result[2] Move right pointer left Next compare 9 and 3 -> 9 > 3, place 9 at result[1] Move left pointer right Finally place 3 at result[0] Result array is [3, 9, 15, 33]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output is sorted ascending: [3, 9, 15, 33] [OK]

Hint: Two pointers fill output from end or start based on a sign [OK]

Common Mistakes:

• Confusing index direction for filling output
• Mixing up left and right pointer values

4. The following code attempts to implement the optimal relative sort array solution. Identify the line containing the subtle bug that causes incorrect output when arr1 contains elements not in arr2.

medium

A. Line 9: Missing resetting freq[val] to zero after processing

B. Line 8: Extending result with elements from arr2 order

C. Line 4: Incrementing frequency count for each num

D. Line 11: Extending result with leftover elements

Solution

1. Step 1: Understand frequency usage

   Frequency array counts occurrences; after outputting elements from arr2, freq[val] must be reset to zero to avoid duplicates.

2. Step 2: Identify missing reset

   Line 9 lacks freq[val] = 0, so leftover loop outputs duplicates of arr2 elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Resetting freq[val] prevents duplicate output of arr2 elements [OK]

Hint: Check if frequency counts are zeroed after use [OK]

Common Mistakes:

• Forgetting to reset frequency after outputting arr2 elements
• Misplacing frequency increment or leftover output
• Assuming leftover loop excludes arr2 elements automatically

5. Suppose the input array can contain negative integers and duplicates, and you want to find the maximum gap between successive unique elements in sorted order. Which modification to the bucket sort / pigeonhole approach correctly handles this scenario without sorting the entire array explicitly?

hard

A. Sort the array fully to handle negatives and duplicates, then scan for maximum gap.

B. Use buckets sized to cover only positive numbers and skip negatives during bucketing.

C. Ignore duplicates by using a set before bucketing, then apply the standard bucket approach on unique values.

D. Modify bucket size to be the difference between max and min ignoring duplicates, but keep duplicates in buckets.

Solution

1. Step 1: Handle duplicates

   Duplicates do not affect maximum gap between unique elements, so remove duplicates first.

2. Step 2: Apply bucket approach on unique values

   After deduplication, apply pigeonhole principle buckets over full range including negatives.

3. Step 3: Avoid sorting entire array

   This approach avoids full sorting and correctly handles negatives and duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Deduplication before bucketing preserves correctness [OK]

Hint: Remove duplicates first, then bucket over full range including negatives [OK]

Common Mistakes:

• Ignoring negatives in bucket sizing
• Keeping duplicates causing incorrect gaps
• Sorting entire array defeats bucket approach