[PYTHON] Let Code Day 46 starting from scratch "406. Queue Reconstruction by Height"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day45 starting from zero "1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree"

I'm currently solving the Top 100 Liked Questions Medium. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

problem

406. Queue Reconstruction by Height

The difficulty level is Medium. Excerpt from Top 100 Liked Questions.

Suppose you have a random list of people in the queue. Each person consists of a pair of integers, (h, k), where h is the height of the person and k is the person who is in front of the person and has a height greater than or equal to h. Refers to the number of people.

In this problem, we design an algorithm that reconstructs a given queue.

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]]

solution

It is a good problem that you need to organize the two integers and formulate an accurate algorithm.

In the case of such a problem, it will be easier to understand if the problem is divided into small pieces and each process is considered independently.

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        if not people: return []
        dic, height, res = {}, [], []
        for i in range(len(people)):
            p = people[i]
            if p[0] in dic:
                dic[p[0]] += (p[1], i),
            else:
                dic[p[0]] = [(p[1], i)]
                height += p[0],
        height.sort()
        for h in height[::-1]:
            dic[h].sort()
            for p in dic[h]:
                res.insert(p[0], people[p[1]])
        return res
# Runtime: 88 ms, faster than 99.14% of Python3 online submissions for Queue Reconstruction by Height.
# Memory Usage: 14.3 MB, less than 5.88% of Python3 online submissions for Queue Reconstruction by Height.

Very fast! If you check the discuss carefully, [this] I was surprised almost with (https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89345/Easy-concept-with-PythonC%2B%2BJava-Solution).

That's all for this time. Thank you for your hard work.