Start learning free

LESSON 168 OF 338 · FREE CODING INTERVIEW QUESTIONS

Max Value and Number of Occurrences in Go: 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

    GO · FREE CODING INTERVIEW QUESTIONS

    Max Val And Number Of Occurrences in Go, explained

    Problem overview

    The function maxValNumOfOccurrences receives a slice of integers, nums, and returns a two-element slice: the largest value, followed by how many times that value appears.

    For nums = [2, 7, 11, 8, 11, 8, 3, 11] the largest value is 11, and it appears three times, so the result is [11, 3]. The statement asks for O(n) time and O(1) extra space, and the follow-up asks for a single pass over the slice.

    Approach

    The simple route uses two loops. The first finds the maximum, the way you would find the smallest of three numbers: keep a variable with the best value so far and replace it whenever something larger shows up. The second loop counts the elements equal to that maximum. Both loops are O(n), so this already meets the time budget, but it reads the data twice.

    The one-pass version keeps the count up to date while the maximum is still being searched. Two things can happen for each element val:

    • val is larger than maxVal. A new maximum has appeared, so maxVal becomes val, and the count restarts at 1 because every earlier occurrence belonged to a smaller value.
    • val equals maxVal. It's one more occurrence of the current maximum, so the count goes up by one.

    Anything smaller than maxVal changes nothing. Tracing [2, 7, 11, 8, 11]:

    val=2  maxVal=2  count=1
val=7  maxVal=7  count=1
val=11 maxVal=11 count=1
val=8  maxVal=11 count=1
val=11 maxVal=11 count=2

    Step by step

    1. Declare maxVal and count together with one :=. maxVal starts as nums[0], a real element, and count starts at 0.
    2. Loop over the slice with range, naming the element val and discarding the index with _.
    3. Check for a new maximum: val > maxVal. The comparison is strict, since an equal value isn't a new maximum, only another occurrence.
    4. Handle it: set maxVal to val and count to 1.
    5. Add the else if branch for val == maxVal, and increment count with ++.
    6. Return a slice literal of type []int with maxVal and count, in that order.

    Starting count at 0 is deliberate. The loop visits nums[0] too. It equals maxVal, so the else if branch counts it, and the count is already 1 when the second element arrives.

    The solution in Go

    func maxValNumOfOccurrences(nums []int) []int {
    maxVal, count := nums[0], 0
    for _, val := range nums {
        if val > maxVal {
            maxVal = val
            count = 1
        } else if val == maxVal {
            count++
        }
    }
    return []int{maxVal, count}
}

    The Go details worth a closer look:

    • Multiple declaration. In maxVal, count := nums[0], 0, the values on the right are assigned to the names on the left in order. Both variables are new, so := is allowed.
    • range yields an index and a value. For a slice, for i, val := range nums gives the position and a copy of the element. Go rejects unused variables, so an index you don't need goes into the blank identifier _.
    • else if stays on the closing brace's line. Write } else if val == maxVal {. A newline between } and else is a syntax error, because Go inserts a semicolon at the end of that line.
    • count++ is a statement. It can't be used inside an expression, and there's no prefix ++count in Go.
    • Returning two values. The lesson returns one slice, []int{maxVal, count}. Go functions can also return several values directly, but the tests expect a slice here.

    Complexity

    Time: O(n). The loop touches each element once and does a constant amount of work for each. Space: O(1). Besides the returned two-element slice, the function uses two integers, maxVal and count.

    Edge cases and common mistakes

    • All values negative. For [-4, -9, -4] the result is [-4, 2]. Starting maxVal at 0 would return 0 with a count of 0, which is not in the slice.
    • A single element. [5] gives [5, 1]: the first iteration finds val == maxVal and counts it.
    • Not resetting the count. If a new maximum doesn't set count = 1, occurrences of smaller values leak into the answer. For [3, 3, 5] the result must be [5, 1].
    • Using >= in the first check. Then an equal value would reset the count to 1 instead of increasing it, and [2, 2] would give [2, 1].
    • An empty slice. The solution reads nums[0], so an empty slice stops the program with an "index out of range" panic. The lesson's inputs always have at least one element; a real caller would check len(nums) first.

    Testing

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