Java - Find maximum number of duplicates within an array

Question

I am utilizing a HashSet for finding the maximum number of duplicates of a value in a sorted Integer array. But my algorithm doesn't seem to work, not returning the desired results.

Set variables storing the number of duplicates found (0), and the maximum number of duplicates (0). 
Set a HashSet that stores the unique values of an array.
Sort the array to be ready for comparison.

Loop through each value of the array
    If the HashSet of unique values contains the current value:
        Increment the duplicate Count

    If the currentValue is not equal to the previous value:
        If the duplicateCount is greater than the maximum Count:
            maximumCount becomes duplicateCount
            Reset duplicateCount to 0

Java Code:

HashSet<Integer> uniqueValues = new HashSet<Integer>(valueSequenceList);

int duplicateCount = 0;
int maxCount = 0;
Arrays.sort(valueSequence);

for (int i = 0; i < valueSequence.length; i++)
{
    if (uniqueValues.contains(valueSequence[i]))
    {
        duplicateCount++;
    }
    if (i > 0 && valueSequence[i] != valueSequence[i-1])
    {
        if (duplicateCount > maxCount)
        {
            maxCount = duplicateCount;
            duplicateCount = 0;
        }
    }
}

Example:
Input: [4, 4, 10, 4, 10]
Output: 4 Duplicates (There are supposed to be a maximum of 3 duplicates - Total number of values that are the same).

