Keep the K Smallest Stream Values

Practice Exercise Intermediate Medium Top K Array Heap

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement k_smallest_values(values, k). Return the k smallest values in ascending order, preserving duplicates. If k is zero return []. Assume k <= len(values).

Starter code

def k_smallest_values(values, k):
    pass

Test cases

stream-selection

{
  "args": [
    [
      8,
      3,
      5,
      1,
      4
    ],
    3
  ]
}

Expected: [1,3,4]

preserve-duplicates

{
  "args": [
    [
      2,
      1,
      2,
      1
    ],
    3
  ]
}

Expected: [1,1,2]

Wizard outline

Step 1: Fill a bounded candidate heap
Keep at most k negated values. Negation makes the most replaceable, largest candidate appear at heap index zero.
Step 2: Replace distinct candidates
Accept a later distinct value only when it improves the selected k. The negated heap root represents the largest selected value; multiplicity is added in the final checkpoint.
Step 3: Retain duplicate candidates
Complete the multiset contract and return ascending output. Each heap entry represents one stream occurrence, so equal values remain independent candidates.

Footguns and prerequisites

A normal min-heap ejects the smallest candidate, the opposite of this contract.
Using set discards duplicates that belong in the result.
arrays strings two pointers sliding window

Reviewed references

Python heapq — Heap Queue Algorithm

Recommended approach and implementation

Use a size-k max-heap represented by negated values, replacing its largest candidate when a smaller stream value arrives.

Why it works: After each item the heap contains the k smallest values seen so far: items are added until full, and thereafter only a value smaller than the current selected maximum can improve the set.

import heapq

def k_smallest_values(values, k):
    if k == 0:
        return []
    candidates = []
    for value in values:
        if len(candidates) < k:
            heapq.heappush(candidates, -value)
        elif value < -candidates[0]:
            heapq.heapreplace(candidates, -value)
    return sorted(-value for value in candidates)