Start learning free

LESSON 168 OF 348 · FREE CODING INTERVIEW QUESTIONS

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

Practice O(n) Read the full explanation

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

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 < minVal:
	minVal = B
if C < 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 = nums[0]
for val in nums:
	if val > maxVal:
		maxVal= val
return maxVal
Now how can we get the number of occurences of this value in nums?

One idea would be that after we found maxVal to traverse the array again and count the occurences in another variable count: 
maxVal = nums[0]
for val in nums:
	if val > maxVal:
		maxVal = val

count = 0
for val in nums:
	if val == maxVal:
		count += 1
	
return [maxVal, 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 occurence ever of this value.
  • val == maxVal => We found a new occurence of the current solution, so we should increment count.
This is how the code would look like: 
maxVal, count = nums[0], 0

for val in nums:
	if val > maxVal:
		maxVal = val
		count = 1
	else if val == maxVal:
		count += 1
		
return [maxVal, count]


STEP 1 OF 6
    Ctrl + Enter to check

    KOTLIN · FREE CODING INTERVIEW QUESTIONS

    Max Val And Number Of Occurrences in Kotlin, explained

    Problem overview

    The function maxValNumOfOccurrences receives an IntArray named nums and returns another IntArray with two numbers: the largest value in nums, and how many times that value appears. The statement asks for O(n) time and O(1) extra space, and the follow-up asks whether one loop over the array is enough.

    For nums = [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, and it appears three times, so the result is [11, 3]. The 8 appears twice, but only the count of the maximum matters.

    Approach: track the maximum and its count together

    The easy version of this problem is to find only the maximum: keep a variable with the largest value seen so far and replace it whenever a bigger value turns up. Counting the occurrences can then be a second loop that counts the elements equal to the maximum. That is correct and runs in O(n), but it reads the array twice.

    One pass is enough if you update both numbers in the same loop. For each value, exactly one of three things is true:

    • It is bigger than the current maximum. A new maximum has appeared, and it has been seen once so far, so the count restarts at 1. The old count belonged to a smaller value and is thrown away.
    • It equals the current maximum. This is another occurrence, so the count grows by 1.
    • It is smaller. It affects neither number.

    Here is the idea on [3, 5, 5, 2, 9, 9, 9]. The maximum starts at 3 with a count of 0, and the first element is then visited by the loop. The 3 equals the maximum, so the count is 1. The 5 is bigger: the maximum is 5 and the count is 1. The next 5 raises the count to 2. The 2 changes nothing. The first 9 resets the count to 1, and the next two raise it to 3. The result is [9, 3].

    Step by step

    1. Declare maxVal and count with var. maxVal starts as nums[0], which is a real element of the array, and count starts at 0. Both need var because the loop reassigns them.
    2. Loop over the values. for (value in nums) visits each element in order. Kotlin infers that value is an Int.
    3. Test for a new maximum with value > maxVal. The comparison is strict, because an equal value is a repeat and not a new maximum.
    4. Inside that branch, set maxVal to value and count to 1.
    5. Add else if (value == maxVal) and increment count in it. Smaller values reach neither branch, so nothing happens for them.
    6. After the loop, return intArrayOf(maxVal, count).

    Starting count at 0 may look odd, since the first element is already in maxVal. It works because the loop visits nums[0] too, and at that moment value == maxVal, so that visit adds the 1.

    The solution in Kotlin

    class Solution {
    fun maxValNumOfOccurrences(nums: IntArray): IntArray {
        var maxVal = nums[0]
        var count = 0
        for (value in nums) {
            if (value > maxVal) {
                maxVal = value
                count = 1
            } else if (value == maxVal) {
                count++
            }
        }
        return intArrayOf(maxVal, count)
    }
}

    The Kotlin details worth knowing:

    • IntArray is not Array<Int> or List<Int>. IntArray compiles to a primitive int[] on the JVM. The function's return type is IntArray, so the result must be built with intArrayOf. arrayOf(maxVal, count) gives an Array<Int> and listOf(maxVal, count) gives a List<Int>, and neither is accepted.
    • Printing an array. println(result) on an IntArray doesn't show the elements. It prints a type-and-hash text such as [I@6ea6d14e. To see the contents, use result.toList(), which prints [11, 3], or result.joinToString().
    • for (value in nums). This form gives you the elements themselves, not their indices. Use nums.indices when the position matters.
    • count++. It is a statement here, used for its effect on count. In Kotlin, count += 1 does the same thing.

    Complexity

    Time: O(n). The loop visits each element once and does a constant amount of work per element. The two-pass version is also O(n), just with about twice as many comparisons.

    Space: O(1). Two integers, maxVal and count, are the only extra memory. The two-element result array has a fixed size, whatever the length of nums.

    Edge cases and common mistakes

    • All values negative. [-3, -1, -1, -7] gives [-1, 2]. Starting maxVal at nums[0] avoids the trap of starting at 0, which would report a maximum that isn't in the array.
    • One element. [5] gives [5, 1].
    • All elements equal. [4, 4, 4] gives [4, 3].
    • An empty array. nums[0] throws an ArrayIndexOutOfBoundsException with the message Index 0 out of bounds for length 0. The code assumes the array has at least one element.
    • Forgetting to reset the count. If a new maximum doesn't set count to 1, the count keeps occurrences of smaller values. For [3, 3, 9], the result would be [9, 2] instead of [9, 1].
    • Using >= in the first test. Equal values would then reset the count to 1 every time, and the result for [4, 4, 4] would be [4, 1].
    • Starting count at 1. The first element would be counted twice, once in the declaration and once by the loop. For [4, 4, 4] the result would be [4, 4].

    Testing

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