Sponsored
Sponsored
This approach uses a hashmap (or dictionary) to store the count of each element in the array. By iterating through the array and updating the map, we can easily identify the element that repeats n times by checking the count value.
Time Complexity: O(N), where N is the length of the nums array because we iterate over it once.
Space Complexity: O(1), since the hashmap is of a fixed size of 10001.
1import java.util.HashMap;
2
3class Solution {
4 public int repeatedNTimes(int[] nums) {
5 HashMap<Integer, Integer> map = new HashMap<>();
6 for (int num : nums) {
7 map.put(num, map.getOrDefault(num, 0) + 1);
8 if (map.get(num) > 1)
9 return num;
10 }
11 return -1; // Unreachable because of the problem guarantee
12 }
13
14 public static void main(String[] args) {
15 Solution solution = new Solution();
16 int[] nums = {1, 2, 3, 3};
17 System.out.println(solution.repeatedNTimes(nums));
18 }
19}
20The Java solution uses a HashMap to store and update counts for each number in the array. We check whether the count of any number exceeds one while iterating and return that number.
In this method, we first sort the array. If an element is repeated n times and the rest are unique, the repeated element must be at the center of the sorted array, appearing consecutively. Checking the middle indexes should reveal the repeated element.
Time Complexity: O(N log N), due to the sorting process.
Space Complexity: O(1) in place sorting.
1
class Solution {
public int RepeatedNTimes(int[] nums) {
Array.Sort(nums);
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] == nums[i + 1]) return nums[i];
}
return -1; // unreachable
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.RepeatedNTimes(new int[] { 1, 2, 3, 3 }));
}
}
In C#, the array is sorted, and then adjacent index values are compared to find the duplicate which is repeated n times.