Values Seen Twice

MediumArrays & Hashing

Problem

A badge reader logged n entries in nums. Every badge id is between 1 and n, and each id appears once or twice.

Return every id that appears twice, in ascending order, in O(n) time and O(1) extra space besides the output. You may modify nums.

Example 1

Input:
nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output:
[2, 3]

Example 2

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

Example 3

Input:
nums = [1]
Output:
[]

Constraints

  • 1 ≤ n = nums.length ≤ 10^5
  • 1 ≤ nums[i] ≤ n
  • Each value appears at most twice.

Hint

Show the first hint

Each id v owns slot v - 1. You need that slot to count up to 2 without losing what it originally held.

Walkthrough

How to approach it

01Clarify before coding

  • Can an id appear three times? No, at most twice.
  • Output order? Ascending.
  • May I modify nums? Yes; it does not need to be restored.

02Brute force

Sort and look for equal neighbours, or count with a hash map.

Cost: Sorting: O(n log n) time. Hash map: O(n) time and O(n) space.

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.

Solve it in the browserStart free

This problem is part of Pro.