Start learning free

LESSON 190 OF 414 · FREE CODING INTERVIEW QUESTIONS

Max Value and Its Occurrences in Rust: O(n) in One Pass

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

    RUST · FREE CODING INTERVIEW QUESTIONS

    Max Val And Number Of Occurrences in Rust, explained

    Problem overview

    The function max_val_num_of_occurrences takes a vector of integers, nums, and returns a vector of two numbers: the largest value in nums, then the number of 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 answer is [11, 3]. Note that 8 also appears twice, but only the maximum counts.

    The statement asks for O(n) time and O(1) extra space, and the follow-up asks whether the array can be read only once.

    Approach: track the maximum and its count together

    The simple plan uses two loops over the vector. The first finds the maximum, the second counts how many elements equal it. That is already O(n), since two passes cost 2n steps, which is still linear. The one-pass version does both jobs at once by updating two variables, max_val and count, as each element arrives. For every element value there are three cases:

    • value > max_val: a new maximum. Store it and reset count to 1, because the old count described a smaller value.
    • value == max_val: one more copy of the current maximum, so add 1 to count.
    • value < max_val: it can't matter, so do nothing.

    Here is the trace for [2, 7, 11, 8, 11]. max_val starts at 2 with count 0. The first element, 2, equals max_val, so count becomes 1. Then 7 is larger: max_val = 7, count = 1. Then 11 is larger: max_val = 11, count = 1. The 8 is ignored, and the second 11 raises count to 2.

    Why does the reset matter? Take [2, 2, 5]. After the two 2s, count is 2, but that is the count of the value 2. Once 5 arrives, the maximum changes, and the old count describes a different number. Setting it back to 1 keeps count always tied to the current max_val. This invariant is the whole idea of the one-pass solution: at every moment, count is the number of times max_val appears among the elements seen so far.

    Step by step

    1. Declare max_val and count with let mut. max_val starts at nums[0], a value that really is in the array, which keeps the answer right when every number is negative. count starts at 0 because the loop visits nums[0] again and counts it through the equal case.
    2. Loop over nums with a variable named value.
    3. Test value > max_val. It must be a strict comparison, because an equal value is another occurrence, not a new maximum.
    4. Update both variables in that branch: max_val becomes value, and count is reset to 1.
    5. Add the else if value == max_val branch and increment count with +=. Rust has no ++ operator.
    6. Return both numbers in a vector built with vec!.

    The solution in Rust

    impl Solution {
    fn max_val_num_of_occurrences(nums: Vec<i32>) -> Vec<i32> {
        let mut max_val = nums[0];
        let mut count = 0;
        for value in nums {
            if value > max_val {
                max_val = value;
                count = 1;
            } else if value == max_val {
                count += 1;
            }
        }
        return vec![max_val, count];
    }
}

    The Rust details worth knowing:

    • The type of count is inferred. Nothing says what type 0 is. The compiler sees that count goes into a Vec alongside the i32 max_val, and chooses i32.
    • for value in nums moves the vector. The loop takes ownership of nums, and the vector can't be used afterwards. Using nums.len() after the loop fails with "borrow of moved value". Here nums[0] is read before the loop, and nothing needs the vector later. To keep it, loop over &nums instead, which makes value a reference of type &i32. The comparisons then need a dereference, as in *value > max_val, because Rust doesn't compare an &i32 with an i32.
    • nums[0] copies an i32. Integers implement Copy, so reading an element leaves the vector intact.
    • No parentheses around conditions, and else if is written on the same line as the closing brace.
    • vec![max_val, count] builds the result vector. Both items must have the same type, which is why count is an i32.

    Complexity

    Time: O(n). The loop visits each element once and does constant work for each: a comparison and at most one or two assignments.

    Space: O(1). The function stores two integers. The result vector always has two entries, no matter how long nums is.

    Edge cases and common mistakes

    • Empty input. nums[0] panics with "index out of bounds: the len is 0 but the index is 0". The lesson's input always has at least one element.
    • All negative numbers. For [-5, -5, -9] the answer is [-5, 2]. Starting max_val at 0 would return 0 with a count of 0.
    • Single element. For [4] the loop sees 4 equal to max_val, so the answer is [4, 1].
    • Forgetting the reset. If count isn't set back to 1 when a new maximum appears, the occurrences of smaller values leak into the answer. For [2, 2, 5] the count of 2 survives and the result is [5, 2] instead of [5, 1].
    • Resetting to 0 instead of 1. The new maximum was just seen, so it already counts once. With 0, [2, 2, 5] would give [5, 0].
    • Starting count at 1. Since the loop also visits nums[0], the first element would be counted twice.

    Testing

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