# O(n sqrt(n)) solution

• 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)

• @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

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

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

• @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.

• @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.

• @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 :-)

• @StefanPochmann can you post the code here?

• @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

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

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

• @peteraristo Yes. So?

• This post is deleted!

• 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!

• 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.

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