Remove Duplicates from Sorted Array
Real-world version: Collapse Repeated OffsetsThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def collapse_offsets(offsets: list[int]) -> list:public Object[] collapseOffsets(int[] offsets)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's