Start learning free

LESSON 168 OF 348 · FREE CODING INTERVIEW QUESTIONS

Max Value and Its Occurrences in TypeScript: 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

    TYPESCRIPT · FREE CODING INTERVIEW QUESTIONS

    Max Val And Number Of Occurrences in TypeScript, explained

    Problem overview

    The method maxValNumOfOccurrences receives an array of numbers, nums, and returns a two-element array: the largest value, then the number of times it 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 whether it can be done in a single pass over the array. This lesson does exactly that.

    Approach: update the maximum and the count together

    An easier version of the problem is finding only the maximum. Keep a variable maxVal with the largest value seen so far, and replace it whenever a bigger value shows up.

    The count can be found with a second loop after the maximum is known: go over the array again and count the elements equal to maxVal. That is correct and still O(n), but it reads the array twice.

    To do it in one pass, update the count while the maximum is changing. For each element val, one of three things is true:

    • val is greater than maxVal. A new maximum was found. Store it and reset the count to 1, because this is its first occurrence. Occurrences of the old, smaller maximum no longer matter.
    • val equals maxVal. Another occurrence of the current maximum. Add 1 to the count.
    • val is smaller. Ignore it.

    Trace [2, 7, 11, 8, 11, 8, 3, 11]. After the first element, maxVal is 2 and count is 1. The 7 raises maxVal to 7 and resets count to 1. The 11 does the same. The 8 is smaller and is ignored. The second 11 raises count to 2. The 8 and the 3 are ignored. The last 11 raises count to 3. The result is [11, 3].

    Both versions have the same complexity, so the one-pass version is not faster in the Big O sense. Its advantage is that it works on data you can only read once, such as values arriving one at a time, and that the whole logic lives in one place. The price is that you must keep the maximum and the count consistent with each other at every step, which is exactly what the three cases above do.

    Step by step

    1. Declare maxVal and count with a single let. Set maxVal to nums[0] and count to 0. Starting the maximum at the first element, rather than at 0, keeps the answer right when every number is negative. The count starts at 0 because the loop visits the first element too and counts it then: it equals maxVal.
    2. Loop over the values with for...of. The loop variable is val. for...of gives you the elements. for...in would give you the indexes, as strings.
    3. Check whether val is greater than maxVal. Use a strict comparison: an equal value is another occurrence, not a new maximum.
    4. Inside it, set maxVal to val and count to 1.
    5. Add an else if checking whether val equals maxVal. If so, increment count with ++. Smaller values fall through both branches and change nothing.
    6. Return [maxVal, count] after the loop, with the maximum first.

    The solution in TypeScript

    class Solution {
    maxValNumOfOccurrences(nums: number[]): number[] {
        let maxVal = nums[0], count = 0;
        for (let val of nums) {
            if (val > maxVal) {
                maxVal = val;
                count = 1;
            } else if (val == maxVal) {
                count++;
            }
        }
        return [maxVal, count];
    }
}

    TypeScript details worth a look:

    • Inferred types. In let maxVal = nums[0], count = 0; both variables are inferred as number. No annotation is needed, and one let can declare several variables.
    • == versus ===. Here both sides are numbers, so == behaves like ===. Many codebases prefer === as a habit, because == converts types when they differ.
    • The return type. number[] is a plain array. The method always returns exactly two elements, but the type does not enforce that.
    • Annotations are erased. The compiled JavaScript contains no types, so the compiler cannot protect you from an array that is empty at run time.

    Complexity

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

    Space: O(1). Only maxVal, count and the loop variable are stored, however long the array is. The returned two-element array has a fixed size.

    Edge cases and common mistakes

    • All values negative. For [-5, -2, -9, -2] the result is [-2, 2]. Starting maxVal at 0 would wrongly report 0.
    • A single element. For [4] the result is [4, 1], because the first element counts as an occurrence.
    • Not resetting the count. If you forget count = 1 when a new maximum appears, occurrences of smaller old maximums leak into the result.
    • Using >= in the first check. An equal value would then reset the count to 1 instead of adding one, so [11, 11] would give [11, 1].
    • Starting count at 1. The first element would be counted twice, since it equals maxVal when the loop reaches it.
    • An empty array. nums[0] is then undefined, and the method returns [undefined, 0] without any error. The lesson's input is non-empty, but a real program would check nums.length first.

    Testing

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