0733MediumArrayBinary SearchSliding WindowSorting

Discarding Readings Until The Bench Settles

Tracked in this browser only

Trains the technique from

LeetCode 3634Minimum Removals to Balance Array

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 test bench has produced a batch of readings, listed as readings, and a tolerance factor k.

A batch counts as settled when it still holds at least one reading and its largest reading is no more than k times its smallest reading.

You may throw away any readings you choose. What is left over is judged only on the readings still in it, whatever positions they came from.

Return the smallest number of readings you have to throw away to leave a settled batch.

Examples

Example 1

Input: readings = [10, 1, 9, 8], k = 2
Output: 1

Throwing away the reading 1 leaves 10, 9 and 8. The largest of those is 10 and the smallest is 8, and 10 is no more than twice 8, so the batch is settled after one discard.

Example 2

Input: readings = [2, 4], k = 2
Output: 0

The batch already holds 4 as its largest and 2 as its smallest, and 4 is exactly twice 2, which the factor allows, so nothing has to go.

Example 3

Input: readings = [1, 2, 3], k = 1
Output: 2

With a factor of 1 a settled batch has to have every reading equal, and no reading is repeated here, so only one reading can stay and the other two are thrown away.

Constraints

1 <= readings.length <= 10^5
1 <= readings[i] <= 10^9
1 <= k <= 10^5

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 fewest_discards(readings: list[int], k: int) -> int:

Java

public int fewestDiscards(int[] readings, int k)

The intended approach

Time O(n log n) for n readings, dominated by the sort.Space O(n) for the sorted copy.

Whether a leftover batch is settled turns only on its smallest and largest reading, and throwing away a reading strictly between them never helps, so the batches worth considering are exactly the runs of a sorted copy of the readings. Slide a window over that sorted copy: extend the right edge one reading at a time and raise the left edge while the reading at the right edge is more than `k` times the reading at the left edge. The widest window seen is the most readings that can stay, and the answer is everything else. Each edge only ever moves forward, so after the sort the sweep is linear.

Pythonentry point: fewest_discards

def fewest_discards(readings, k):
    # Only the smallest and largest surviving reading matter, so sorting a copy puts
    # every candidate survivor set in one stretch of the sorted order.  Walk a right
    # edge along the sorted copy and pull the left edge up while the largest reading
    # in the stretch is more than k times the smallest.  The widest stretch that
    # holds gives the most readings that can stay.
    # Time O(n log n) for the sort.  Space O(n) for the sorted copy.
    order = sorted(readings)
    n = len(order)
    left = 0
    widest = 0
    for right in range(n):
        while order[right] > k * order[left]:
            left += 1
        if right - left + 1 > widest:
            widest = right - left + 1
    return n - widest

The obvious version

Try every non-empty selection of readings, take its smallest and largest, and keep the biggest selection whose largest is within the factor of its smallest. Report how many readings that leaves out.

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_fewest_discards(readings, k):
    n = len(readings)
    kept = 0
    for mask in range(1, 1 << n):
        low = None
        high = None
        size = 0
        for i in range(n):
            if mask & (1 << i):
                size += 1
                if low is None or readings[i] < low:
                    low = readings[i]
                if high is None or readings[i] > high:
                    high = readings[i]
        if high <= k * low and size > kept:
            kept = size
    return n - kept

How this problem was checked

Reference solution executed against 14 test cases — 14 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