[LeetCode] Queue Reconstruction by Height

Problem: You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example:

Input: people = [[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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Approach: We can solve this question using sorting easily but we need to think about how we want to sort this input array. We will sort this array in the descending order of height but if the heights match for two persons then in the ascending order of position. Let's take an example to understand why.

people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]

Let's apply our sorting:

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

Just see the use of this sorting if just had [7, 0] and [7, 1], we were just done after doing the sorting. Basically it is ensuring first that people[i] has no person of more height on the left that is people[i + 1] to people[n] and second the people with same height are in the right order.

After this sorting we can just have a loop from i = 0 to n and we can insert people[i] in the result array at people[i][1] and that is all. Let's see using the above example only. After sorting the array becomes:

people = [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

result = []

i = 0, people[0] = [7, 0], Insert [7, 0] at 0

result = [[7, 0]]

i = 1, people[1] = [7, 1], Insert [7, 1] at 1

result = [[7, 0],  [7, 1]]

i = 2, people[2] = [6, 1], Insert [6, 1] at 1

result = [[7, 0],  [6, 1], [7, 1]]

i = 3, people[3] = [5, 0], Insert [5, 0] at 0

result = [[5,0], [7, 0],  [6, 1], [7, 1]]

i = 4, people[4] = [5, 2], Insert [5, 2] at 2

result = [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]

i = 5, people[5] = [4, 4], Insert [4, 4] at 4

result = [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

Hopefully the approach is clear now.

Implementation in C#:

        public int[][] ReconstructQueue(int[][] people)

        {

            System.Array.Sort(people, (p1, p2) =>

            {

                int compare = p2[0].CompareTo(p1[0]);

                return compare == 0 ? p1[1].CompareTo(p2[1]) : compare;

            });

            List<int[]> result = new List<int[]>();

            foreach (int[] ppl in people)

            {

                result.Insert(ppl[1], ppl);

            }

            return result.ToArray();

        }

Complexity: O(n^2)