Thin Out a Sorted Log
EasyArrays & Hashing
Problem
An audit log stores user ids in nums, sorted in non-decreasing order, and the same id may appear many times in a row. Keep only the first occurrence of each id.
Do it in place: compact the distinct values to the front of nums, in order, and then shrink the array so its length equals the number of distinct values (in Python with del nums[k:], in JavaScript by setting nums.length = k). The function returns nothing.
Example 1
- Input:
- nums = [1, 1, 2, 3, 3, 3]
- Output:
- [1, 2, 3]
Three distinct ids remain, in their original order.
Example 2
- Input:
- nums = [-2, 0, 0, 5]
- Output:
- [-2, 0, 5]
Example 3
- Input:
- nums = [4]
- Output:
- [4]
Constraints
- 1 ≤ nums.length ≤ 3 · 10^4
- -10^4 ≤ nums[i] ≤ 10^4
- nums is sorted in non-decreasing order.
- Use O(1) extra space.
Hint
Show the first hint
Because the array is sorted, all copies of a value sit next to each other.
Walkthrough
How to approach it
01Clarify before coding
- Is the input guaranteed sorted? Yes, non-decreasing, so duplicates are adjacent.
- What does 'in place' mean for the result? The first k slots hold the distinct values and the array is then cut to length k.
- Can the array be empty? No, it has at least one element.
02Brute force
Build a new list with every value that differs from the previous one, then copy it back over nums.
Cost: O(n) time but O(n) extra space, which breaks the memory requirement. Deleting duplicates one by one with remove/splice is O(1) extra but O(n²) time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.