Three Cheapest Fares with heapq

Medium ⏱ 12 min 61% acceptance ★★★★☆ 4.2

Write cheapest(fares, k) returning the k smallest numbers from a list using heapq.nsmallest — the right tool when k is small relative to a large list, beating a full sort. Mention the complexity difference in the discussion: O(n log k) vs O(n log n).

Examples

Example 1

Input

cheapest([4500, 3200, 7800, 2900], 2)

Output

[2900, 3200]

Explanation

The two lowest fares in ascending order.

Constraints

Use heapq.nsmallest.
Result is ascending.

Topics

Modules & Packagesheapq

Companies

MakeMyTripUberAmazon

Hints

Hint 1

import heapq.

Hint 2

nsmallest(k, iterable) does everything.

← Design a Package Layout Modules Are Singletons →

Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.