Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
You are given an n x n square matrix of integers grid. Return the matrix such that:
Example 1:
Input: grid = [[1,7,3],[9,8,2],[4,5,6]]
Output: [[8,2,3],[9,6,7],[4,5,1]]
Explanation:
The diagonals with a black arrow (bottom-left triangle) should be sorted in non-increasing order:
[1, 8, 6] becomes [8, 6, 1].[9, 5] and [4] remain unchanged.The diagonals with a blue arrow (top-right triangle) should be sorted in non-decreasing order:
[7, 2] becomes [2, 7].[3] remains unchanged.Example 2:
Input: grid = [[0,1],[1,2]]
Output: [[2,1],[1,0]]
Explanation:
The diagonals with a black arrow must be non-increasing, so [0, 2] is changed to [2, 0]. The other diagonals are already in the correct order.
Example 3:
Input: grid = [[1]]
Output: [[1]]
Explanation:
Diagonals with exactly one element are already in order, so no changes are needed.
Constraints:
grid.length == grid[i].length == n1 <= n <= 10-105 <= grid[i][j] <= 105Problem summary: You are given an n x n square matrix of integers grid. Return the matrix such that: The diagonals in the bottom-left triangle (including the middle diagonal) are sorted in non-increasing order. The diagonals in the top-right triangle are sorted in non-decreasing order.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[[1,7,3],[9,8,2],[4,5,6]]
[[0,1],[1,2]]
[[1]]
sort-the-matrix-diagonally)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3446: Sort Matrix by Diagonals
class Solution {
public int[][] sortMatrix(int[][] grid) {
int n = grid.length;
for (int k = n - 2; k >= 0; --k) {
int i = k, j = 0;
List<Integer> t = new ArrayList<>();
while (i < n && j < n) {
t.add(grid[i++][j++]);
}
Collections.sort(t);
for (int x : t) {
grid[--i][--j] = x;
}
}
for (int k = n - 2; k > 0; --k) {
int i = k, j = n - 1;
List<Integer> t = new ArrayList<>();
while (i >= 0 && j >= 0) {
t.add(grid[i--][j--]);
}
Collections.sort(t);
for (int x : t) {
grid[++i][++j] = x;
}
}
return grid;
}
}
// Accepted solution for LeetCode #3446: Sort Matrix by Diagonals
func sortMatrix(grid [][]int) [][]int {
n := len(grid)
for k := n - 2; k >= 0; k-- {
i, j := k, 0
t := []int{}
for ; i < n && j < n; i, j = i+1, j+1 {
t = append(t, grid[i][j])
}
sort.Ints(t)
for _, x := range t {
i, j = i-1, j-1
grid[i][j] = x
}
}
for k := n - 2; k > 0; k-- {
i, j := k, n-1
t := []int{}
for ; i >= 0 && j >= 0; i, j = i-1, j-1 {
t = append(t, grid[i][j])
}
sort.Ints(t)
for _, x := range t {
i, j = i+1, j+1
grid[i][j] = x
}
}
return grid
}
# Accepted solution for LeetCode #3446: Sort Matrix by Diagonals
class Solution:
def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
n = len(grid)
for k in range(n - 2, -1, -1):
i, j = k, 0
t = []
while i < n and j < n:
t.append(grid[i][j])
i += 1
j += 1
t.sort()
i, j = k, 0
while i < n and j < n:
grid[i][j] = t.pop()
i += 1
j += 1
for k in range(n - 2, 0, -1):
i, j = k, n - 1
t = []
while i >= 0 and j >= 0:
t.append(grid[i][j])
i -= 1
j -= 1
t.sort()
i, j = k, n - 1
while i >= 0 and j >= 0:
grid[i][j] = t.pop()
i -= 1
j -= 1
return grid
// Accepted solution for LeetCode #3446: Sort Matrix by Diagonals
impl Solution {
pub fn sort_matrix(mut grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = grid.len();
if n <= 1 {
return grid;
}
for k in (0..=n - 2).rev() {
let mut i = k;
let mut j = 0;
let mut t = Vec::new();
while i < n && j < n {
t.push(grid[i][j]);
i += 1;
j += 1;
}
t.sort();
let mut i = k;
let mut j = 0;
while i < n && j < n {
grid[i][j] = t.pop().unwrap();
i += 1;
j += 1;
}
}
for k in (1..=n - 2).rev() {
let mut i = k;
let mut j = n - 1;
let mut t = Vec::new();
loop {
t.push(grid[i][j]);
if i == 0 {
break;
}
i -= 1;
j -= 1;
}
t.sort();
let mut i = k;
let mut j = n - 1;
loop {
grid[i][j] = t.pop().unwrap();
if i == 0 {
break;
}
i -= 1;
j -= 1;
}
}
grid
}
}
// Accepted solution for LeetCode #3446: Sort Matrix by Diagonals
function sortMatrix(grid: number[][]): number[][] {
const n = grid.length;
for (let k = n - 2; k >= 0; --k) {
let [i, j] = [k, 0];
const t: number[] = [];
while (i < n && j < n) {
t.push(grid[i++][j++]);
}
t.sort((a, b) => a - b);
for (const x of t) {
grid[--i][--j] = x;
}
}
for (let k = n - 2; k > 0; --k) {
let [i, j] = [k, n - 1];
const t: number[] = [];
while (i >= 0 && j >= 0) {
t.push(grid[i--][j--]);
}
t.sort((a, b) => a - b);
for (const x of t) {
grid[++i][++j] = x;
}
}
return grid;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.