Max Val and Number of Occurrences in O(n) Time Using C++

Input: nums = [2, 7, 11, 8, 11, 8, 3, 11]
Output: [11, 3]
Explanation: The maximum value is 11 and it appears 3 times

Your algorithm should run in O(n) time and use O(1) space.

Could you do this in one pass (e.g. looping over the array only once)?

Problem Definition

We need to find the maximum value in an array of integers and count how many times this maximum value occurs. The solution should be efficient, running in O(n) time complexity and using O(1) space complexity.

Input:

An array of integers nums.

Output:

A list containing two elements: the maximum value and its number of occurrences.

Constraints:

• The array can contain both positive and negative integers.
• The array is non-empty.

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

Understanding the Problem

The core challenge is to find the maximum value in the array and count its occurrences efficiently. This problem is significant in various applications such as statistical analysis, data processing, and more. A common pitfall is to use a two-pass solution, which is not optimal for this problem.

Approach

To solve this problem efficiently, we can use a single-pass algorithm. The idea is to iterate through the array once, keeping track of the maximum value and its count simultaneously.

Naive Solution

A naive solution would involve two passes over the array: one to find the maximum value and another to count its occurrences. This approach is not optimal as it requires O(n) time complexity but involves two passes.

Optimized Solution

We can optimize the solution by combining the two passes into one. During a single iteration, we can update the maximum value and its count as follows:

• If the current element is greater than the current maximum, update the maximum and reset the count to 1.
• If the current element is equal to the current maximum, increment the count.

Algorithm

Here is a step-by-step breakdown of the algorithm:

1. Initialize maxVal to the first element of the array and count to 0.
2. Iterate through each element in the array.
3. If the current element is greater than maxVal, update maxVal and reset count to 1.
4. If the current element is equal to maxVal, increment count.
5. Return [maxVal, count].

Code Implementation

#include <iostream>
#include <vector>
using namespace std;

pair findMaxAndCount(const vector& nums) {
    // Initialize maxVal to the first element and count to 0
    int maxVal = nums[0];
    int count = 0;

    // Iterate through the array
    for (int val : nums) {
        if (val > maxVal) {
            // Found a new maximum value
            maxVal = val;
            count = 1; // Reset count to 1
        } else if (val == maxVal) {
            // Found another occurrence of the current maximum value
            count++;
        }
    }

    // Return the maximum value and its count
    return {maxVal, count};
}

int main() {
    vector nums = {2, 7, 11, 8, 11, 8, 3, 11};
    pair result = findMaxAndCount(nums);
    cout << "Max Value: " << result.first << ", Count: " << result.second << endl;
    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n) because we only iterate through the array once. The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Consider the following edge cases:

• Array with all identical elements: [5, 5, 5, 5]
• Array with negative and positive integers: [-1, -2, 3, 4, -1, 4]
• Array with a single element: [10]

Each of these cases should be handled correctly by the algorithm.

Testing

To test the solution comprehensively, consider a variety of test cases:

• Simple cases with small arrays.
• Edge cases as mentioned above.
• Large arrays to test performance.

Using a testing framework like Google Test can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller, manageable parts.
• Think about the most efficient way to solve the problem.
• Consider edge cases and how your solution handles them.
• Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to find the maximum value in an array and count its occurrences efficiently using a single-pass algorithm in C++. Understanding and solving such problems is crucial for improving your algorithmic thinking and coding skills. Keep practicing and exploring further to master these concepts.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode - Practice coding problems.
• GeeksforGeeks - Tutorials and problem-solving tips.
• cplusplus.com - C++ documentation and tutorials.