algoadvance

You are given an integer array nums with a length of 2 * n where n is greater than 1. The elements in nums are between 1 and n, inclusive.

The array nums contains n + 1 unique elements, and exactly one of these elements is repeated n times.

Return the element that is repeated n times.

Clarifying Questions

1. Input constraints:
   • nums will have a length of 2 * n where n > 1.
   • All elements in nums are between 1 and n.
   • Exactly one element repeats n times.
2. Output requirements:
   • Return the element that is repeated n times.
3. Examples:
   • 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

Strategy

To solve this problem, we need to identify which element is repeated exactly n times in the array. Given the constraints and properties of the array, a few different methods could work, but for simplicity and efficiency:

1. Hash Map:
   • Traverse the array and count the occurrences of each element using a hash map (dictionary).
   • If any element’s count reaches n, return that element immediately.

This approach ensures that we don’t traverse the array more than necessary and provides a time-efficient solution.

Code

Let’s implement the hash map strategy in Python:

def repeatedNTimes(nums):
    from collections import defaultdict
    
    counts = defaultdict(int)
    
    for num in nums:
        counts[num] += 1
        if counts[num] == len(nums) // 2:
            return num

# Test cases
print(repeatedNTimes([1, 2, 3, 3]))      # Output: 3
print(repeatedNTimes([2, 1, 2, 5, 3, 2])) # Output: 2
print(repeatedNTimes([5, 1, 5, 2, 5, 3, 5, 4])) # Output: 5

Time Complexity

• Time Complexity: O(N), where N is the length of the nums array. We traverse the array once, and dictionary operations (insert and check) are average O(1).
• Space Complexity: O(N), where N is the length of the nums array, as we may need to store counts for all elements in the worst case.

This solution is efficient for the given problem constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?