961. N-Repeated Element in Size 2N Array
Approach
Use a HashSet; the first element that fails insertion is the repeated element.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
// Approach: Use a HashSet; the first element that fails insertion is the repeated element.
// Time: O(n) Space: O(n)
public class Solution
{
public int RepeatedNTimes(int[] nums)
{
// Create a HashSet to store unique elements
// Initial capacity is set to n/2 + 1 for optimization
HashSet<int> seenNumbers = new HashSet<int>(nums.Length / 2 + 1);
// Iterate through the array
for (int i = 0; ; ++i)
{
// Try to add current element to the set
// Add() returns false if element already exists
if (!seenNumbers.Add(nums[i]))
// Found the duplicate element that appears n times
return nums[i];
}
}
}