3833. Count Dominant Indices

EasyArrayEnumeration

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n.

An element at index i is called dominant if it is strictly greater than the average of all the elements that appear to its right. In other words, index i is dominant when:

nums[i] > average(nums[i + 1], nums[i + 2], ..., nums[n - 1])

Here, the average of a set of numbers is computed by adding all of them together and then dividing the total by how many numbers there are.

Your task is to count how many indices i are dominant.

Keep in mind that the rightmost element of the array has no elements to its right, so it can never be dominant.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Traversing from right to left with a running suffix sum and comparing each element to the right-side average is a direct enumeration.

Open in Flowchart

Intuition

To decide whether an index i is dominant, we need to compare nums[i] against the average of every element to its right. The average is the sum of those elements divided by their count.

A naive idea would be to recompute the sum of the right-side elements for each index, but that would repeat a lot of work. Notice that as we move the index i one step to the left, the elements "to the right" of the new position are exactly the old right-side elements plus the element we just stepped over. This observation suggests a clever way to avoid recomputation.

If we traverse the array from back to front, we can keep a running suffix sum suf that always represents the total of all elements lying to the right of the current index. For each position i, the number of elements on its right is n - i - 1, so the average is simply suf / (n - i - 1). We compare nums[i] with this value, and if nums[i] is larger, we count it as dominant.

After checking position i, we update the suffix sum by adding nums[i] into suf, preparing it to be used when we examine the next position to the left. This way, each element is visited only once, giving us an efficient single-pass solution.

Solution Approach

Solution 1: Reverse Traversal

We 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 whether it is greater than the average value of the elements to its right, suf / (n - i - 1). If so, we increment the answer by one. Finally, we return the answer.

Let's walk through the implementation step by step:

Initialization: Let n be the length of nums. We set ans = 0 to count the dominant indices. We initialize the suffix sum suf = nums[-1], which is the last element of the array. This sets up suf to already hold the sum of elements to the right of index n - 2 before we start iterating.
Reverse iteration: We loop i from n - 2 down to 0 (the rightmost element at index n - 1 is skipped because it can never be dominant). At each step:
- The number of elements to the right of index i is n - i - 1.
- We check if nums[i] > suf / (n - i - 1). If this condition holds, index i is dominant, so we do ans += 1.
- We then update the suffix sum with suf += nums[i], so that suf correctly represents the sum to the right of the next index i - 1 in the following iteration.
Return: After the loop finishes, ans holds the total count of dominant indices, which we return.

Because each element is visited exactly once and we only maintain a couple of variables, the time complexity is O(n) and the space complexity is O(1), where n is the length of the array.

Example Walkthrough

Let's trace through the Reverse Traversal approach using the small example:

nums = [5, 2, 1, 8]
n = 4

We want to count how many indices i satisfy nums[i] > average(elements to the right).

Initialization:

ans = 0
suf = nums[-1] = nums[3] = 8 (the suffix sum now holds the sum of elements to the right of index 2)

Iteration (i from n - 2 = 2 down to 0):

Step 1: i = 2, nums[2] = 1

Elements to the right: [8], count = n - i - 1 = 4 - 2 - 1 = 1
Average = suf / 1 = 8 / 1 = 8
Check: 1 > 8? No → not dominant
Update suffix sum: suf += nums[2] → suf = 8 + 1 = 9

Step 2: i = 1, nums[1] = 2

Elements to the right: [1, 8], count = 4 - 1 - 1 = 2
Average = suf / 2 = 9 / 2 = 4.5
Check: 2 > 4.5? No → not dominant
Update suffix sum: suf += nums[1] → suf = 9 + 2 = 11

Step 3: i = 0, nums[0] = 5

Elements to the right: [2, 1, 8], count = 4 - 0 - 1 = 3
Average = suf / 3 = 11 / 3 ≈ 3.67
Check: 5 > 3.67? Yes → dominant! ans += 1 → ans = 1
Update suffix sum: suf += nums[0] → suf = 11 + 5 = 16

Result: The loop ends and we return ans = 1.

