Start learning free

LESSON 187 OF 414 · FREE CODING INTERVIEW QUESTIONS

Max Value and Number of Occurrences in Scala: One Pass, O(n)

Practice O(n) Read the full explanation

Given an array of integers, return the maximum value and its number of occurrences.

Example:

Input: nums = [2, 7, 11, 8, 11, 8, 3, 11]
Output: [11, 3]
Explanation: The maximum value is 11 and it appears 3 times

Note:

Your algorithm should run in O(n) time and use O(1) space.


Follow up:

Could you do this in one pass (e.g. looping over the array only once)?




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


STEP 1 OF 6
    Ctrl + Enter to check

    SCALA · FREE CODING INTERVIEW QUESTIONS

    Max Val And Number Of Occurrences in Scala, explained

    Problem overview

    The method maxValNumOfOccurrences receives an Array[Int] called nums and returns an Array[Int] with two entries: the largest value in nums, and how many times that value appears.

    For nums = Array(2, 7, 11, 8, 11, 8, 3, 11) the largest value is 11, and it appears three times, so the answer is [11, 3]. The statement asks for O(n) time and O(1) extra space, and the follow-up asks whether one pass over the array is enough.

    Approach: a running maximum with a running count

    Finding only the maximum is a familiar pattern: keep the largest value seen so far and replace it whenever something bigger shows up. Counting how often the maximum occurs could be a second loop after the first one, which is still O(n). But both facts can be maintained together in a single loop.

    For each element value, exactly one of three things is true:

    • value is greater than the current maximum. The previous maximum, and every occurrence counted for it, no longer matters. The new maximum has been seen once, so the count resets to 1.
    • value equals the current maximum. This is one more occurrence, so the count goes up by 1.
    • value is smaller. Nothing changes.

    When the loop ends, the pair (maximum, count) describes the whole array.

    Tracing the example

    On Array(2, 7, 11, 8, 11, 8, 3, 11) the state starts as maxVal = 2, count = 0. The first element, 2, equals the maximum, so the count becomes 1. Then 7 and 11 are each larger, so the maximum becomes 7 and then 11, with the count reset to 1 both times. The 8 is smaller and changes nothing. The next 11 raises the count to 2, the 8 and the 3 change nothing, and the last 11 raises the count to 3. The method returns [11, 3].

    The two-pass version, which finds the maximum first and counts it in a second loop, gives the same answer with twice the work. The single pass is what the follow-up asks for.

    Step by step

    1. Declare two vars: maxVal set to nums(0) and count set to 0. The maximum starts as a real element of the array, which keeps the result right even when every number is negative. The count starts at 0, not 1, because the loop will visit the first element again and count it then; with 1 the first element would be counted twice. Scala indexes arrays with parentheses, not square brackets.
    2. Loop over the array with for (value <- nums). The arrow reads "for each value in nums".
    3. Test value > maxVal inside the loop. It must be strict: an equal value is another occurrence, not a new maximum.
    4. In that branch, set maxVal = value and count = 1. This discards the occurrences of the old, smaller maximum.
    5. Add else if (value == maxVal) after the closing brace of the first branch, and increment with count += 1. Scala has no ++ operator.
    6. After the loop, return Array(maxVal, count), in that order. Array(a, b) builds an array from its arguments, and the element type Int is inferred.

    The solution in Scala

    class Solution {
    def maxValNumOfOccurrences(nums: Array[Int]): Array[Int] = {
        var maxVal = nums(0)
        var count = 0
        for (value <- nums) {
            if (value > maxVal) {
                maxVal = value
                count = 1
            } else if (value == maxVal) {
                count += 1
            }
        }
        return Array(maxVal, count)
    }
}

    The Scala details worth a closer look:

    • var versus val. Both variables change during the loop, so they must be var. The loop variable value is a fresh val on every iteration.
    • The array is not modified. The loop only reads nums. The returned array is a new one with two elements.
    • Printing an array. println(Array(11, 3)) doesn't show the elements; it prints a type tag and a hash code, something like [I@b684286. To see the contents, use mkString: Array(11, 3).mkString("[", ", ", "]") gives [11, 3].
    • Explicit return. Leaving it off, so the last line is just Array(maxVal, count), is the more usual Scala style and means the same thing.
    • The type is Int. The values are 32-bit integers, and nothing in this method adds or multiplies them, so there is no overflow to worry about. The count can't exceed the array's length.

    Complexity

    Time: O(n). The loop visits each element once and does a constant amount of work for it.

    Space: O(1). Besides the two-element result, the method keeps two integers, no matter how long nums is.

    Edge cases and common mistakes

    • All negative numbers. For Array(-5, -2, -9, -2) the result is [-2, 2]. Starting maxVal at 0 would wrongly report 0 with a count of 0.
    • One element. Array(4) gives [4, 1]: the first element is compared with itself, equals the maximum, and is counted once.
    • All elements equal. Array(3, 3, 3) gives [3, 3].
    • Maximum at the end. Array(1, 2, 3) gives [3, 1]. The count is reset to 1 when 3 arrives, which is why the earlier counts don't leak into the answer.
    • Empty array. nums(0) throws an ArrayIndexOutOfBoundsException ("Index 0 out of bounds for length 0"). The problem implies at least one element; if empty input were possible, the method would need to check nums.isEmpty first.
    • Forgetting the reset. If the count = 1 line is missing, a new maximum inherits the old count.
    • Using >= in the first test. Then equal values would also go through the reset branch and the count would never exceed 1.

    Testing

    • Array(2, 7, 11, 8, 11, 8, 3, 11) gives [11, 3].
    • Array(-5, -2, -9, -2) gives [-2, 2].
    • Array(4) gives [4, 1].
    • Array(3, 3, 3) gives [3, 3].
    • Array(1, 2, 3) gives [3, 1].
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free