LeetCode: Queue Reconstruction by Height C#

Question

https://leetcode.com/problems/queue-reconstruction-by-height/

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers \$(h, k)\$, where \$h\$ is the height of the person and \$k\$ is the number of people in front of this person who have a height greater than or equal to \$h\$. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Please review for performance

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

namespace SortingQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/queue-reconstruction-by-height/
    /// </summary>
    [TestClass]
    public class ReconstructQueueTest
    {
        [TestMethod]
        public void ReconstructQueueExampleTest()
        {
            int[][] people = new int[6][];
            people[0] = new[] { 7, 0 };
            people[1] = new[] { 4, 4 };
            people[2] = new[] { 7, 1 };
            people[3] = new[] { 5, 0 };
            people[4] = new[] { 6, 1 };
            people[5] = new[] { 5, 2 };

            int[][] expected = new int[6][];
            expected[0] = new[] { 5, 0 };
            expected[1] = new[] { 7, 0 };
            expected[2] = new[] { 5, 2 };
            expected[3] = new[] { 6, 1 };
            expected[4] = new[] { 4, 4 };
            expected[5] = new[] { 7, 1 };
            int[][] res = ReconstructQueueClass.ReconstructQueue(people);
            for (var index = 0; index < res.Length; index++)
            {
                CollectionAssert.AreEqual(expected[index], res[index]);
            }
        }
    }

    public class ReconstructQueueClass
    {
        public static int[][] ReconstructQueue(int[][] people)
        {
            int[][] res = new int[people.Length][];
            Array.Sort(people, new PairComparer());

            List<int> list = new List<int>();

            for (int i = 0; i < people.Length; i++)
            {
                list.Add(i); //a list of indices 0,1,2,3,4...
                res[i] = new int[2];
            }

            for (int i = 0; i < people.Length; i++)
            {
                int index = list[people[i][1]]; //the index in the result is the number of people before you
                res[index][0] = people[i][0];
                res[index][1] = people[i][1];
                list.RemoveAt(people[i][1]); // we remove the index from the list so we keep only the un used ones
            }
            return res;
        }
    }

    /// <summary>
    /// sort the people, have min height first
    /// for the same height for example 5,0 and 5,2
    /// 5,2 is before 5,0
    /// </summary>
    public class PairComparer : IComparer<int[]>
    {
        public int Compare(int[] x, int[] y)
        {
            if (x[0] != y[0])
            {
                return x[0] - y[0];// we want min value first
            }
            return y[1] - x[1];
        }
    }
}

Answer 1

API

I assume it's part of the platform requirements, but int[] is a terrible data-structure for storing the (k, h) pair, because it could have any length and implies an ordering that doesn't really exist. This should be a small class or immutable struct. (Not a Tuple, because Tuples are structural, and therefore only solve part of the problem).

Even if this was imposed upon me, I would want to map it to something sensible before doing anything else. This mapping would act as a (necessary) validation layer, to check I'm not being given nonsense.

ReconstructQueueList

This should document what it does.

I don't see the point in initialising every element of res, when you could just assign them a copy of the existing person array when you set them. This makes the code much tidier. I would move the declaration of res toward where it is actually used.

list is a completely meaningless variable name. These are the positions in the queue that you have yet to be assigned, so I will call it positions; however, I'm sure you can think of something much better. I would create positions with Enumerable.Range(0, people.Length), which is more compact and has less scope for errors. I doubt the added overhead will be significant, but feel free to measure it.

PairComparer

PairComparer is not a fantastic name for something that sorts people.

It's good that you've given some description of what the custom comparer does. However, I don't understand the description you provide.

I'd prefer to see x[0].CompareTo(y[0]) instead of x[0] = y[0]: it's much clearer what is going on, and it doesn't risk overflowing for numbers with large magnitude.

Performance

This section is pretty underwhelming

If we ignore the problem size limit of 1100 (where did they find that number?), the main performance concern is the List.Remove(int) calls, which means this algorithm is quadratic in the worst case (though linear in the best case). You can address this by using a data-structure which allows log(n) removal by index. I threw together a simple OrderedShrinkList, where removing every has a cost of n log(n) and n is the number of elements with which it begins, and ran some benchmarks.

Swapping this appears to give a significant performance boost for large problems: it is 10 times faster on a particular random instance of size 200000 gist of code and results (it seems to be slower for smaller ones).

Running small problems (e.g. size 1100 and smaller), the potential inefficiency of List based method is not immediately revealed, and the overhead of my shoddy OrderedShrinkList seems to make it significantly slower. I've run out of energy to keep trying things, but a linked list might actually improve things, because it replacing a linear 'move' with a linear scan, and you can choose at which end to start.

Note: I did run benchmark for some different seeds, and the general trend was similar, but this isn't the most rigorous test ever.