Leetcode Problem Hacks: 881 Boats to Save People

I was doing some recreational programming tonight on LeetCode and I stumbled into an interesting performance case study.

The Problem

This is LeetCode Problem: 881 Boats to Save People.

Boats to Save People

The 

i-th

people[i]

limit

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most 

limit

Return the minimum number of boats to carry every given person.  (It is guaranteed each person can be carried by a boat.)

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

My code solved this problem in a blazing 452ms and 21 MB of memory. Not too shabby!

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        start,end = 0,len(people)-1
        boats = 0
        while start <= end:
            while start < end and people[end] > limit - people[start]:
                boats += 1
                end -= 1
            boats += 1
            start += 1
            end -= 1
        return boats

After completing the problem, I realized that this problem is perfectly suited for Count Sort.

Count Sort

Count sort is one of my favorite algorithms because for the right data it is a sort that works in linear time, that’s O(n)!

Count Sort is a special sorting algorithm that works against data that is guaranteed to fit into a fixed range 

w

n

Count sort works by putting elements in an array of fixed length 

C

C

Here is how I implemented it for this problem. In this example, 

people

count = [0]*(limit+1)
for i in people:
    count[i] += 1
p = 0
for i in range(len(count)):
    while count[i]:
        people[p] = i
        count[i] -= 1
        p += 1

I was thrilled to use my favorite sorting algorithm! Count Sort should be faster than Timsort (python’s built in sorting algorithm). Which has an average performance of O(n * log n) and O(n) space complexity.

Stable Count Sort

My stable count sort solution solved the problem in 552ms and 21.1 MB of memory:

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:

        #Count Sort
        count = [0]*(limit+1)
        for i in people:
            count[i] += 1
        total = 0
        for i in range(limit+1):
            count[i],total = total,count[i]+total
        n = [0]*len(people)
        for i in people:
            n[count[i]] = i
            count[i] += 1
        people = n
        start,end = 0,len(people)-1
        boats = 0
        while start <= end:
            if people[end] <= limit - people[start]:
                start += 1
            boats += 1
            end -= 1
        return boats

There was a slight increase in memory usage, .1 MB. This isn’t unexpected, Timsort uses O(N) space, whereas stable count sort uses O(N+W) space. But I was not expecting to see the runtime increase of +100ms!

Let’s see how the non-stable count sort does.

Non-Stable Count Sort

Non-Stable Count Sort Solution 500ms and 20.1 MB of memory:

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        #Count Sort
        count = [0]*(limit+1)
        for i in people:
            count[i] += 1
        p = 0
        for i in range(len(count)):
            while count[i]:
                people[p] = i
                count[i] -= 1
                p += 1
        start,end = 0,len(people)-1
        boats = 0
        while start <= end:
            if people[end] <= limit - people[start]:
                start += 1
            boats += 1
            end -= 1
        return boats

I was happy to see the decrease in memory use. I predicted an O(w) memory usage, because I modify the 

people

But why did Count Sort not beat out Timsort?

Why would Timsort beat Count Sort?

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

Wikipdia Timsort

Honestly, I don’t know the answer here. But I have some ideas:

Best Case

Timsort has a Best case performance of O(n). This could beat out Count Sort (also O(n) if Timsort’s actual performance is faster.

Timsort is very adaptive and works best with real world data according to Wikipedia. It could just be smarter than me and out perform count sort here.

Timsort is Written in C

The code for Timsort in CPython’s built-in 

sort()

This would absolutely have a big performance impact over my implementation of count sort in Python.

Leetcode is a Poor Test Harness

Leetcode isn’t really meant to measure these kind of performance differences. There are pytest modules that I could use to measure the performance of this code with 1000s of iterations to account for statistical variations.

The tests provided by leetcode are also limited. The inputs are only so large.

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

It could be the case that CPython’s Timsort does out perform Count Sort for these small numbers, but when you get into the millions or billions scale, Count Sort starts to be faster.

Conclusion

I believe Timsort outperformed Count Sort for all the reasons I listed above and probably more reasons that I didn’t even think of!

Software performance is a super hard problem. There are layers and layers of abstractions to dig into, as well as low level physical variance occurring at the atomic level when measuring performance.

This was a fun exercise to go through, and I hope you learned something, I definitely did.

Check out my course on APIs

If you enjoyed this deep dive, you might love my course on APIs!

It is written in a beautiful Notion document and it is packed with awesome learning moments!

If you can't afford this course but still want it, just contact me and I'll give it to you for free.

Also published here.