N-Repeated Element in Size 2N Array

Problem Description

Ah, the classic “N-Repeated Element in Size 2N Array” problem! Imagine you’re at a party, and there are twice as many people as there should be, but somehow, one person just can’t stop showing up. You know, the one who thinks they’re the life of the party but really just keeps repeating themselves. In this problem, you’re given an array of size 2N, where N is a positive integer, and you need to find that one element that appears N times.

So, if you have an array like [1, 2, 3, 3], you’d be looking for the number 3, because it’s the only one that decided to crash the party N times.

Code Solution

class Solution {
  public int repeatedNTimes(int[] nums) {
    for (int i = 0; i + 2 < nums.length; ++i)
      if (nums[i] == nums[i + 1] || nums[i] == nums[i + 2])
        return nums[i];
    return nums[nums.length - 1];
  }
}
    

Approach

The approach here is straightforward yet clever. The code iterates through the array and checks if the current element is equal to either the next element or the one after that. If it finds a match, it returns that element. If it doesn’t find any matches during the loop, it simply returns the last element of the array. This works because, in a valid input, the repeated element will always be found in the first few checks.

Time and Space Complexity

• Time Complexity: O(N) - The loop runs through the array once, making it linear in terms of time.
• Space Complexity: O(1) - No additional space is used that scales with input size, just a few variables.

Real-World Example

Let’s say you’re at a concert, and the band has a fan who just can’t stop singing along to their favorite song. This fan is like the repeated element in our array. No matter how many times the band plays, this fan is always there, singing their heart out. In our array, this fan represents the number that appears N times, while the rest of the crowd is just there for the show.