You are given an integer array nums of length n.
An element at index i is called dominant if: nums[i] > average(nums[i + 1], nums[i + 2], ..., nums[n - 1])
Your task is to count the number of indices i that are dominant.
The average of a set of numbers is the value obtained by adding all the numbers together and dividing the sum by the total number of numbers.
Note: The rightmost element of any array is not dominant.
Example 1:
Input: nums = [5,4,3]
Output: 2
Explanation:
i = 0, the value 5 is dominant as 5 > average(4, 3) = 3.5.i = 1, the value 4 is dominant over the subarray [3].i = 2 is not dominant as there are no elements to its right. Thus, the answer is 2.Example 2:
Input: nums = [4,1,2]
Output: 1
Explanation:
i = 0, the value 4 is dominant over the subarray [1, 2].i = 1, the value 1 is not dominant.i = 2 is not dominant as there are no elements to its right. Thus, the answer is 1.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100Problem Overview: You are given an integer array and need to count how many indices are dominant. An index is dominant if its value is greater than every element that appears to its right in the array.
This is closely related to the classic "array leaders" pattern. The key challenge is checking whether each element dominates all elements to its right without repeatedly scanning the suffix of the array.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Check every index and verify whether it is greater than all elements to its right. For each position i, iterate from i + 1 to the end of the array and track the maximum value in that suffix. If none of those elements are greater than or equal to nums[i], then i is dominant.
This method uses straightforward enumeration. The drawback is repeated scanning of the same suffix ranges, leading to O(n²) time in the worst case. It works fine for small arrays but does not scale well.
Approach 2: Reverse Traversal with Running Maximum (O(n) time, O(1) space)
Traverse the array from right to left while maintaining the maximum value seen so far. The rightmost element is always dominant because nothing appears after it. Store this value as maxSoFar.
For each index i while moving left, compare nums[i] with maxSoFar. If nums[i] is greater, it dominates every element to its right, so increment the count and update maxSoFar. Otherwise, update maxSoFar if needed and continue.
This works because the running maximum represents the largest value in the suffix i+1 ... n-1. The algorithm performs a single pass and constant-time comparisons, making it optimal for problems involving suffix dominance in arrays. This reverse scanning pattern is a common optimization when suffix information can be maintained incrementally.
Recommended for interviews: Start by explaining the brute force enumeration to show you understand the definition of dominance. Then transition to the reverse traversal optimization. Interviewers expect the O(n) solution because it eliminates repeated suffix scans using a simple running maximum.
We can traverse the array from back to front, maintaining a suffix sum suf, which represents the sum of all elements to the right of the current element. For each element, we check if it is greater than the average value of the elements to its right \frac{suf}{n - i - 1}. If so, we increment the answer by one. Finally, we return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the definition of dominant indices or when constraints are very small |
| Reverse Traversal with Running Maximum | O(n) | O(1) | General case and optimal solution when scanning arrays with suffix comparisons |
Count Dominant Indices | Leetcode 3833 | Weekly Contest 488 | Java Code | Developer Coder • Developer Coder • 130 views views
Watch 9 more video solutions →Practice Count Dominant Indices with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor