LeetCode Problem 3833

Difficulty: 🟢 Easy
Topics: Array, Enumeration

Solution

LeetCode 3833 - Count Dominant Indices

Problem Understanding

The problem gives us an integer array nums of length n. For every index i, we must determine whether the element nums[i] is dominant.

An index is considered dominant if its value is strictly greater than the average of all elements to its right. In other words, for index i, we look at the subarray:

$$nums[i+1], nums[i+2], \dots, nums[n-1]$$

and compute its average. If nums[i] is greater than that average, then index i contributes one to the answer.

A special rule is given for the last element. Since there are no elements to its right, there is no average to compute. Therefore, the rightmost index is never considered dominant.

The input is simply an array of positive integers. The output is the count of indices that satisfy the dominance condition.

The constraints are very small:

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

Since the array length is at most 100, even quadratic algorithms are perfectly acceptable. However, it is still useful to think about how to compute the answer efficiently.

Some important edge cases include:

• An array of length 1, where the only element cannot be dominant.
• Arrays where all values are equal.
• Cases where an element equals the average exactly, since the condition requires a strict greater-than comparison.
• Arrays where the suffix contains only one element, making the average equal to that element itself.

Approaches

Brute Force

The most direct solution is to examine every index individually.

For each index i, we compute the sum of all elements to its right, calculate the average, and compare nums[i] against that average.

Since each index may require scanning the remainder of the array, the work performed is:

• Up to n choices for i
• Up to n elements scanned for each choice

This leads to O(n²) time complexity.

The approach is correct because it directly implements the definition of a dominant index. However, it repeatedly recomputes suffix sums, which is unnecessary.

Optimal Approach

The key observation is that the average depends only on:

• The sum of elements to the right
• The number of elements to the right

Instead of recomputing the suffix sum for every index, we can precompute information once.

Let:

• total_sum be the sum of the entire array.

As we move from left to right, we maintain the sum of elements already processed. Then the sum of elements to the right of index i can be computed in constant time:

$$suffix_sum = total_sum - prefix_sum - nums[i]$$

The number of elements to the right is:

$$suffix_count = n - i - 1$$

To avoid floating-point arithmetic, we compare:

$$nums[i] > \frac{suffix_sum}{suffix_count}$$

which is equivalent to:

$$nums[i] \times suffix_count > suffix_sum$$

This lets us determine dominance in constant time per index.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes suffix sums for every index
Optimal	O(n)	O(1)	Uses prefix information to derive suffix sums instantly

Algorithm Walkthrough

1. Compute the total sum of all elements in the array.
2. Initialize a variable prefix_sum to 0. This will track the sum of elements that have already been processed.
3. Initialize answer to 0.
4. Iterate through indices from 0 to n - 2. The last index is skipped because it can never be dominant.
5. For the current index i, compute the sum of elements to its right:

$$suffix_sum = total_sum - prefix_sum - nums[i]$$ 6. Compute the number of elements to the right:

$$suffix_count = n - i - 1$$ 7. Check whether:

$$nums[i] \times suffix_count > suffix_sum$$

This is equivalent to checking whether nums[i] is greater than the suffix average. 8. If the condition is true, increment answer. 9. Add nums[i] to prefix_sum so future iterations know that this element has been processed. 10. After all valid indices have been examined, return answer.

Why it works

For every index i, the algorithm computes the exact sum and size of the suffix to its right. The dominance condition depends only on these two quantities. Since

$$nums[i] > \frac{suffix_sum}{suffix_count}$$

is mathematically equivalent to

$$nums[i] \times suffix_count > suffix_sum,$$

the algorithm performs the same comparison without using floating-point arithmetic. Every index is checked exactly once, and each check matches the problem definition, so the final count is correct.

Python Solution

from typing import List

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

        total_sum = sum(nums)
        prefix_sum = 0
        answer = 0

        for i in range(n - 1):
            suffix_sum = total_sum - prefix_sum - nums[i]
            suffix_count = n - i - 1

            if nums[i] * suffix_count > suffix_sum:
                answer += 1

            prefix_sum += nums[i]

        return answer

The implementation begins by computing the sum of the entire array. This allows every suffix sum to be derived in constant time.

The variable prefix_sum tracks the sum of all elements before the current index. Using total_sum, prefix_sum, and nums[i], the algorithm computes the sum of elements to the right without scanning the suffix.

The comparison uses integer arithmetic:

nums[i] * suffix_count > suffix_sum

This avoids floating-point calculations while remaining mathematically equivalent to comparing against the average.

Finally, the loop updates prefix_sum and continues until all valid indices have been processed.

Go Solution

