Most popular element with count in Array with Java
(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&lt;Integer&gt; inputList) {
L1: Collections.sort(inputList); // Θ(n log n) hopefully
L2: Set&lt;RepeatedEntry&gt; resultSet = new TreeSet&lt;&gt;(); // Θ(1)
L3: for (int i = 0; i &lt; 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 &lt; inputList.size(); end++ ) { // Θ(n)
  if ( !inputList.get(end).equals(inputList.get(start)) ) { // Θ(1)
    if ( end - start &gt; maxLength ) { // Θ(1)
      maxItem = inputList.get(start); // Θ(1)
      maxLength = end - start; // Θ(1)
    }
    start = end; // Θ(1)
  }
}
// case: maxItem is top/last element
if ( end - start &gt; 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&lt;E, Integer&gt; frequency = new HashMap&lt;&gt;();
E maxItem = null;
int maxLength = 0;

for ( E item : inputList ) { // Θ(n)
  int count = frequency.merge(item, 1, Integer::sum); // Θ(1) [!]
  if ( count &gt; 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.