N-Repeated Element in Size 2N Array

N-Repeated Element in Size 2N Array - Problem

You are given an integer array nums with the following properties:

nums.length == 2 * n
nums contains n + 1 unique values
n of the unique values occur exactly once in the array
Exactly one element of nums is repeated n times

Return the element that is repeated n times.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,3]

› Output: 3

💡 Note: Array length is 4 = 2*2, so n=2. Element 3 appears exactly 2 times, while 1 and 2 appear once each.

Example 2 — Different Arrangement

$ Input: nums = [2,1,2,5,3,2]

› Output: 2

💡 Note: Array length is 6 = 2*3, so n=3. Element 2 appears exactly 3 times, while other elements appear once.

Example 3 — Minimum Size

$ Input: nums = [5,1,5,2,5,3,5,4]

› Output: 5

💡 Note: Array length is 8 = 2*4, so n=4. Element 5 appears exactly 4 times, occupying half the array.

Constraints

2 ≤ nums.length ≤ 2 * 10⁴
nums.length is even
-10⁹ ≤ nums[i] ≤ 10⁹
nums contains exactly n + 1 unique values
Exactly one value appears n times

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 Apple 8 M Microsoft 6

The key insight is that since one element appears n times in a 2n-length array, it occupies more than half the positions. By the pigeonhole principle, this element must appear in at least one adjacent pair. Best approach is adjacent pair checking with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Count Frequencies	O(n)	O(n)	Use a hash map to count frequency of each element in one pass
Brute Force - Count Each Element	O(n²)	O(1)	For each unique element, count its occurrences in the entire array
Adjacent Pair Check - Space Optimal	O(n)	O(1)	Check adjacent elements since the repeated element must appear in at least one adjacent pair

Hash Map - Count Frequencies — Algorithm Steps

Create a hash map to store element frequencies
Iterate through array once, incrementing count for each element
Find and return the element with count equal to n (length/2)

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Array

Go through each element once

Count in Map

Increment count in hash map

Check Count

Return when count reaches n

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int key;
    int count;
} Entry;

int solution(int* nums, int numsSize) {
    Entry entries[1000];
    int entryCount = 0;
    int n = numsSize / 2;
    
    for (int i = 0; i < numsSize; i++) {
        int found = 0;
        for (int j = 0; j < entryCount; j++) {
            if (entries[j].key == nums[i]) {
                entries[j].count++;
                if (entries[j].count == n) {
                    return nums[i];
                }
                found = 1;
                break;
            }
        }
        if (!found) {
            entries[entryCount].key = nums[i];
            entries[entryCount].count = 1;
            if (entries[entryCount].count == n) {
                return nums[i];
            }
            entryCount++;
        }
    }
    
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, hash map operations are O(1)

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n+1 unique elements

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~10 min Avg. Time

950 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Count Frequencies — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler