Start learning free

LESSON 188 OF 415 · FREE CODING INTERVIEW QUESTIONS

Max Value and Its Occurrences in Swift: One Pass, O(n) Time, O(1) Space

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

    SWIFT · FREE CODING INTERVIEW QUESTIONS

    Max Val And Number Of Occurrences in Swift, explained

    Problem overview

    The method maxValNumOfOccurrences receives an array of integers, nums, and returns an array of two integers: 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 one loop over the array is enough.

    Approach: update the maximum and the count together

    The simplest plan has two passes: find the maximum with one loop, then count how many elements equal it with a second loop. That is already O(n) time and O(1) space, but it reads the array twice.

    func twoPass(_ nums: [Int]) -> [Int] {
    var maxValue = nums[0]
    for value in nums where value > maxValue {
        maxValue = value
    }
    var count = 0
    for value in nums where value == maxValue {
        count += 1
    }
    return [maxValue, count]
}

    Here where after a for-in loop filters which elements run the body. For the example array it returns [11, 3] as well.

    The single-pass version has one practical advantage: it never needs to look at an element again, so it would also work on values that arrive one at a time and cannot be re-read.

    A single pass works because each element tells you everything you need at the moment you see it. Keep two variables: the largest value so far and how many times it has appeared so far. For each element there are three cases:

    • It is greater than the current maximum. This is a new champion, seen once so far. Replace the maximum and reset the count to 1. Occurrences of the old, smaller maximum no longer matter.
    • It is equal to the current maximum. This is one more occurrence, so add 1 to the count.
    • It is smaller. Nothing changes.

    On the example, the running state (maxValue, count) goes (2, 1), (7, 1), (11, 1), then stays (11, 1) for 8, becomes (11, 2) on the second 11, stays for 8 and 3, and ends at (11, 3).

    Step by step

    1. Declare maxValue and count with var. Both are reassigned in the loop. maxValue starts at nums[0], a value that really is in the array. Starting at 0 would be wrong for an array of negative numbers. count starts at 0.
    2. Loop with for value in nums. Swift's for-in needs no parentheses and no index.
    3. Test value > maxValue. The comparison is strict: an equal value is not a new maximum, just another occurrence.
    4. On a new maximum, assign it and set count = 1. This is the first occurrence of the new maximum.
    5. Add else if value == maxValue and increment count. Using else if keeps the two cases exclusive, so a value that just became the maximum is not counted twice.
    6. Return [maxValue, count]. The order matches what the task asks for.

    Why does count start at 0 when the first element is already the maximum? The loop visits nums[0] too. It equals maxValue, so the else if branch counts it as the first occurrence.

    The solution in Swift

    class Solution {
    func maxValNumOfOccurrences(_ nums: [Int]) -> [Int] {
        var maxValue = nums[0]
        var count = 0
        for value in nums {
            if value > maxValue {
                maxValue = value
                count = 1
            } else if value == maxValue {
                count += 1
            }
        }
        return [maxValue, count]
    }
}

    Swift details worth knowing:

    • No ++. Swift has no increment operator, so the code uses count += 1.
    • The loop variable is a constant. Inside for value in nums, value is a fresh let on every iteration. Assigning to it is a compile error, and it is not needed here.
    • Braces and else if. The braces are mandatory, and } else if goes on the line of the closing brace by convention.
    • Arrays are values. nums is a copy-on-assignment value type and the method never changes it, so the caller's array is untouched.
    • The return type. Returning two numbers as an [Int] is what the lesson's tests expect, with the maximum at index 0 and the count at index 1.

    Calling it:

    let solution = Solution()
print(solution.maxValNumOfOccurrences([2, 7, 11, 8, 11, 8, 3, 11]))
print(solution.maxValNumOfOccurrences([-5, -5, -9]))
print(solution.maxValNumOfOccurrences([4]))

    [11, 3]
[-5, 2]
[4, 1]

    Complexity

    Time: O(n). The loop visits each element once and does a constant amount of work for it. Space: O(1). The method keeps two integers and builds a two-element result, whatever the size of nums.

    Edge cases and common mistakes

    • All values negative. [-5, -5, -9] returns [-5, 2]. This is the reason for starting from nums[0] instead of 0.
    • A single element. [4] returns [4, 1].
    • All elements equal. [6, 6, 6] returns [6, 3]: the first element is counted by the else if branch, and the other two add 1 each.
    • The maximum at the end. [1, 2, 2, 9] returns [9, 1]. The count is reset when 9 arrives, which discards the two 2s.
    • Forgetting the reset. If a new maximum does not set count = 1, the count carries over occurrences of an older, smaller value.
    • Two separate ifs. Replacing else if with a second if makes a new maximum set count = 1 and then immediately match the equality test and add another 1, giving 2.
    • An empty array. nums[0] on an empty array stops the program with a run-time crash. The task describes inputs that have at least one element; if empty input were possible, a guard !nums.isEmpty check at the top would be needed.

    Testing

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