Only index 0 is dominant, since 5 is greater than the average (3.67) of all elements to its right.

`i`	`nums[i]`	Right elements	Average	Dominant?	`suf` after
3	8	(none)	—	skipped	8 (initial)
2	1	[8]	8.0	No	9
1	2	[1, 8]	4.5	No	11
0	5	[2, 1, 8]	3.67	Yes	16

Notice how suf is reused across iterations instead of being recomputed each time—this is what gives the solution its O(n) time and O(1) space efficiency.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def dominantIndices(self, nums: List[int]) -> int:
6        n = len(nums)
7        count = 0          # Number of indices satisfying the condition
8        suffix_sum = nums[-1]  # Running sum of elements to the right of the current index
9
10        # Traverse from the second-to-last element down to the first
11        for i in range(n - 2, -1, -1):
12            # Number of elements strictly to the right of index i
13            right_count = n - i - 1
14
15            # Check if nums[i] is greater than the average of all elements to its right
16            if nums[i] > suffix_sum / right_count:
17                count += 1
18
19            # Update the suffix sum to include the current element
20            # so it becomes the "right side" for the next (smaller) index
21            suffix_sum += nums[i]
22
23        return count
24```
25
26**Notes on the changes made:**
27
281. **Python3 syntax** — Added `from typing import List` to make `List` resolvable (often omitted in LeetCode's pre-imported environment, but needed for standalone correctness).
29
302. **Standardized naming** — Renamed `ans` → `count` and `suf` → `suffix_sum` for clarity. Introduced `right_count` to give the expression `n - i - 1` a meaningful name.
31
323. **Method name preserved** — `dominantIndices` is kept unchanged as required.
33
34**Alternative perspective:** To avoid floating-point division (which can introduce precision concerns), you could compare using multiplication instead:
35
36```python3
37if nums[i] * right_count > suffix_sum:
38    count += 1
39

1class Solution {
2    public int dominantIndices(int[] nums) {
3        // Total number of elements in the array
4        int length = nums.length;
5
6        // Counter for indices that satisfy the dominant condition
7        int answer = 0;
8
9        // Running suffix sum of elements to the right of the current index.
10        // Initialized with the last element since we start iterating from n - 2.
11        int suffixSum = nums[length - 1];
12
13        // Traverse the array from the second-to-last element down to the first
14        for (int i = length - 2; i >= 0; --i) {
15            // Number of elements strictly to the right of index i is (length - i - 1).
16            // Check whether the current element scaled by that count exceeds
17            // the sum of all elements to its right.
18            if (nums[i] * (length - i - 1) > suffixSum) {
19                answer++;
20            }
21
22            // Update the suffix sum to include the current element,
23            // preparing it for the next (left-ward) iteration.
24            suffixSum += nums[i];
25        }
26
27        // Return the total count of dominant indices found
28        return answer;
29    }
30}
31

1class Solution {
2public:
3    int dominantIndices(vector<int>& nums) {
4        int n = nums.size();
5        int ans = 0;
6        // sufSum holds the sum of all elements strictly to the right of index i
7        // Initialize with the last element so that when i = n - 2, it equals nums[n - 1]
8        int sufSum = nums[n - 1];
9        // Traverse from the second-to-last element down to the first
10        for (int i = n - 2; i >= 0; --i) {
11            // rightCount = (n - i - 1) is the number of elements to the right of i
12            // Condition nums[i] * rightCount > sufSum is equivalent to
13            // nums[i] > average of the elements to its right (multiplied form avoids division)
14            if (nums[i] * (n - i - 1) > sufSum) {
15                ++ans;
16            }
17            // Extend the suffix sum to include the current element for the next iteration
18            sufSum += nums[i];
19        }
20        return ans;
21    }
22};
23

