1
\$\begingroup\$

https://leetcode.com/problems/sort-the-matrix-diagonally/

enter image description here

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. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat3, and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

my idea is to run as a BFS on the matrix. each cell visit top and right cells. to form a diagonal and sort it.

please review for performance. it took 30 mins to write the code. review this please as this is a coding interview.

using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ArrayQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/sort-the-matrix-diagonally/
    /// </summary>
    [TestClass]
    public class MatrixDiagonalSortTest
    {
        [TestMethod]
        public void TestMethod1()
        {
            int[][] input = { new[] { 3, 3, 1, 1 }, new[] { 2, 2, 1, 2 }, new[] { 1, 1, 1, 2 } };
            int[][] output = { new[] { 1, 1, 1, 1 }, new[] { 1, 2, 2, 2 }, new[] { 1, 2, 3, 3 } };
            var res = DiagonalSort(input);
            for (int r = 0; r < res.Length; r++)
            {
                CollectionAssert.AreEqual(output[r], res[r]);
            }
            
        }
        public int[][] DiagonalSort(int[][] mat)
        {
            Queue<Cell> Q = new Queue<Cell>();
            Q.Enqueue(new Cell(mat.Length-1, 0, mat[mat.Length-1][0]));
            while (Q.Count > 0)
            {
                List<Cell> tempList = new List<Cell>();
                int count = Q.Count;
                for (int i = 0; i < count; i++)
                {
                    var curr = Q.Dequeue();
                    tempList.Add(curr);
                    int newR = curr.r - 1;
                    int newC = curr.c;
                    if (newR >= 0)//go up
                    {
                        if (Q.FirstOrDefault(x => x.r == newR && x.c == newC) == null)
                        {
                            Q.Enqueue(new Cell(newR, newC, mat[newR][newC]));
                        }

                    }
                    newR = curr.r;
                    newC = curr.c + 1;
                    if (newC <= mat[0].Length - 1)//go right
                    {
                        if (Q.FirstOrDefault(x => x.r == newR && x.c == newC) == null)
                        {
                            Q.Enqueue(new Cell(newR, newC, mat[newR][newC]));
                        }
                    }
                }
                var listValues = new List<int>();
                foreach (var item in tempList)
                {
                    listValues.Add(item.v);
                }
                listValues.Sort();
                for (int i = 0; i < tempList.Count; i++)
                {
                    mat[tempList[i].r][tempList[i].c] = listValues[i];
                }
            }
            return mat;
        }
    }
    [DebuggerDisplay("r ={r}, c={c}, v={v}")]
    public class Cell
    {
        public Cell(int r1, int c1, int v1)
        {
            r = r1;
            c = c1;
            v = v1;

        }
        public int r { get; set; }
        public int c { get; set; }
        public int v { get; set; }
    }
}
\$\endgroup\$
0

1 Answer 1

Reset to default
2
\$\begingroup\$

Few tips

  1. For code quality, consider to give variables/fields more understandeable names.
  2. For immutable Cell fields add readonly, it may affect the performance.
  3. If you know how many items will be put in the collection, construct it with capacity new List<Cell>(count), capacity means initial size for the underlying storage not max items limit.
  4. FirstOrDefault == null can be replaced with !Any.
  5. You may add items directly to listValues i guess, and optimize out tempList or vice-versa. Then Sort by field with Linq, or custom comparer, or implement IComparable for Cell.
  6. Cell can be struct? If yes, you can try to take an advantage of stack allocations (for small amount of data) instead of heap using Span<T>-related optimizations.

For 5th tip, this code (as far as I got the idea)

var listValues = new List<int>();
foreach (var item in tempList)
{
    listValues.Add(item.v);
}
listValues.Sort();
for (int i = 0; i < tempList.Count; i++)
{
    mat[tempList[i].r][tempList[i].c] = listValues[i];
}

Can be optimized as

int i = 0;
foreach (var item in tempList.OrderBy(x => x.v))
{
    mat[tempList[i].r][tempList[i].c] = item.v;
    i++;
}

Btw, I've tested various optimizations from listed above and more but got only insignificant performance boost. The slowest point is here FirstOrDefault(x => x.r == newR && x.c == newC). I have no idea how to improve it without moving the solution to different approach.

Ok, let's do it.

public int[][] DiagonalSort(int[][] mat)
{
    int width = mat[0].Length;
    int height = mat.Length;
    List<int> values = new List<int>(height);
    for (int j = 2 - height; j < width - 1; j++)
    {
        for (int i = 0; i < height; i++)
        {
            int offset = j + i;
            if (offset >= 0 && offset < width)
                values.Add(mat[i][offset]);
        }
        values.Sort();
        for (int i = 0, count = 0; i < height; i++)
        {
            int offset = j + i;
            if (offset >= 0 && offset < width)
                mat[i][offset] = values[count++];
        }
        values.Clear();
    }
    return mat;
}

~15% faster than initial solution.

\$\endgroup\$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.