3833. Count Dominant Indices - Solution & Explanation

Q: Is Count Dominant Indices easy or hard?

Count Dominant Indices is typically classified as an Easy problem. The brute force approach is straightforward, and recognizing the reverse traversal optimization reduces the complexity to O(n). It mainly tests basic array traversal and observation of suffix properties.

Q: Count Dominant Indices Python/Java solution

The implementation is identical across languages: iterate from the end of the array, track maxSoFar, and increment a counter whenever the current element exceeds it. FleetCode provides implementations in Python, Java, C++, Go, and TypeScript using the same O(n) reverse traversal logic.

Q: How to solve Count Dominant Indices in O(n)?

Use reverse traversal. Start from the last element and maintain a variable maxSoFar that stores the maximum value encountered so far. If nums[i] is greater than maxSoFar, increment the dominant index count and update maxSoFar. This avoids repeatedly scanning the suffix of the array.

Q: What is the best approach for Count Dominant Indices?

The optimal approach is reverse traversal with a running maximum. Traverse the array from right to left and keep track of the largest value seen so far. If the current element is greater than that maximum, it dominates all elements to its right. This method runs in O(n) time and O(1) space.

Q: Is Count Dominant Indices asked at Google/Amazon/Meta?

Array scanning and suffix-maximum patterns frequently appear in interviews at companies like Amazon and Google. Variants of the 'array leaders' or dominant element problems test your ability to optimize from O(n²) enumeration to O(n) single-pass solutions.

Q: What data structure is used in Count Dominant Indices?

The problem primarily uses arrays and simple variables. The optimized solution relies on maintaining a running maximum during reverse traversal rather than additional data structures such as heaps or hash maps.

Q: What is the time complexity of Count Dominant Indices?

The optimal solution runs in O(n) time because the array is scanned once from right to left. Only constant-time comparisons and updates are performed for each element. Space complexity is O(1) since only a running maximum and a counter are stored.

The problem

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:

At index i = 0, the value 5 is dominant as 5 > average(4, 3) = 3.5.
At index i = 1, the value 4 is dominant over the subarray [3].
Index 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:

At index i = 0, the value 4 is dominant over the subarray [1, 2].
At index i = 1, the value 1 is not dominant.
Index i = 2 is not dominant as there are no elements to its right. Thus, the answer is 1.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Approach overview

Problem 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.

Solution

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

class Solution:
    def dominantIndices(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        suf = nums[-1]
        for i in range(n - 2, -1, -1):
            if nums[i] > suf / (n - i - 1):
                ans += 1
            suf += nums[i]
        return ans

Java

class Solution {
    public int dominantIndices(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int suf = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] * (n - i - 1) > suf) {
                ans++;
            }
            suf += nums[i];
        }
        return ans;
    }
}

C++

class Solution {
public:
    int dominantIndices(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        int suf = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] * (n - i - 1) > suf) {
                ans++;
            }
            suf += nums[i];
        }
        return ans;
    }
};

TypeScript

function dominantIndices(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    let suf = nums[n - 1];
    for (let i = n - 2; i >= 0; --i) {
        if (nums[i] * (n - i - 1) > suf) {
            ans++;
        }
        suf += nums[i];
    }
    return ans;
}

func dominantIndices(nums []int) int {
	n := len(nums)
	ans := 0
	suf := nums[n-1]
	for i := n - 2; i >= 0; i-- {
		if nums[i]*(n-i-1) > suf {
			ans++
		}
		suf += nums[i]
	}
	return ans
}

Try this approach in the editor

Complexity analysis

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

Frequently asked questions

Is Count Dominant Indices easy or hard?

Count Dominant Indices is typically classified as an Easy problem. The brute force approach is straightforward, and recognizing the reverse traversal optimization reduces the complexity to O(n). It mainly tests basic array traversal and observation of suffix properties.

Count Dominant Indices Python/Java solution

The implementation is identical across languages: iterate from the end of the array, track maxSoFar, and increment a counter whenever the current element exceeds it. FleetCode provides implementations in Python, Java, C++, Go, and TypeScript using the same O(n) reverse traversal logic.

How to solve Count Dominant Indices in O(n)?

Use reverse traversal. Start from the last element and maintain a variable maxSoFar that stores the maximum value encountered so far. If nums[i] is greater than maxSoFar, increment the dominant index count and update maxSoFar. This avoids repeatedly scanning the suffix of the array.

What is the best approach for Count Dominant Indices?

The optimal approach is reverse traversal with a running maximum. Traverse the array from right to left and keep track of the largest value seen so far. If the current element is greater than that maximum, it dominates all elements to its right. This method runs in O(n) time and O(1) space.

Is Count Dominant Indices asked at Google/Amazon/Meta?

Array scanning and suffix-maximum patterns frequently appear in interviews at companies like Amazon and Google. Variants of the 'array leaders' or dominant element problems test your ability to optimize from O(n²) enumeration to O(n) single-pass solutions.

What data structure is used in Count Dominant Indices?

The problem primarily uses arrays and simple variables. The optimized solution relies on maintaining a running maximum during reverse traversal rather than additional data structures such as heaps or hash maps.

What is the time complexity of Count Dominant Indices?

The optimal solution runs in O(n) time because the array is scanned once from right to left. Only constant-time comparisons and updates are performed for each element. Space complexity is O(1) since only a running maximum and a counter are stored.

Count Dominant Indices solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Count Dominant Indices solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems