N-Repeated Element in Size 2N Array

Easy
595.

N-Repeated Element in Size 2N Array

N-Repeated Element in Size 2N Array is an easy coding problem on arrays and hash table, asked in Amazon and Adobe interviews.

You are given an array nums of length 2n containing n + 1 distinct values, exactly one of which appears n times.

Return that repeated value.

Example 1

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

Example 2

Input
nums = [2,1,2,5,3,2]
Output
2

Example 3

Input
nums = [5,1,5,2,5,3,5,4]
Output
5

Constraints

  • nums.length is even and at least 4
  • 0 <= nums[i] <= 10000
  • nums contains n + 1 distinct values, one repeated n times.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

N-Repeated Element in Size 2N Array — Problem & Solution

N-Repeated Element in Size 2N Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

N-Repeated Element in Size 2N Array is an easy coding problem on arrays and hash table, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of length 2n containing n + 1 distinct values, exactly one of which appears n times.

Return that repeated value.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • nums.length is even and at least 4
  • 0 <= nums[i] <= 10000
  • nums contains n + 1 distinct values, one repeated n times.

Hints for N-Repeated Element in Size 2N Array

  1. Hint 1

    Every other value appears exactly once, so the first value you see twice is the answer.

  2. Hint 2

    A set is enough — no counting needed.

  3. Hint 3

    The structure also guarantees two copies appear within any window of four, if you want O(1) space.

How to solve N-Repeated Element in Size 2N Array

All other values are unique, so the very first repeat encountered while scanning must be the target.

Approach

  1. Keep a set of values seen so far.
  2. For each element, return it immediately if it is already in the set.
  3. Otherwise add it and continue.

Why it works

Only one value repeats at all, so any collision identifies it. The guarantee that it appears n times means a collision is certain before the array ends.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Counting frequencies and taking the maximum also works but does more work than needed.
  • The 'majority element' voting algorithm is not valid here — the repeated value occupies exactly half the array, not more.

Reference solution

Python

from typing import List

def repeatedNTimes(nums: List[int]) -> int:
    seen = set()
    for x in nums:
        if x in seen:
            return x
        seen.add(x)
    return -1

Java

public static int repeatedNTimes(int[] nums) {
    HashSet<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (!seen.add(x)) return x;
    }
    return -1;
}

C++

int repeatedNTimes(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return x;
        seen.insert(x);
    }
    return -1;
}

JavaScript

var repeatedNTimes = function(nums) {
    const seen = {};
    for (let i = 0; i < nums.length; i++) {
        const k = String(nums[i]);
        if (seen[k] === true) return nums[i];
        seen[k] = true;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets