Teaching Kids Programming – Algorithms to Find Two Smallest Numbers (Buy Two Chocolates – Heap – Sorting – Linear Scan)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Here is the problem:

You are given an integer array prices representing the prices of various chocolates in a store. You are also given a single integer money, which represents your initial amount of money. You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.

Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return money. Note that the leftover must be non-negative.

Example 1:
Input: prices = [1,2,2], money = 3
Output: 0
Explanation: Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 – 3 = 0 units of money afterwards. Thus, we return 0.

Example 2:
Input: prices = [3,2,3], money = 3
Output: 3
Explanation: You cannot buy 2 chocolates without going in debt, so we return 3.

Constraints:
2 <= prices.length <= 50
1 <= prices[i] <= 100
1 <= money <= 100

It is basically equivalent of finding two Smallest Numbers in an Array

Algorithms to Find Two Smallest Numbers in An Array

We can sort, using heap, or tracking the two smallest numbers:

Sort and Find Two Smallest Elements

Sorting takes O(NLogN) time. For quick sort, the average/optimial time/space complexity is O(NLogN). For space complexity, the average/optimal is O(LogN), and the worst space complexity is O(N).

We sort the array and the first two are the smallest:

1
2
3
4
5
6

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        prices.sort()
        if prices[0] + prices[1] > money:
            return money
        return money - prices[0] - prices[1]

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        prices.sort()
        if prices[0] + prices[1] > money:
            return money
        return money - prices[0] - prices[1]

Using Heap to Find Two Smallest Elements

A Heap is a tree-like data structure where every node is larger or smaller than its children. The root is the minimum for a min heap, and the maximum for a max heap. We can construct a min heap in Python from a given array, that takes O(N) time – however, if we push an element via heappush O(LogN) time to construct a heap with N elements. That will take O(NLogN) time.

So, we heapify the array into a min heap, and heap pop twice to get the two smallest elements:

1
2
3
4
5
6
7

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        heapify(prices)
        x = heappop(prices) + heappop(prices)
        if money >= x:
            return money - x
        return money

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        heapify(prices)
        x = heappop(prices) + heappop(prices)
        if money >= x:
            return money - x
        return money

The overall time complexity is O(N), the space complexity is O(N) where we keep a heap.

Linear Algorithm: Tracking Two Smallest Elements

We can perform a linear scan, so track and update the two smallest element:

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

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        min1 = min2 = inf
        for i in prices:
            if i <= min1:
                min2 = min1
                min1 = i
            elif i <= min2:
                min2 = i        
        if min1 + min2 > money:
            return money
        return money - min1 - min2

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        min1 = min2 = inf
        for i in prices:
            if i <= min1:
                min2 = min1
                min1 = i
            elif i <= min2:
                min2 = i        
        if min1 + min2 > money:
            return money
        return money - min1 - min2

The time complexity is O(N), the space complexity is O(1). Therefore, among all three approaches, this algorithm is the optimal in terms of time and space complexity.

–EOF (The Ultimate Computing & Technology Blog) —