Start learning free

LESSON 167 OF 347 · FREE CODING INTERVIEW QUESTIONS

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

    C# · FREE CODING INTERVIEW QUESTIONS

    Max Val And Number Of Occurrences in C#, explained

    Problem overview

    The method MaxValNumOfOccurrences takes an int[] named nums and returns a two-element int[]: the largest value in the array, then how many times it appears.

    For nums = [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, and it shows up at three positions, 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 array.

    Approach

    Start with the easier question: what is the maximum? Keep a variable maxVal holding the largest value seen so far, begin with the first element, and replace it whenever a bigger element appears. This is the same idea as picking the smallest of three numbers, applied to a loop.

    The simple way to get the count is a second loop: after maxVal is known, walk the array again and count the elements equal to it. That is two passes, still O(n).

    One pass is possible because the count only depends on what has happened so far. For each element val there are three cases:

    • val is greater than maxVal. A new maximum. Every earlier count belonged to a smaller value, so reset the count to 1.
    • val equals maxVal. Another copy of the current maximum, so add 1 to the count.
    • val is smaller. Ignore it.

    On [2, 7, 11, 8, 11, 8, 3, 11] the pair (maxVal, count) goes (2, 1), (7, 1), (11, 1), then 8 changes nothing, (11, 2), 8 and 3 change nothing, and the last 11 gives (11, 3).

    Step by step

    1. Declare both variables in one statement. maxVal starts at nums[0], so it is always a real element. Starting at 0 would be wrong for an array of negative numbers. count starts at 0, not 1, because the loop will visit the first element too and count it through the "equal" case.
    2. Loop over the values with foreach. The loop needs no index, only each element in turn.
    3. Test for a larger value with a strict >. An equal value is not a new maximum.
    4. Handle the new maximum. Store val in maxVal and set count to 1.
    5. Add an else if for equality. It increments count. Because it is an else if, a value that just replaced the maximum is not counted a second time.
    6. Return both numbers in an array, the maximum first.

    The solution in C#

    class Solution {
    public int[] MaxValNumOfOccurrences(int[] nums) {
        int maxVal = nums[0], count = 0;
        foreach (int val in nums) {
            if (val > maxVal) {
                maxVal = val;
                count = 1;
            } else if (val == maxVal) {
                count++;
            }
        }
        return new int[]{maxVal, count};
    }
}

    The C# details worth noting:

    • Several variables in one declaration. int maxVal = nums[0], count = 0; declares two int variables, each with its own initializer.
    • foreach. It reads each element of the array in order. The loop variable val is read-only, so you can't assign to it inside the loop, which is fine here because the code only reads it.
    • The first element is visited twice. It initializes maxVal and then foreach visits it as well. It is not greater than itself, so it lands in the else if branch and gets counted once. That is why count starts at 0.
    • Returning two values. new int[]{maxVal, count} creates an array of length 2 and fills it in one expression. The array has a fixed length, which suits a pair like this.

    The two-pass version, for comparison

    If you find the single-pass logic hard to trust at first, write the two-pass version and compare results. It separates the two jobs, finding the maximum and counting it:

    int maxVal = nums[0];
foreach (int val in nums) {
    if (val > maxVal) {
        maxVal = val;
    }
}
int count = 0;
foreach (int val in nums) {
    if (val == maxVal) {
        count++;
    }
}
return new int[]{maxVal, count};

    It gives [11, 3] for the example, just like the one-pass solution. Both are O(n), and the one-pass version walks the array only once. The reason it works is the reset: when a bigger value arrives, everything counted so far was counted for a smaller maximum, so the count restarts at 1. After the last element, count describes only the final maxVal.

    Note that the two foreach loops can both declare a variable named val. The variable belongs to its loop, so the second loop's val is a new one, not a redeclaration.

    Complexity

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

    Space: O(1). Two integers, plus the two-element result array, whose size does not depend on n.

    Edge cases and common mistakes

    • All negative numbers. [-4, -4, -9] returns [-4, 2]. It works because maxVal starts from an element, not from 0.
    • One element. [5] returns [5, 1].
    • All elements equal. [3, 3, 3] returns [3, 3].
    • Starting count at 1. The first element would then be counted twice, giving [11, 4] for the example.
    • Forgetting the reset. If count = 1 is missing when a new maximum appears, occurrences of smaller values leak into the answer. In [1, 2, 3] the result would be 3 instead of 1.
    • Using >= in the first test. Equal values would then reset the count to 1 instead of adding to it.
    • An empty array. nums[0] throws an IndexOutOfRangeException. The lesson's tests don't use an empty array, but real code would check nums.Length first.

    Testing

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