O(n sqrt(n)) solution


  • 14

    Based on this solution which I first saw brought up by @bigoffer4all here (and which I explained here):

    def reconstructQueue(self, people):
        queue = []
        for p in sorted(people, key=lambda (h, t): (-h, t)):
            queue.insert(p[1], p)
        return queue
    

    That takes O(n^2) because each insert into the list takes O(n).

    Instead of just one long list of all people, I break the queue into O(sqrt(n)) blocks of size up to sqrt(n). Then to insert at the desired index, I find the appropriate block, insert the person into that block, and potentially have to break the block into two. Each of those things takes O(sqrt(n)) time.

    def reconstructQueue(self, people):
        blocks = [[]]
        for p in sorted(people, key=lambda (h, t): (-h, t)):
            index = p[1]
    
            for i, block in enumerate(blocks):
                m = len(block)
                if index <= m:
                    break
                index -= m
            block.insert(index, p)
            if m * m > len(people):
                blocks.insert(i + 1, block[m/2:])
                del block[m/2:]
    
        return [p for block in blocks for p in block]
    

    "Unfortunately", Python's list.insert is really fast compared to doing things in Python myself, and with the inputs allowed here (less than 1100 people), the O(n^2) solution wins. Locally I tested with larger inputs, and around 200000 people the two solutions were about equally fast. With 300000 people, the O(n sqrt(n)) solution was about factor 1.25 faster, and with a million people, the O(n sqrt(n)) solution was about factor 2.2 faster

    The testing code:

    # The original O(n^2) solution.
    class Solution(object):
        def reconstructQueue(self, people):
            queue = []
            for p in sorted(people, key=lambda (h, t): (-h, t)):
                queue.insert(p[1], p)
            return queue
    nsquared = Solution().reconstructQueue
    
    # The O(n sqrt(n)) solution.
    class Solution(object):
        def reconstructQueue(self, people):
            blocks = [[]]
            for p in sorted(people, key=lambda (h, t): (-h, t)):
                index = p[1]
    
                for i, block in enumerate(blocks):
                    m = len(block)
                    if index <= m:
                        break
                    index -= m
                block.insert(index, p)
                if m * m > len(people):
                    blocks.insert(i + 1, block[m/2:])
                    del block[m/2:]
    
            return [p for block in blocks for p in block]
    nsqrtn = Solution().reconstructQueue
    
    # Generate a large test case and time it.
    from bisect import bisect
    from random import randint, shuffle
    from timeit import timeit
    n = 300000
    heights = [randint(1, n) for _ in range(n)]
    standing = []
    people = []
    for h in heights:
        i = bisect(standing, -h)
        standing.insert(i, -h)
        people.append([h, i])
    shuffle(people)
    for solution in nsquared, nsqrtn, nsquared, nsqrtn:
        print timeit(lambda: solution(people), number=1)
    

  • 0

    @StefanPochmann This is my O(n^2) solution that doesn't get accepted, though...

    class Solution(object):
        def reconstructQueue(self, people):
            def count(stack, h):
                return sum(e[0] >= h for e in stack)
                
            people.sort(key=lambda x:x[1])
            stack = []
            for person in people:
                cache = []
                while count(stack, person[0]) > person[1]:
                    cache.append(stack.pop())
                stack.append(person)
                stack.extend(cache[::-1])
            return stack
    
    

  • 0

    @agave That's not O(n^2) but O(n^3). Consider inputs like [[n, 0], [n-1, 0], ..., [2, 0], [1, 0]].


  • 0

    @StefanPochmann Why is O(n^2) at each iteration and not O(n)?


  • 0

    @agave In each of the O(n) for-loop iterations you have O(n) while-loop iterations and in each of those you have O(n) for the sum in count.


  • 0

    @StefanPochmann said in O(n sqrt(n)) solution:

    @agave In each of the O(n) for-loop iterations you have O(n) while-loop iterations and in each of those you have O(n) for the sum in count.

    Yeah you're right.


  • 0

    @agave I just changed it to use count only before each while-loop and it got accepted in 1652 ms, still beating 1.91% of Python submissions :-)


  • 0

    @StefanPochmann can you post the code here?


  • 0

    @agave I should maybe edit+retest it before posting here, but whatever...

    def reconstructQueue(self, people):
        def count(stack, h):
            return sum(e[0] >= h for e in stack)
            
        people.sort(key=lambda x:x[1])
        stack = []
        for person in people:
            cache = []
            cunt = count(stack, person[0])
            while cunt > person[1]:
                cache.append(stack.pop())
                cunt -= cache[-1][0] >= person[0]
            stack.append(person)
            stack.extend(cache[::-1])
        return stack

  • 0

    @StefanPochmann nice variable name, cunt! Hahaha!
    Yeah, I understand. I would've probably done that optimization, if I had more time in this period :)


  • 0
    P

    Doesn't the sort itself take O(nlog(n))?


  • 0

    @peteraristo Yes. So?


  • 0
    S
    This post is deleted!

  • 3
    Z

    The quadratic algorithm is beautiful and I was impressed by the second technique when I first saw it here:
    http://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/
    Thank for for sharing all your thought with us!


  • 0
    H

    Can you explain why you split the block if

    m * m > len(people)
    

    Isn't the size of the block m + 1 after inserting, so shouldn't you check

    (m + 1) * (m + 1) > len(people)
    

    Not that it's a huge deal, just want to understand better. Cool method. Thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.