Max Val and Number of Occurrences

Let's start by thinking about an easier version of the problem. Suppose we only want to return the maximum value in the array and we don't care how many times it occurs. Have we solved a similar easier problem in the past? Can we adapt that solution here?

That similar problem is "Minimum Value Of Three". There we tried out each of the three numbers and used a variable minVal to store the smallest one found so far throught the algorithm:

minVal = A
if B is less than minVal: minVal = B
if C is less than minVal: minVal = C
return minVal

How can we adapt this approach for an array of numbers instead of just three?

The principle is the same. We will iterate through each value in the array nums and update the maximum accordingly. The variable is now maxVal and stores the greatest element found so far:

maxVal = the first element of nums
for each val in nums:
    if val is greater than maxVal: maxVal = val
return maxVal

Now how can we get the number of occurrences of this value in nums?

One idea would be that after we found maxVal to traverse the array again and count the occurrences in another variable count:

maxVal = the first element of nums
for each val in nums:
    if val is greater than maxVal: maxVal = val

count = 0
for each val in nums:
    if val is equal to maxVal: count = count + 1

return maxVal and count

This is good, but the follow up asks us to solve the question in one pass. We can also compute count in the same for loop where we compute maxVal. Take a small example and try to figure out how to update both maxVal and count for each val when necessary.

For each element val of nums, there are two scenarios that are important:

• val > maxVal => We found a new maximum value, so we should update maxVal to val and reset count to 1 as this is the first occurrence ever of this value.
• val equals maxVal => We found a new occurrence of the current solution, so we should increment count.

This is how the code would look like:

maxVal = the first element of nums, count = 0

for each val in nums:
    if val is greater than maxVal:
        maxVal = val
        count = 1
    otherwise, if val is equal to maxVal:
        count = count + 1

return maxVal and count