1329. Sort the Matrix Diagonally

leetcode medium

#array#csharp#hash-table#heap#leetcode#matrix#medium#queue#sort#string

Task

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

Input: mat = [[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]]

C# solution

matched/original

public class Solution {
    public int[][] DiagonalSort(int[][] mat) {
        int m = mat.Length;
        int n = mat[0].Length;
        var diagonals = new Dictionary<int, PriorityQueue<int, int>>();
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                if (!diagonals.ContainsKey(key)) {
                    diagonals[key] = new PriorityQueue<int, int>();
                }
                diagonals[key].Enqueue(mat[row][col], mat[row][col]);
            }
        }
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                mat[row][col] = diagonals[key].Dequeue();
            }
        }
        return mat;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int[][] DiagonalSort(int[][] mat) {
        int m = mat.size();
        int n = mat[0].size();
        var diagonals = new unordered_map<int, PriorityQueue<int, int>>();
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                if (!diagonals.count(key)) {
                    diagonals[key] = new PriorityQueue<int, int>();
                }
                diagonals[key].Enqueue(mat[row][col], mat[row][col]);
            }
        }
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                mat[row][col] = diagonals[key].Dequeue();
            }
        }
        return mat;
    }
}

Java solution

matched/original

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        Map<Integer, PriorityQueue<Integer>> diagonals = new HashMap<>();

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                diagonals.putIfAbsent(key, new PriorityQueue<>());
                diagonals.get(key).add(mat[row][col]);
            }
        }

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                mat[row][col] = diagonals.get(key).poll();
            }
        }

        return mat;
    }
}

Go solution

matched/original

func diagonalSort(mat [][]int) [][]int {
    m := len(mat)
    n := len(mat[0])
    diagonals := make(map[int]*PriorityQueue)

    for row := 0; row < m; row++ {
        for col := 0; col < n; col++ {
            key := row - col
            if diagonals[key] == nil {
                diagonals[key] = NewPriorityQueue()
            }
            diagonals[key].Push(mat[row][col])
        }
    }

    for row := 0; row < m; row++ {
        for col := 0; col < n; col++ {
            key := row - col
            mat[row][col] = diagonals[key].Pop().(int)
        }
    }

    return mat
}

type PriorityQueue struct {
    items []int
}

func NewPriorityQueue() *PriorityQueue {
    return &PriorityQueue{items: []int{}}
}

func (pq *PriorityQueue) Push(x int) {
    pq.items = append(pq.items, x)
    pq.up(len(pq.items) - 1)
}

func (pq *PriorityQueue) Pop() interface{} {
    n := len(pq.items) - 1
    pq.swap(0, n)
    pq.down(0, n)

    item := pq.items[n]
    pq.items = pq.items[:n]
    return item
}

func (pq *PriorityQueue) up(j int) {
    for {
        i := (j - 1) / 2
        if i == j || pq.items[i] <= pq.items[j] {
            break
        }
        pq.swap(i, j)
        j = i
    }
}

func (pq *PriorityQueue) down(i, n int) {
    for {
        j := 2*i + 1
        if j >= n || j < 0 {
            break
        }
        if k := j + 1; k < n && pq.items[k] < pq.items[j] {
            j = k
        }
        if pq.items[i] <= pq.items[j] {
            break
        }
        pq.swap(i, j)
        i = j
    }
}

func (pq *PriorityQueue) swap(i, j int) {
    pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
}

Explanation

Algorithm

Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

Вставьте значения в хеш-карту, используя разность между индексами строки и столбца как ключ, чтобы собирать элементы на одной и той же диагонали.

Извлеките значения из хеш-карты и обновите матрицу, заполняя ее отсортированными значениями диагоналей. Верните отсортированную матрицу.

😎