Show problems as
Classic problem #80MediumArrayTwo Pointers

Remove Duplicates from Sorted Array II

Real-world version: Trim Repeats in the Depth Log
Tracked in this browser only
Read Remove Duplicates from Sorted Array II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def trim_repeat_readings(readings: list[int]) -> int:
Java
public int trimRepeatReadings(int[] readings)

More on the same topics