703135. Maximum repeating number
Maximum Repeating Number
Slug: maximum-repeating-number4858 Difficulty: Easy Id: 703135 Topic Tags: Arrays, Data Structures, Hash, Algorithms Company Tags: Accolite, Amazon
Summary
Given an array of integers, find the maximum repeating number in the array. A number is considered to be repeating if it appears more than once in the array.
Detailed Explanation
To solve this problem, we can use a hash map to keep track of the frequency of each number in the array. We iterate through the array and for each number, we check if it's already present in our hash map. If it is, we update its count; otherwise, we add it to the map with a count of 1.
We then find the maximum value among all the counts in our hash map. This will be the maximum repeating number in the array. Here's a step-by-step breakdown:
- Initialize an empty hash map
freqMap. - Iterate through the array.
- For each number, check if it's already present in
freqMap. If it is:- Update its count by incrementing the current value by 1.
- If the number is not present in
freqMap, add it with a count of 1. - Find the maximum value among all the counts in
freqMap. This will be the maximum repeating number.
Time complexity: O(n), where n is the size of the array. We iterate through the array once, so the time complexity is linear.
Space complexity: O(min(n, m)), where m is the maximum possible value in the array. In our case, we use a hash map to store the frequency of each number, so the space complexity is proportional to the size of the hash map. Since the size of the hash map cannot exceed the size of the array or the maximum possible value in the array, we can say that the space complexity is O(min(n, m)).
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public class MaximumRepeatingNumber {
public static int findMaxRepeatingNumber(int[] arr) {
Map<Integer, Integer> freqMap = new HashMap<>();
int maxCount = 0;
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
maxCount = Math.max(maxCount, freqMap.get(num));
}
return maxCount;
}
}