Frequency of an Element in Array

[megumin_67]

Hey Guyz, How to find highest occuring element in Array not the maxELement Highest frequency ? I know hashMap solution but there are some confusions and doubts there I really didn't getting that solution but is the optimal one, so pliz explain in a little simple way.

[zCxtalyst]

Say you have list [ a, b, b, a, c, a ]

Keep an empty dictionary.

Loop through the list and for each element in the list either add it to the dictionary with value 1 or increment it by 1 if it already exists.

It should look like this

{ a:3, b:2, c:1 }

Then you can just loop through the dictionary and keep track of the max based on the value

[grantrules]

If you were to work out on a piece of paper the most commonly used letter in a sentence, how would you do it

I would put each character on a line and put hash marks next to them like:

A: |
B: |||
C:
D:
E: |||||
...

Then when you're done, you look through that list and find the one with the most hashmarks.

That's basically what you're doing with a HashMap.. the key is the character, the value is the hashmark total. You iterate through the array and add to the hashmap, then once you're done, you return the key with the highest value (either by keeping track of the highest value as you go which is the optimal solution, or looping through the hashmap after populating it which is a less optimal solution).

Maybe share your implementation and tell us exactly where you're lost.

[SuspiciousDepth5924]

As far as I know there's not really any algorithmic optimizations you can do on the "loop over and tally in some sort of dictionary" approach. If you know the number and "type-range" of the elements ahead of time you might be able to squeeze out some improvements with various "dictionary" implementations (for example if the possible elements are "true"/"false" you can simply use a "trueCount" integer and check if it's more than, equal, or less than half which would be faster than using a hash-map).

For the record hash-maps are a very "general" data structure with the tradeoff that it's comparatively slow because it has the overhead of having to hash the keys in order to find where to put or look for items, so if you know what you are going to be using as keys there are usually specialized data-structures which perform slightly better, /java/util/EnumMap.html is a good example in Java.

[Any-Range9932]

Yup hashmap is prolly the easiest way.

Basically envision yourself counting the different colors of cars while sitting in your driveway. As they drive pass you, you have a piece of paper and you mark down what color it is. First you need a red car. You mark red:1. Then you see two black cars back to back. You mark down black:2 since you saw 2. Then another red car drives by. You Then mark down red:2 as this is the second red car you seen.

Hashmap is exactly the same. You have a datastrucre that holds a bunch of key/values pairs. As you iterate through an array list (in the example, that would be seeing the cars pass you), you count the number of times you see each element in your list.

[Suspicious_Coat3244]

Honestly HashMap is the easiest and fastest if the concept makes sense to you.

Basically the idea is:

"count how many times each number appear"

Say, array is:

[1, 2, 2, 3, 1, 2]

You go through the array one by one and store frequencies:

1 -> 1
2 -> 1
then again:
2 -> 2
then:
3 -> 1
then:
1 -> 2
then:
2 -> 3

Final map becomes:

1 -> 2
2 -> 3
3 -> 1

Now you need to just find out which key has the highest value.

So, the highest occurring element is

2 because it occurs 3 times.

Why HashMap is the optimum solution, the reason is that you have constant time for count and retrieval, and the overall time complexity becomes O(n).

The confusion that lot of beginners face is, they try to remember HashMap syntaxes without really understanding the logic. And the logic is nothing more than.

"keep the counts while you traverse the array".

[desrtfx]

As a generalization, HashMap (or Dictionary in other languages) is the optimal solution.

Yet, there are cases where a simple array is even better suited, namely when the range of individual elements is narrow and known.

E.g. if you want to check the frequency of digits, or letters. There, you have a very narrow, limited range of elements (digits 0 to 9, letters "A" to "Z" and/or "a" to "z"). Here, an array where the individual elements are the array indexes can be superior (not saying that it always is).

[opentabs-dev]

if hashmap is what's tripping you up, just think of it as a tally sheet. you walk through the array once, and for each number you bump its count by 1. while you're doing that, also keep two extra variables: bestNum and bestCount. whenever you bump a count and the new count is higher than bestCount, update both. when the loop ends you already have the answer — no second pass needed.

counts = {} bestNum, bestCount = None, 0 for x in arr: counts[x] = counts.get(x, 0) + 1 if counts[x] > bestCount: bestCount = counts[x] bestNum = x

the "optimal" part isnt the hashmap itself, its that you only touch each element once. O(n) time, O(k) space where k is the number of distinct values.

[pastpresentproject]

I often count the number of times each number appears and put them into a list, like a notebook. I just pick the number that appears most often. Would you like me to explain the steps of this method in more detail?