Problem

Given an integer array arr, return every element that appears more than once, listed once each, in the order of its first appearance.

Input / Output

• Input: integer array arr.
• Output: list of integers (may be empty).

Examples

Example 1 Input: arr = [4, 3, 2, 4, 1, 3, 5, 4] Output: [4, 3]

Example 2 Input: arr = [1, 2, 3] Output: []

Example 3 Input: arr = [2, 2, 2] Output: [2]

Constraints

• 1 <= n <= 10^5

Approach

Hash map, two passes. Count frequencies, then walk the array and output an element the first time you meet it if its count is greater than 1 (track a reported set so each repeated value is printed once).

Single pass with a seen-set. Maintain seen and reported. For each v: if v in seen and not in reported, output it and add to reported; otherwise add to seen. Output order is the order of the second occurrence — acceptable when the problem only asks for the set.

O(1) space when values are in 1..n. Use the sign trick: for each value v, look at index |v|-1; if arr[|v|-1] is already negative, v is a repeat, else negate it. This modifies the array in place and is a common follow-up.

Complexity

• Time: O(n)
• Space: O(k), or O(1) with the in-place trick.

Reference solution (Python)

from collections import Counter

def repeating(arr):
    freq = Counter(arr)
    out, done = [], set()
    for v in arr:
        if freq[v] > 1 and v not in done:
            out.append(v)
            done.add(v)
    return out

Test cases

Input	Expected
[4,3,2,4,1,3,5,4]	[4,3]
[1,2,3]	[]
[2,2,2]	[2]
[1,2,1,2]	[1,2]