Your example is not sorted, while the question says it should be. — amit, Jul 02 '15 at 06:57
@amit I sorted the array in my code. I forgot to add it onto the question. — Henry Zhu, Jul 02 '15 at 06:59
@HenryIsVeryPro Then update the question instead of putting up a comment! — GhostCat, Jul 02 '15 at 06:59
@HenryIsVeryPro, you don't need a HashSet, just check `valueSequence[i] == valueSequence[i-1]`. — aioobe, Jul 02 '15 at 07:01
`HashSet` would remove any duplicate item (it's a set...).... Not sure what you're doing. — Reut Sharabani, Jul 02 '15 at 07:02
Please note that you got answers to different questions. I think your question is not clear enough. Should an input of [4,2,4,3,2,3,4] return an output of 3 (since 4 appears 3 times) or 4 (number of duplicates, which is also the length of the array minus the size of the HashSet)? — Eran, Jul 02 '15 at 07:15

score 3 · Accepted Answer · edited May 23 '17 at 12:00

This is the Element Distinctness Problem - which is explained with details in the thread: Find duplicates in an array.

The mentiones thread discusses solutions to the problem, and shows lower bounds as well (cannot be done better than O(nlogn) without using a hash table.

So, if your data is not sorted - you could sort and iterate (as follows), or use a hash set - and then you don't need to sort the array.

If you first sort the array, or the array is already sorted, a single iteration will do:

Single iteration on a sorted array:

if (arr == null || arr.length == 0) return 0;
int last = arr[0];
int numDupes = 1;
for (int i = 1; i < arr.length; i++) { 
   if (arr[i] == last) numDupes++;
   last = arr[i];
}

Using a HashSet (no need to sort):

if (arr == null) return 0;
Set<Integer> set = new HashSet<>();
int numDupes = 0;
for (int x : arr) { 
    if (set.contains(x)) numDupes++;
    set.add(x);
}

If you are looking for the maximal number some element repeats (and not total number of repeats), you can use the same approach but slightly different:

Hashing solution - use a histogram:

Map<Integer,Integer> histogram = new HashMap<>();
for (int x : arr) { 
  if (!histogram.containsKey(x)) histogram.put(x,1); 
  else histogram.put(x,histogram.get(x) + 1);
}
int max = 0;
for (int x : histogram.values) max = max > x ? max : x;
return max;

Sorted array solution:

if (arr == null || arr.length == 0) return 0;
int last = arr[0];
int max = 0;
int currNumDupes = 1;
for (int i = 1; i < arr.length; i++) { 
   if (arr[i] == last) currNumDupes++;
   else { 
        max = max > currNumDupes ? max : currNumDupes;
        currNumDupes = 1;
   }
   last = arr[i];
}
max = max > currNumDupes ? max : currNumDupes; //if the most dupes is from the highest element

You can do `if (!set.add(x)) numDupes++;` instead. – aioobe Jul 02 '15 at 07:05 — aioobe, Jul 02 '15 at 07:05

Eran · Answer 2 · 2015-07-02T07:27:38.393

EDIT : I'm assuming (based on your code) that the goal is to find the number of appearances of the number that appears the most in the array. Calling it "maximum number of duplicates" is misleading.

First of all, the HashSet is useless. You add all the elements to it up front, which means uniqueValues.contains(valueSequence[i]) is always true.

Now, you only want to increment the duplicateCount if you still haven't moved to the next element :

for (int i = 0; i < valueSequence.length; i++)
{
    if (i == 0 || valueSequence[i] == valueSequence[i-1])
    {
        duplicateCount++;
    }
    else
    {
        if (duplicateCount > maxCount)
        {
            maxCount = duplicateCount;                
        }
        duplicateCount = 1; // another small fix
    }
}
if (duplicateCount > maxCount)
    maxCount = duplicateCount;
}

If the goal is to find the number of duplicates, you can do it without any loop (since the number of duplicates is the total number of elements minus the number of unique elements) :

HashSet<Integer> uniqueValues = new HashSet<Integer>(valueSequenceList);
int duplicateCount = valueSequenceList.size() - uniqueValues.size();

Small issues with the code (1) in the `else` clause - it should reset `duplicateCount` to 1 (you just found the first duplicate, which is different from last element) (2) It does not handle the case where the max duplicates is at the end (2,2,3,3,3,3,3 for example) — amit, Jul 02 '15 at 07:23

Reut Sharabani · Answer 3 · 2015-07-02T07:24:16.160

Suggestion:

You could use a simple Map<Integer, Integer> where the key is the item value, and the value is the count of that item.

This would make the code simple - no need to sort:

Map<Integer, Integer> count = new HashMap<Integer, Integer>();

for (Integer item : list){
    if (count.containsKey(item)){
        // increate count
        count.put(item, count.get(key) + 1);
    } else {
        // no item yet - set count to 1
        count.put(item, 1);
    }
}

You could now use something like Collections.max to find the maximum Integer value on count.values() - or even write a Comparator<Entry<Integer, Integer>> for the entries to find the maximal Map.Entry<Integer, Integer> from count.entrySet() (preferable, can be used with Collections.max).

Note: You could use something like MutableInt (Apache commons) or even AtomicInt for mutable map values. I haven't tested the differences but it may be faster.

score 1 · Answer 4 · answered Jul 02 '15 at 07:11

check the following code which returns the max count of duplicates

 public static void main(String args[]) {
    int[] inputArray = { 4, 4, 10, 4, 10 };
    Map<Integer, Integer> hMap = new HashMap<Integer, Integer>();
    HashSet<Integer> hSet = new HashSet<Integer>();
    for (int i : inputArray) {
        if (hSet.add(i)) {
            hMap.put(i, 1);
        } else {
            hMap.put(i, hMap.get(i) + 1);
        }
    }
    Iterator<Integer> iter = hMap.values().iterator();
    int temp = 0;
    while (iter.hasNext()) {
        int max = iter.next();
        if (max > temp) {
            temp = max;
        }
    }
    System.out.println(temp);
}

score 1 · Answer 5 · answered Aug 01 '19 at 04:50

String[] Csssplit = Css.split("====");
        HashMap<String,Integer> Spancsslist = new HashMap<String,Integer>();
        for(int c=0;c<Csssplit.length;c++){
            Css = Csssplit[c];
            //System.out.println("css::"+Css);
            int count = Spancsslist.getOrDefault(Css, 0);
            Spancsslist.put(Css,count+1);    
        }
        if(Spancsslist.size()==0){ continue; }

        Spancsslist = Spancsslist.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue())).collect(toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e2,LinkedHashMap::new));
        Css = Spancsslist.keySet().stream().findFirst().get();

score 0 · Answer 6 · answered Aug 20 '18 at 08:03

using Integer.MIN_VALUE to find max array, then count duplicate max int array.

public static int main(int[] ar) {
        int count = 0;
        int max = Integer.MIN_VALUE;
        int lastMax = 0;

        for(int i = 0; i < ar.length; i++) {
           if(ar[i] > max) {
            max = ar[i];
            if(lastMax != max){
              count = 0;
            }
            lastMax = max;
           } 

          if(ar[i] == max) {
          count += 1;
          }
        }
           return count;
    }

The question asks the maximum number of duplicates within an array. Your answer is about the number of duplicates of the max element. — hkchengrex, Aug 20 '18 at 08:14

Java - Find maximum number of duplicates within an array

6 Answers6