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 is11and it appears3times

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)?

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.

An array of integers, `nums`

.

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

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

Input:nums=`[2, 7, 11, 8, 11, 8, 3, 11]`

Output:[11, 3]Explanation:The maximum value is11and it appears3times

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.

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

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

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.

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.

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.

- 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`

.

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

- Initialize
`maxVal`

to the first element of the array and`count`

to 0. - 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`

. - Return an array containing
`maxVal`

and`count`

.

```
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]);
}
}
```

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.

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

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]`

The algorithm handles these cases correctly by initializing `maxVal`

to the first element and updating it as necessary.

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]`

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

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.

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.

- LeetCode - Practice coding problems.
- GeeksforGeeks - Tutorials and explanations on various algorithms.
- Java Documentation - Official Java tutorials and documentation.