Watch 10 video solutions for Count Dominant Indices, a easy level problem involving Array, Enumeration. This walkthrough by Developer Coder has 130 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |