406.Queue Reconstruction by Height

Tags: [sort], [insert_element_to_array]

Com: {g}

Link: https://leetcode.com/problems/queue-reconstruction-by-height/?tab=Description

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers(h, k), where his the height of the person and kis 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]]

Better Solution:

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        if not people:
            return []

        people.sort(cmp=self.compare_people)
        result = []
        for p in people:
            result.insert(p[1], p)

        return result

    def compare_people(self, p1, p2):
        if p1[0] == p2[0]:
            return p1[1] - p2[1]
        else:
            return -(p1[0] - p2[0])

Revelation:

• The reason why we sort people mainly based on height(descending order), then based on k(ascending order) is that, first we sort people mainly based on height (descending) which guarantees that all people in right side is shorter than the people than left side, then we can insert the people on right side based on the k. For example, k = 3, then we just insert this person into the result array at where index = 3, because all people before are higher or equal to the current person, and we put it at index = 3, which guarantees that there are 3 people has greater or equal height to him.

Note:

• Time complexity = O(n^2), n is the number of the elements in the give array.

Solution: sort, insert_element_to_array

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        if not people or len(people) <= 1:
            return people

        people = sorted(people, cmp=self.compare_person)

        new_people = []
        index = 0
        while index < len(people):
            if not new_people or new_people[-1][0] == people[index][0]:
                new_people.append(people[index])
            else:
                self.insert_person(new_people, people[index])
            index += 1

        return new_people

    def insert_person(self, people, person):
        target_index = person[1]
        # insert th person before the target index
        people.append(None)
        for i in xrange(len(people) - 1, target_index, -1):
            people[i] = people[i - 1]

        people[target_index] = person

    @staticmethod
    def compare_person(p1, p2):
        if p1[0] == p2[0]:
            return p1[1] - p2[1]
        return -(p1[0] - p2[0])

Revelation:

• Sort the people, and get the first group, then insert the remaining people into the group.
• For example: after sorting, we will have the people arr: [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]], the first group is [[7, 0], [7, 1]].

Note:

• Time complexity = O(nlgn) + O(n^2) = O(nlgn + n^2) = O(n^2), n is the number of the people in the given array.
• Should be familiar with how to insert the element to array at target index.

Time Limited Exceeded

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        if not people or len(people) <= 1:
            return people

        result = [[]]
        buff = []
        index_set = set()
        self.permutate(people, index_set, buff, result)
        return result[0]

    def permutate(self, people, index_set, buff, result):
        # base case
        if len(buff) == len(people):
            if self.valid(buff):
                result[0] = list(buff)
            return

        for i in xrange(len(people)):
            if i in index_set:
                continue

            index_set.add(i)
            buff.append(people[i])

            # recursion
            self.permutate(people, index_set, buff, result)

            buff.pop()
            index_set.remove(i)

    def valid(self, people):
        for i in xrange(len(people)):
            person = people[i]
            counter = 0
            for j in xrange(0, i):
                if people[j][0] >= person[0]:
                    counter += 1

            if counter != person[1]:
                return False

        return True

Revelation:

• Try to build all permutations, and do validation on each one, finally get the valid one.

Note:

• Time complexity = O(n!), n is the number of people in the given array. There are n! permutations.