func dominantIndices(nums []int) int {
	n := len(nums)

	totalSum := 0
	for _, num := range nums {
		totalSum += num
	}

	prefixSum := 0
	answer := 0

	for i := 0; i < n-1; i++ {
		suffixSum := totalSum - prefixSum - nums[i]
		suffixCount := n - i - 1

		if nums[i]*suffixCount > suffixSum {
			answer++
		}

		prefixSum += nums[i]
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. Since the constraints are extremely small, integer overflow is not a concern. The algorithm uses only a few integer variables and does not allocate any additional data structures. Slices are accessed directly, and no special handling for empty arrays is required because the constraints guarantee at least one element.

Worked Examples

Example 1

Input: nums = [5, 4, 3]

Initial values:

• total_sum = 12
• prefix_sum = 0
• answer = 0

i	nums[i]	suffix_sum	suffix_count	Check	Dominant?
0	5	7	2	5 × 2 > 7	Yes
1	4	3	1	4 × 1 > 3	Yes

After index 0:

• answer = 1
• prefix_sum = 5

After index 1:

• answer = 2
• prefix_sum = 9

Final answer:

2

Example 2

Input: nums = [4, 1, 2]

Initial values:

• total_sum = 7
• prefix_sum = 0
• answer = 0

i	nums[i]	suffix_sum	suffix_count	Check	Dominant?
0	4	3	2	4 × 2 > 3	Yes
1	1	2	1	1 × 1 > 2	No

After index 0:

• answer = 1
• prefix_sum = 4

After index 1:

• answer = 1
• prefix_sum = 5

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is processed exactly once
Space	O(1)	Only a few variables are used regardless of input size

The algorithm makes one pass to compute the total sum and one pass to count dominant indices. Both passes are linear, so the overall time complexity remains O(n). No auxiliary arrays or data structures are created, resulting in constant extra space usage.

Test Cases

from typing import List

s = Solution()

assert s.dominantIndices([5, 4, 3]) == 2      # Example 1
assert s.dominantIndices([4, 1, 2]) == 1      # Example 2

assert s.dominantIndices([10]) == 0           # Single element
assert s.dominantIndices([5, 5]) == 0         # Equal values
assert s.dominantIndices([6, 5]) == 1         # First larger than last
assert s.dominantIndices([1, 2]) == 0         # First smaller than last

assert s.dominantIndices([3, 3, 3, 3]) == 0  # All equal
assert s.dominantIndices([10, 1, 1, 1]) == 1 # Large first element
assert s.dominantIndices([1, 1, 10]) == 0    # Large last element

assert s.dominantIndices([2, 1, 1]) == 1     # Dominant at start
assert s.dominantIndices([8, 4, 2, 1]) == 3  # Every valid index dominant

assert s.dominantIndices([2, 2, 2, 1]) == 2  # Multiple dominant indices
assert s.dominantIndices([1, 100, 1, 100]) == 1  # Alternating values

assert s.dominantIndices([4, 2, 6, 2]) == 1  # Mixed values

Test Summary

Test	Why
[5,4,3]	First official example
[4,1,2]	Second official example
[10]	Smallest valid array
[5,5]	Equality should not count
[6,5]	Single valid dominant index
[1,2]	No dominant index
[3,3,3,3]	Uniform values
[10,1,1,1]	Very large first element
[1,1,10]	Large value at end only
[2,1,1]	Dominance from first position
[8,4,2,1]	Every eligible index dominant
[2,2,2,1]	Multiple dominant positions
[1,100,1,100]	Alternating large and small values
[4,2,6,2]	General mixed-case validation

Edge Cases

Array of Length One

When the array contains only one element, there are no elements to the right of any index. The problem explicitly states that the rightmost element is never dominant. Since the only element is also the rightmost element, the answer must be zero.

The implementation handles this naturally because the loop runs from 0 to n - 2. When n = 1, the loop executes zero times and returns 0.

Values Equal to the Suffix Average

The dominance condition requires a strict inequality. If an element equals the average of the suffix, it should not be counted.

For example, in [5, 5], the first element equals the suffix average of 5. The comparison

nums[i] * suffix_count > suffix_sum

evaluates to 5 > 5, which is false, so the index is correctly excluded.

Suffix Consisting of One Element

Near the end of the array, the suffix may contain exactly one value. In that situation, the average is simply that value itself.

For example, in [6, 5], the suffix for index 0 is [5], whose average is 5. The algorithm computes:

6 * 1 > 5

which correctly identifies index 0 as dominant. This case is handled without any special logic because the suffix count formula naturally becomes 1.

Large First Element with Small Remaining Values

Arrays such as [100, 1, 1, 1, 1] can expose mistakes in suffix-sum calculations. If the suffix sum is computed incorrectly, the first index may be misclassified.

The implementation derives each suffix sum from:

total_sum - prefix_sum - nums[i]

which guarantees that all elements to the right are included exactly once. Therefore even highly unbalanced arrays are processed correctly.