Most popular element with count in Array with Java

Question

Here is the input array of int values

Example: { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 }

Find the most repeated element with its count, example output; 5 - repeated 3 times

Here is my code after some improvisations to improve the complexity from O(n)

class RepeatedEntry implements Comparable<RepeatedEntry> {
    private int number;
    private int count;

    public void setNumber(int number) {
        this.number = number;
    }

    public void setCount(int count) {
        this.count = count;
    }

    public int getNumber() {
        return number;
    }

    public int getCount() {
        return count;
    }

    @Override
    public int compareTo(RepeatedEntry obj) {
        return obj.count - this.count;
    }
}

public class MaxCountOfDuplicate {

    public static RepeatedEntry findMostPopularItem(List<Integer> inputList) {
        Collections.sort(inputList);
        Set<RepeatedEntry> resultSet = new TreeSet<>();
        for (int i = 0; i < inputList.size(); i++) {
            int thisEle = inputList.get(i);
            int lastIndexOfThisEle = inputList.lastIndexOf(thisEle);
            int repeatedCount = (lastIndexOfThisEle - i) + 1;
            if (repeatedCount != 1) {
                RepeatedEntry repeatedEntry = new RepeatedEntry();
                repeatedEntry.setNumber(thisEle);
                repeatedEntry.setCount(repeatedCount);
                resultSet.add(repeatedEntry);
            }
        }
        return resultSet.iterator().next();
    }

    /* Given an input array find the duplicate element with max count. */
    public static void main(String[] args) {

        Integer[] x = { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 }; // input array
        RepeatedEntry finalResult = findMostPopularItem(Arrays.asList(x));

        System.out.println("Most repeated element and its count is -> \n");
        System.out.println(finalResult.getNumber() + " - repeated "
                + finalResult.getCount() + " times");

    }
}

Here are my relevant questions to this

I am sure the time complexity is not O(n) and O(n^2) In this case, how do I calculate time complexity and what is it in this case? And coming to space complexity, creating RepeatedEntry objects in a loop, is it a performance issue?

I have assumed the input array to be Integer wrapper, if it was strictly int primitive, the conversions and complexity's would increase I guess. I thought of storing the result in HashMap but avoided as it needs further processing to fetch the output, any answer using HashMap improving complexity would help me learn too and best possible solutions as well.

Answer 1

(Useful: What is the difference between O, Ω, and Θ?)

How do I calculate time complexity and what is it in this case?

Algorithmic time complexity, as we commonly understand it, is a measure of how an algorithm scales in terms of its input. We're usually interested in asymptotic complexity, meaning we want to see how it performs in the generalized, large-scale cases. It is the answer to the question: "What if we make it bigger?"

How you calculate is fairly straightforward: you figure out the number of steps your algorithm needs compared to your input size, and you crib out the scalars:

Θ(4n² + 25n + 842) = Θ(n²) ; Θ(28n * 6 log (18n)) = Θ(n log n)

... with the understanding that, as n approaches very large numbers, all scalars become insignificant. (This isn't entirely accurate, but it's good enough for envelope-and-fingers calculations.)

Here is a line-per-line of your code:

// annotated with time complexity, with n = inputList.size()
public static RepeatedEntry findMostPopularItem(List<Integer> inputList) {
L1: Collections.sort(inputList); // Θ(n log n) hopefully
L2: Set<RepeatedEntry> resultSet = new TreeSet<>(); // Θ(1)
L3: for (int i = 0; i < inputList.size(); i++) { // Θ(n)
L4:     int thisEle = inputList.get(i); // Θ(1)
L5:     int lastIndexOfThisEle = inputList.lastIndexOf(thisEle); // Θ(n)
L6:     int repeatedCount = (lastIndexOfThisEle - i) + 1; // Θ(1)
L7:     if (repeatedCount != 1) { // Θ(1)
L8:         RepeatedEntry repeatedEntry = new RepeatedEntry(); // Θ(1)
L9:         repeatedEntry.setNumber(thisEle); // Θ(1)
L10:        repeatedEntry.setCount(repeatedCount); // Θ(1)
L11:        resultSet.add(repeatedEntry); // Θ(log n)
L12:    }
L13:}
L14:return resultSet.iterator().next(); // Θ(log n)
}

L3 * L5 gives you an algorithmic time complexity approached by Θ(n²) (consider the case where no numbers are repeated).

If the input is already sorted, you can find the top in a Θ(n) fashion:

E maxItem = null;
int maxLength = 0;

int start, end;
for ( start = 0, end = 1; end < inputList.size(); end++ ) { // Θ(n)
  if ( !inputList.get(end).equals(inputList.get(start)) ) { // Θ(1)
    if ( end - start > maxLength ) { // Θ(1)
      maxItem = inputList.get(start); // Θ(1)
      maxLength = end - start; // Θ(1)
    }
    start = end; // Θ(1)
  }
}
// case: maxItem is top/last element
if ( end - start > maxLength ) { // Θ(1)
  maxItem = inputList.get(start); // Θ(1)
  maxLength = end - start; // Θ(1)
}
return new RepeatedEntry(maxItem, maxLength); // Θ(1)

... but sorting itself is a Θ(n log n) operation in the ideal case.

I thought of storing the result in HashMap but avoided as it needs further processing to fetch the output, any answer using HashMap improving complexity would help me learn too and best possible solutions as well.

Map<E, Integer> frequency = new HashMap<>();
E maxItem = null;
int maxLength = 0;

for ( E item : inputList ) { // Θ(n)
  int count = frequency.merge(item, 1, Integer::sum); // Θ(1) [!]
  if ( count > maxLength ) { // Θ(1)
    maxItem = item; // Θ(1)
    maxLength = count; // Θ(1)
  }
}
return new RepeatedEntry(maxItem, maxLength); // Θ(1)

The exclamation mark at Map.merge is because, while HashMap provides access in asymptotically constant time, the actual constant time may be significant, and it depends on practical factors like load factor, bucket sizes, and hash spread.

Answer 2

• Complexity is \$O(n^2)\$, because lastIndexOf is linear. Using lasIndexOf(thisEle) fails to take advantage of the fact that the array is sorted. You should use a two-argument version lastIndexOf(thisEle, i).

  Also, the code does many unnecessary calls to lastIndexOf. Instead of i++ you should set i to lastIndexOf() + 1.

• Set is very suspicious. You only need a single instance of RepeatedEntry:

  RepeatedEntry entry = new RepeatedEntry(0, 0);
  ....
      if (repeatedCount > entry.count) {
          entry.count = repeatedCount;
          entry.number = thisEle;
      }
      ....
  return entry;