Count How Often the Maximum Appears
Solve this ProblemEasy10 min
Topics
BasicsComplexityArrays
Companies
TCSInfosysWipro
Given an array
nums, return how many times its largest value appears.
Both solutions are O(n)Linear Time O(n)Work that grows in direct proportion to the input size: twice the data, about twice the time.: every element is looked at a fixed number of times, so doubling the array roughly doubles the work. Two passes cost 2n and one pass costs n, but Big-O ignores constant factors — both are linear. Linear time is usually the best possible when every element has to be inspected.
Test Case 1:
Input:nums = [3, 9, 2, 9, 9]
Output:3
Explanation:The maximum is 9 and it appears three times.
Test Case 2:
Input:nums = [-4, -7]
Output:1
Explanation:With all-negative values the maximum is −4, appearing once.
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
-1000000 ≤ nums[i] ≤ 1000000
Try the Dry Run
Approach & Solutions
Two PassesGood
First walk the array to find the maximum. Then walk it a second time and count how many values equal that maximum. Two passes of n steps is 2n steps — still linear time, O(n), because the work grows in direct proportion to the length.
Time
O(n)Space
O(1)Java
class Solution {
public int maxCount(int[] nums) {
int best = nums[0];
for (int value : nums) {
if (value > best) {
best = value;
}
}
int count = 0;
for (int value : nums) {
if (value == best) {
count++;
}
}
return count;
}
}One Pass, Reset on a New MaximumOptimal
Track the best value so far and how many times it has been seen. A bigger value starts a new maximum, so reset the count to 1; an equal value adds one to the count; smaller values change nothing. One pass is enough. It is still O(n) — just with a smaller constant.
Time
O(n)Space
O(1)Java
class Solution {
public int maxCount(int[] nums) {
int best = nums[0];
int count = 0;
for (int value : nums) {
if (value > best) {
best = value;
count = 1;
} else if (value == best) {
count++;
}
}
return count;
}
}