0279MediumArrayTwo Pointers

Trim Repeats in the Depth Log

Tracked in this browser only

Trains the technique from

LeetCode 80Remove Duplicates from Sorted Array 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 depth probe files one figure per sample into readings, measured in metres against sea level, so a sample taken below the surface is negative. The probe files them in non-decreasing order.

The log is too repetitive to archive as it stands: no figure may appear more than twice. Rewrite readings so that the figures which survive sit at the front of the array in the order they were filed, and return the count k of survivors. Whatever sits at index k and beyond in the array afterwards is disregarded.

Carry out the rewrite inside the array you were handed, using only a constant amount of extra space rather than assembling a second array.

Examples

Example 1

Input: readings = [-5, -5, -5, 0, 0, 7]
Output: 5

The figure -5 was filed three times, so one copy goes. The first five slots become -5, -5, 0, 0, 7 and the count 5 is returned.

Example 2

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

Two copies of 0 are allowed to stay, so the first two slots hold 0 and 0 and the count 2 is returned.

Example 3

Input: readings = [-3, -1, 4]
Output: 3

No figure was filed twice, so all three slots stay as they are and the count 3 is returned.

Constraints

1 <= readings.length <= 3 * 10^4
-10^4 <= readings[i] <= 10^4
readings is sorted in non-decreasing order.

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

Java

public int trimRepeatReadings(int[] readings)

The intended approach

Time O(n)Space O(1)

Keep a write index that counts the survivors so far and read the log from front to back. A figure is written out when fewer than two survivors exist yet, or when it differs from the survivor two slots behind the write index, which is exactly the test for whether this value has already been kept twice. Because the write index never overtakes the read position, the rewrite happens safely inside the same array and the write index is the answer.

Pythonentry point: trim_repeat_readings

def trim_repeat_readings(readings):
    # One walk with a write index k.  A reading is kept when fewer than two have
    # been written, or when it differs from the reading two slots back among the
    # ones already written.  Comparing against readings[k - 2], the written slot,
    # rather than against the source position, is what stops a third copy of a
    # value slipping in after earlier drops have shifted things forward.
    # Time: O(n), one pass.  Space: O(1); the rewrite happens inside the argument.
    k = 0
    for v in readings:
        if k < 2 or v != readings[k - 2]:
            readings[k] = v
            k += 1
    return k

The obvious version

Tally how often each figure occurs, walk the distinct figures in the order they first appeared, emit up to two copies of each into a fresh list, then copy that list back over the front of the array and report its length.

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_trim_repeat_readings(readings):
    counts = {}
    order = []
    for v in readings:
        if v not in counts:
            counts[v] = 0
            order.append(v)
        counts[v] += 1
    kept = []
    for v in order:
        take = 2 if counts[v] > 2 else counts[v]
        for _ in range(take):
            kept.append(v)
    for i in range(len(kept)):
        readings[i] = kept[i]
    return len(kept)

How this problem was checked

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