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

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

Given an array of integers, the task is to find the maximum value in the array and the number of times this maximum value occurs.

Input:

An array of integers, nums.

Output:

An array containing two elements: the maximum value and the number of occurrences of this maximum value.

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 how many times it appears. This problem is significant in various applications such as statistical analysis, data processing, and more.

Potential pitfalls include not handling edge cases like arrays with all identical elements or arrays with negative numbers.

Approach

To solve this problem, we can use a single pass through the array to find both the maximum value and its count. This ensures an O(n) time complexity and O(1) space complexity.

Naive Solution

A naive solution would involve two passes: one to find the maximum value and another to count its occurrences. However, this is not optimal as it requires two passes through the array.

Optimized Solution

We can optimize this by using a single pass. During the iteration, we keep track of the current maximum value and its count. If we find a new maximum, we update the maximum value and reset the count. If we find another occurrence of the current maximum, we increment the count.

Algorithm

Here is a step-by-step breakdown of the optimized 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 an array containing maxVal and count.

Code Implementation

// Function to find the maximum value and its number of occurrences
function findMaxAndCount(nums) {
  // Initialize maxVal to the first element and count to 0
  let maxVal = nums[0];
  let count = 0;

  // Iterate through each element in the array
  for (let val of nums) {
    // If current value is greater than maxVal, update maxVal and reset count
    if (val > maxVal) {
      maxVal = val;
      count = 1;
    } 
    // If current value is equal to maxVal, increment count
    else if (val === maxVal) {
      count += 1;
    }
  }

  // Return the result as an array
  return [maxVal, count];
}

// Example usage
const nums = [2, 7, 11, 8, 11, 8, 3, 11];
console.log(findMaxAndCount(nums)); // Output: [11, 3]

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] should return [5, 4].
• Array with negative numbers: [-1, -2, -3, -1] should return [-1, 2].

Testing

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

• Simple cases with small arrays.
• Arrays with all identical elements.
• Arrays with negative numbers.
• Large arrays to test performance.

Thinking and Problem-Solving Tips

When approaching such problems, consider breaking down the problem into smaller parts. Think about how you can 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 in an array and its number of occurrences in O(n) time using JavaScript. We explored the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode - Practice coding problems.
• GeeksforGeeks - Tutorials and coding challenges.
• MDN Web Docs - JavaScript documentation.