0051EasyArrayTwo Pointers

Collapse Repeated Offsets

Tracked in this browser only

Trains the technique from

LeetCode 26Remove Duplicates from Sorted 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 probe logs one calibration offset per sweep into the array offsets. An offset is signed, because the probe reads under the reference as readily as over it, and the firmware already files the log in non-decreasing order.

A repeat tells the operators nothing new, so squeeze the log down: each distinct offset has to survive exactly once, and the survivors have to occupy the front slots of offsets, still climbing. Whatever is left sitting in the slots behind them is disregarded.

Squeeze offsets where it lies, using a fixed handful of scratch variables no matter how long the log runs. Building a second array as long as the log and copying the survivors across is not permitted.

Call k the number of distinct offsets. Return a list of two items: k, followed by the list of the first k slots of offsets exactly as they read once you are done. That short copy is only there so the result can be reported, and it does not count against the space rule.

Examples

Example 1

Input: offsets = [-4, -4, 0, 3, 3, 3, 9]
Output: [4, [-4, 0, 3, 9]]

Four distinct offsets survive, so k is 4 and the first four slots read -4, 0, 3, 9. The three slots behind them may hold anything.

Example 2

Input: offsets = [2, 2, 2, 2]
Output: [1, [2]]

Every sweep read the same offset, so a single survivor sits in slot zero.

Example 3

Input: offsets = [5]
Output: [1, [5]]

A log of one sweep has nothing to collapse and is already in the required shape.

Constraints

1 <= offsets.length <= 3 * 10^4
-100 <= offsets[i] <= 100
offsets is filed in non-decreasing order
Only a fixed amount of extra space may be used, aside from the short reported copy

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 collapse_offsets(offsets: list[int]) -> list:

Java

public Object[] collapseOffsets(int[] offsets)

The intended approach

Time O(n)Space O(1) beyond the reported copy

Because the log climbs, a repeat can only ever sit directly behind the value it repeats, so one survivor slot plus one reading position is enough. Keep a write cursor just past the survivors found so far and scan forward: whenever the value under the reader differs from the last survivor, copy it onto the cursor and push the cursor along. The cursor never overtakes the reader, so nothing unread is overwritten.

Pythonentry point: collapse_offsets

def collapse_offsets(offsets):
    write = 1
    for i in range(1, len(offsets)):
        if offsets[i] != offsets[write - 1]:
            offsets[write] = offsets[i]
            write += 1
    return [write, offsets[:write]]

The obvious version

Ignore the space rule and gather survivors in a side list, admitting a value only after a linear search of the survivors so far turns up nothing equal to it. No cursor arithmetic at all. O(n^2).

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_collapse_offsets(offsets):
    kept = []
    for value in offsets:
        already = False
        for other in kept:
            if other == value:
                already = True
                break
        if not already:
            kept.append(value)
    return [len(kept), kept]

How this problem was checked

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