Start learning free

LESSON 183 OF 410 · FREE CODING INTERVIEW QUESTIONS

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

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

    JAVA · FREE CODING INTERVIEW QUESTIONS

    Max Val And Number Of Occurrences in Java, explained

    Problem Definition

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

    Input:

    An array of integers, nums.

    Output:

    An array 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 and count its occurrences in a single pass through the array. This is significant in scenarios where performance is critical, such as real-time data processing.

    Common Applications:

    • Data analysis and statistics.
    • Real-time monitoring systems.
    • Competitive programming.

    Potential Pitfalls:

    • Not handling negative numbers correctly.
    • Using additional space unnecessarily.
    • Not considering edge cases like arrays with all identical elements.

    Approach

    To solve this problem efficiently, we can use a single pass through the array while maintaining two variables: one for the maximum value and one for its count.

    Naive Solution:

    A naive solution would involve two passes: 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 tasks into a single pass. We will iterate through the array once, updating the maximum value and its count as we go.

    Thought Process:

    • Initialize maxVal to the first element of the array and count to 0.
    • Iterate through the array:
      • If the current element is greater than maxVal, update maxVal and reset count to 1.
      • If the current element is equal to maxVal, increment 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:
      • If the current element is greater than maxVal, update maxVal and set count to 1.
      • If the current element is equal to maxVal, increment count.
    3. Return an array containing maxVal and count.

    Code Implementation

    public class MaxValueAndOccurrences {
    public static int[] findMaxAndCount(int[] 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 result as an array
        return new int[]{maxVal, count};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 8, 11, 8, 3, 11};
        int[] result = findMaxAndCount(nums);
        System.out.println("Max Value: " + result[0] + ", Count: " + result[1]);
    }
}

    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 regardless of the input size.

    Comparison:

    • Naive approach: O(n) time, but with two passes.
    • Optimized approach: O(n) time with a single pass.

    Edge Cases

    Consider the following edge cases:

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

    Handling Edge Cases:

    The algorithm handles these cases correctly by initializing maxVal to the first element and updating it as necessary.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple case: [2, 7, 11, 8, 11, 8, 3, 11]
    • All identical elements: [5, 5, 5, 5]
    • Negative numbers: [-1, -2, -3, -1]
    • Single element: [10]

    Testing Frameworks:

    Use JUnit or any other Java testing framework to automate the testing process.

    Thinking and Problem-Solving Tips

    When approaching such problems:

    • Break down the problem into smaller, manageable parts.
    • Think about edge cases and how to handle them.
    • Optimize your solution by reducing the number of passes through the data.
    • Practice similar problems to improve your problem-solving skills.

    Conclusion

    In this blog post, we discussed how to find the maximum value and its number of occurrences in an array in O(n) time using Java. We explored the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for efficient data processing and algorithmic thinking.

    Additional Resources

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free