1/**
2 * Counts the number of indices that are "dominant" over their suffix.
3 * An index i is considered dominant when nums[i] is strictly greater than
4 * the average of all elements located after index i.
5 *
6 * @param nums - The input array of numbers.
7 * @returns The count of dominant indices.
8 */
9function dominantIndices(nums: number[]): number {
10    // Total number of elements in the array.
11    const length = nums.length;
12
13    // Accumulated count of dominant indices.
14    let dominantCount = 0;
15
16    // Running suffix sum: the sum of all elements located after the current index.
17    // Initialized with the last element so the loop can start at length - 2.
18    let suffixSum = nums[length - 1];
19
20    // Traverse from the second-to-last element down to the first.
21    for (let i = length - 2; i >= 0; --i) {
22        // Number of elements strictly after index i.
23        const suffixCount = length - i - 1;
24
25        // Compare nums[i] against the suffix average without division:
26        // nums[i] > suffixSum / suffixCount  <=>  nums[i] * suffixCount > suffixSum
27        if (nums[i] * suffixCount > suffixSum) {
28            dominantCount++;
29        }
30
31        // Extend the suffix to include the current element for the next iteration.
32        suffixSum += nums[i];
33    }
34
35    return dominantCount;
36}
37

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The function iterates through the array once with a single for loop running from index n - 2 down to 0, performing constant-time operations (comparison, division, and addition) in each iteration. Thus, the total time is linear in the size of the input.
Space Complexity: O(1). The algorithm uses only a constant number of extra variables (n, ans, suf, and the loop index i), regardless of the input size. No additional data structures that scale with the input are allocated.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Floating-Point Precision Errors in the Average Comparison

The most common mistake is comparing nums[i] directly against the floating-point result of suffix_sum / right_count. Floating-point division can introduce tiny rounding errors, which is especially dangerous when nums[i] happens to equal the average exactly.

For example, consider a case where suffix_sum = 10 and right_count = 3. The true average is 3.333..., but in binary floating point this might be stored as something like 3.3333333333333335. If nums[i] is meant to be compared near this boundary, the imprecise representation can flip the result of a > comparison and produce a wrong answer.

Solution: Multiply instead of divide. Since right_count is always a positive integer, the inequality

nums[i] > suffix_sum / right_count

is mathematically equivalent to

nums[i] * right_count > suffix_sum

This keeps everything in integer arithmetic, completely eliminating precision concerns:

from typing import List


class Solution:
    def dominantIndices(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        suffix_sum = nums[-1]

        for i in range(n - 2, -1, -1):
            right_count = n - i - 1
            # Integer-only comparison avoids floating-point precision issues
            if nums[i] * right_count > suffix_sum:
                count += 1
            suffix_sum += nums[i]

        return count

Pitfall 2: Indexing into an Empty or Single-Element Array

The line suffix_sum = nums[-1] assumes the array has at least one element. If nums is empty, this raises an IndexError.

Additionally, when n == 1, the loop range(n - 2, -1, -1) becomes range(-1, -1, -1), which is empty, so the function correctly returns 0. This case is handled gracefully, but it's worth verifying the constraints guarantee n >= 1 before relying on nums[-1].

Solution: Add an explicit guard if the constraints don't guarantee a non-empty array:

if not nums:
    return 0

Pitfall 3: Off-by-One Error in the Suffix Sum Initialization

A subtle bug arises if you initialize suffix_sum = 0 and start the loop at i = n - 1 while still treating index n - 1 as a candidate. The rightmost element has no elements to its right, so it can never be dominant, and dividing by right_count = 0 would cause a ZeroDivisionError.

The correct setup pre-loads suffix_sum = nums[-1] and begins iteration at i = n - 2, ensuring right_count is always at least 1.

Solution: Always skip the last index as a candidate and seed the suffix sum with nums[-1], exactly as the reference solution does. This guarantees right_count = n - i - 1 >= 1 throughout the loop, so no division by zero can occur.

Pitfall 4: Updating the Suffix Sum Before the Comparison

The order of operations matters. If you accidentally write suffix_sum += nums[i] before the comparison, then suffix_sum would incorrectly include nums[i] itself, making it the sum of elements from index i onward rather than strictly to the right of i.

Solution: Always perform the comparison first, then update the suffix sum afterward, so that during the check suffix_sum represents only the elements strictly to the right of the current index.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering