0800HardTwo PointersStackTreeDepth-First SearchBinary Search TreeHeap (Priority Queue)Binary Tree

K Nearest Meter Readings

Tracked in this browser only

Trains the technique from

LeetCode 272Closest Binary Search Tree Value II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A water utility files every meter reading it has ever taken into a binary search tree keyed by the reading itself: for any filed reading, everything in the branch to its left is smaller and everything in the branch to its right is larger. No two filed readings are the same.

The tree arrives as readings, a level-order listing. Its first entry is the reading at the top of the tree. After that, the listing gives the left branch then the right branch of each reading already listed, in the order those readings appear, writing null where a branch is empty. Slots below a null are never written down, and the trailing run of null entries is left off.

An auditor supplies target, a figure that need not be a whole number and may fall outside the range of the filed readings, and asks for the k readings nearest to it. Rank the filed readings by the size of the gap |reading - target|, smallest gap first; when two readings sit at exactly the same gap, the smaller reading ranks first. Take the first k readings of that ranking.

Return those k readings in ascending order. You are told that k never exceeds the number of filed readings.

Examples

Example 1

Input: readings = [20, 9, 35, 4, 14, 27, 41], target = 15.0, k = 3
Output: [9, 14, 20]

The filed readings are 4, 9, 14, 20, 27, 35 and 41, with gaps to 15 of 11, 6, 1, 5, 12, 20 and 26. The three smallest gaps belong to 14, 20 and 9, which come back in ascending order.

Example 2

Input: readings = [50, 40, null, 30, null, 20, null, 10], target = 25.0, k = 3
Output: [10, 20, 30]

Gaps to 25 are 25, 15, 5, 5 and 15 for readings 50, 40, 30, 20 and 10. Readings 20 and 30 take the first two places at a gap of 5, and the third place is contested at a gap of 15 by 10 and 40, where the smaller reading 10 ranks first.

Example 3

Input: readings = [10, null, 20, null, 30, null, 40], target = 35.0, k = 1
Output: [30]

Readings 30 and 40 both sit 5 away from 35, and the smaller of two equally close readings ranks first, so the single answer is 30.

Constraints

The number of readings filed in the tree is n.
1 <= k <= n <= 10^4
1 <= readings.length <= 2 * 10^4
0 <= readings[i] <= 10^9
-10^9 <= target <= 10^9
An entry of readings that is null marks an empty branch rather than a reading.
readings[0] is never null, and no reading appears twice.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def nearest_readings(readings: list[int | None], target: float, k: int) -> list[int]:

Java

public List<Integer> nearestReadings(Integer[] readings, double target, int k)

The intended approach

Time O(m + h + k log k) for a listing of m slots, a tree of height h and k requested readings: one pass to wire the tables, O(h) for the walk down, amortised O(1) stack work per pick, and a final sort of the k readings.Space O(m) for the index tables, plus O(h) for the two stacks and O(k) for the returned list.

Wire the listing into left and right index tables with a queue sweep. Then walk down from the top once, dropping each reading that is not above the target onto a `below` stack and each reading above it onto an `above` stack; because the tree is ordered, the top of `below` is the largest filed reading not above the target and the top of `above` is the smallest filed reading above it. Taking a reading off a stack and then pushing the spine that follows it turns each stack into a step-by-step scanner running away from the target, so k rounds of comparing the two gaps collect the k nearest readings; a tie hands the round to the `below` side, which holds the smaller reading. Sort the k collected readings before returning them.

Pythonentry point: nearest_readings

def _decode(listing):
    """Compact level-order listing -> (values, left, right) index tables."""
    if not listing or listing[0] is None:
        return [], [], []
    left = [-1] * len(listing)
    right = [-1] * len(listing)
    queue = [0]
    head = 0
    slot = 1
    while head < len(queue) and slot < len(listing):
        here = queue[head]
        head += 1
        if slot < len(listing):
            if listing[slot] is not None:
                left[here] = slot
                queue.append(slot)
            slot += 1
        if slot < len(listing):
            if listing[slot] is not None:
                right[here] = slot
                queue.append(slot)
            slot += 1
    return list(listing), left, right


def _encode(values, left, right):
    """(values, left, right) index tables -> compact level-order listing."""
    if not values:
        return []
    out = [values[0]]
    order = [0]
    head = 0
    while head < len(order):
        here = order[head]
        head += 1
        for table in (left, right):
            kid = table[here]
            if kid == -1:
                out.append(None)
            else:
                out.append(values[kid])
                order.append(kid)
    while out and out[-1] is None:
        out.pop()
    return out

def nearest_readings(readings, target, k):
    values, left, right = _decode(readings)

    def slide(stack, first, then):
        # take the next reading off this side, then push the spine that follows it
        node = stack.pop()
        step = first[node]
        while step != -1:
            stack.append(step)
            step = then[step]
        return values[node]

    # one walk down from the root splits the path into a stack of readings that
    # are not above the target, largest on top, and a stack of readings above
    # it, smallest on top; neither walk recurses
    below = []
    above = []
    here = 0 if values else -1
    while here != -1:
        if values[here] <= target:
            below.append(here)
            here = right[here]
        else:
            above.append(here)
            here = left[here]
    picked = []
    for _ in range(k):
        take_below = bool(below)
        if below and above:
            take_below = target - values[below[-1]] <= values[above[-1]] - target
        if take_below:
            picked.append(slide(below, left, right))
        else:
            picked.append(slide(above, right, left))
    picked.sort()
    return picked

The obvious version

Never build a tree at all: the filed readings are exactly the non-null entries of the listing. Sort them all by the pair (gap to the target, reading), cut the first k off the front and sort those k into ascending order.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_nearest_readings(readings, target, k):
    marks = [v for v in readings if v is not None]
    ranked = sorted(marks, key=lambda v: (abs(v - target), v))
    return sorted(ranked[:k])

How this problem was checked

Reference solution executed against 21 test cases — 21 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in