Finding the most frequent String in a sorted ArrayList without using HashMap

Question

Considering an ArrayList of String's containing

animalsArray[dog, cat, dog, dog, cat, duck, duck, dog]

I could easily use HashMap's to find the most common String, using the HashMap value as a counter, and the key to store the animal name.

If the ArrayList was sorted

[dog, dog, dog, dog, cat, cat, duck, duck]

What is the easiest way to find the most common element without using Hashmaps? I was thinking about using a for loop comparing animalArray.get(i) with animalArray.get(i-1) but I wasn't able to develop this solution. And what are the advantages, if there are any, of having a sorted ArrayList when we need we need to find the most common element?

GBlodgett · Accepted Answer · 2018-12-09 18:38:38Z

4

What is the easiest way to find the most common element without using Hashmaps?

I would consider (Java 8+) this to be quite easy:

String str = list.stream()
                 .distinct()
                 .max(Comparator.comparing(e -> Collections.frequency(list, e)))
                 .get();

Which will create a Stream of the List, and find the element with the most frequency in the List.

And what are the advantages, if there are any, of having a sorted ArrayList when we need we need to find the most common element?

Imagine an unsorted List:

[dog, cat, turtle, cat, dog, snake]

For every element, you will have to search the rest of the List to see how many times it occurs.

However with a sorted List:

[dog, dog, cat, cat, snake, turtle]

You only have to have a counter to keep track of the longest sublist that contains the same elements. Then it turns into something like (psuedocode):

//T being the type of the List
T element
int count = 0;
int biggestCount = 0;
for(every element in the list) {
   if the item is the same as previous
      count++
   else 
      //Only check when we're about to change elements
      if count > biggestCount
          biggestCount = count
          element = current element of List
      //Starting over with a new element
      count = 1
}
return element

edited Dec 9, 2018 at 18:38

answered Dec 8, 2018 at 22:11

GBlodgett

12.8k4 gold badges33 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jaymartines Over a year ago

Thank you so much for your solution! if i got your loop right, at the end of the loop you would return the highest number, which is amazing, but not the name of the animal associated to it. Also, tell me if I am wrong, counting using hashmaps would result in time complexity O(n), while sorting using Collection.sort is O(n log n) + the for loop to find the highest which should be O(n) so in the end O(n log n) + O(n)?

GBlodgett Over a year ago

@jaymartines Yes the loop I showed was just to illustrate that finding the greatest element in the sorted was much easier than an unsorted. And yes using a HashMap allows for only one iteration over the loop so it has the better time complexity, assuming the List is unsorted.

Collectives™ on Stack Overflow

Finding the most frequent String in a sorted ArrayList without using HashMap

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related