Teaching Kids Programming – Two Pointer Algorithm to Rescue People in Rocketship

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers weights representing peoples’ weights and an integer limit representing the weight limit of one rocket ship. Each rocketship can take at most two people. Return the minimum number of rocket ships it would take to rescue everyone to Mars.

Constraints
n ≤ 100,000 where n is the length of weights
max(weights) ≤ limit

Example 1
Input
weights = [200, 300, 200]
limit = 400
Output
2
Explanation
It would take one rocket ship to take the two people whose weights are 200, and another to take the person whose weight is 300.

Hint #1
Note that we must put the heaviest person in a rocket ship. Can we pair them with someone else?

Hint #2
in every trip we must take at least one person.

Hint #3
Think greedy!

Hint #4
Will sorting help?

Two Pointer Algorithm to Carry People in Rocketship

We can apply the greedy strategy. First sort the people by weights which takes O(NLogN) time. Then, we need to pick the current heaviest person, and check if he/she can go with the current most lightest person.

If the most heaviest cannot go with the most lightest, it means he/she cannot go with any other person as well. If the most heaviest can go with the most lightest, it also means the most lightest person can also go with any other person. Thus, we can use Two Pointer Algorithm – to choose the most heaviest person and most lightest person if fit.

So, the strategy is Greedy, and we first perform the sorting, to make the array of weights in ascending order, and then apply Two Pointer. Take the lightest one (on the left) if possible (to pair with the heaviest one on the right).

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def minNumberOfRocket(self, weights, limit):
        weights.sort()
        ans = 0
        i, j = 0, len(weights) - 1
        while i <= j:
            cur = weights[j]
            j -= 1
            if cur + weights[i] <= limit:
                i += 1
            ans += 1
        return ans

class Solution:
    def minNumberOfRocket(self, weights, limit):
        weights.sort()
        ans = 0
        i, j = 0, len(weights) - 1
        while i <= j:
            cur = weights[j]
            j -= 1
            if cur + weights[i] <= limit:
                i += 1
            ans += 1
        return ans

The overall time complexity is O(NLogN) due to sorting. The space complexity is O(1). We can also implement using deque:

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def minNumberOfRocket(self, weights, limit):
        weights.sort()
        data = deque(weights)
        ans = 0
        while data:
            cur = data.pop()
            if len(data) > 0 and cur + data[0] <= limit:
                cur += data.popleft()                
            ans += 1
        return ans

class Solution:
    def minNumberOfRocket(self, weights, limit):
        weights.sort()
        data = deque(weights)
        ans = 0
        while data:
            cur = data.pop()
            if len(data) > 0 and cur + data[0] <= limit:
                cur += data.popleft()                
            ans += 1
        return ans

Here, cur=data.pop() which pops the last element from the queue or deque and return it, it is effectively the same as following but shorter.

1
2

cur = data[-1]
data.pop()

cur = data[-1]
data.pop()

Time complexity is O(NLogN) and the space complexity is O(N) as we are using a double-ended queue.

–EOF (The Ultimate Computing & Technology Blog) —