406. Queue Reconstruction by Height

Medium

Problem:

There is a queue of people, each represented by a pair of integers (h, k), where h is the person's height, and k is the number of people in front of this person who have a height greater or equal to h. Write an algorithm to rearrange the queue such that these values are accurate.

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.

What to learn:

Tuple vs List

1. The first example uses a tuple to store the person's data:

   codeheapq.heappush(heap, (-person[0], person[1]))

2. The second example uses a list to store the person's data:

   codeheapq.heappush(heap, [-person[0], person[1]])

Here's the key distinction between the two:

• Tuple: Tuples are immutable, meaning their values cannot be changed after they are created. So, when a person's data is stored as a tuple, it's "locked in" and cannot be altered unless a new tuple is created. Tuples can be used as dictionary keys or inserted into sets because of this immutability.

• List: Lists are mutable, meaning their values can be changed after they are created. When a person's data is stored as a list, it can be altered directly.

For the specific code and problem you've presented, the practical effect is minimal since the stored items in the heap are not modified after they are added. But in other scenarios, the choice between tuple and list can be more consequential.

As a general rule of thumb:

• Use tuples when you want an ordered collection of items that should not be changed (immutable).

• Use lists when you want an ordered collection of items that you might need to modify (mutable).

In this particular context, using tuples might be slightly more memory-efficient and conceptually clearer, since there's no intention to modify the person's data once it's in the heap.

The memory consumption of both tuples and lists is affected by a combination of factors:

1. Overhead: Both tuples and lists have a fixed overhead for the data structure itself. Lists generally have a higher overhead than tuples because they are designed to be mutable and need to account for potential growth or shrinkage in size.

2. Content: The actual memory used by the elements stored in the tuple or list.

3. Allocation Strategy: Lists typically allocate more memory than is currently necessary to account for future additions. This means that lists might have extra allocated but unused capacity to make append operations more efficient. Tuples don't need to do this because they're immutable.

4. Storage of References: Both lists and tuples store references to objects, not the objects themselves (unless they are primitives). The size of these references is constant regardless of the size of the actual objects.

In practice, for small collections of items, a tuple might use slightly less memory than a list. But the difference is often minimal and may be overshadowed by other considerations, like the need for mutability or other functional requirements.

However, stating that tuples are always more memory-efficient than lists would be misleading. The actual memory usage depends on the implementation details of the Python interpreter and the specific conditions of the program. The most accurate way to measure memory consumption is to use tools or modules like sys.getsizeof() in the context of the application.

To be clear: while there might be slight memory advantages to using a tuple in some contexts, the primary reason to choose between a list and a tuple should be based on the need for mutability versus immutability, rather than memory considerations.

Solution:

Priority itself is used to extract the minimum or maximum value at any given time, so most greedy problems are solved using a priority queue.

The solution can be implemented in the form of a max-heap, where the first value is extracted in descending order, and the second value can be used as the insertion index. Since Python only supports min-heaps, the first value can be negated to implement a min-heap as if it were a max-heap.

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        heap = []
        for person in people:
            heapq.heappush(heap, (-person[0], person[1]))
        
        result = []
        while heap:
            person = heapq.heappop(heap)
            result.insert(person[1], [-person[0], person[1]])
        
        return result