Skip to content

3833. Count Dominant Indices

Description

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​​​​​​​

Solutions

Solution 1: Reverse Traversal

Thinking

A dominant index is strictly larger than the average of the suffix to its right; the last index is excluded. \(n \le 100\) allows recomputing each suffix, but those sums overlap.

The suffix average depends only on the suffix sum and its length.

Walk right to left with a running suffix sum \(\textit{suf}\), compare \(nums[i]\) with \(\textit{suf}/(n-i-1)\), then fold \(nums[i]\) into the suffix.

One reverse pass decides every index.

We can traverse the array from back to front, maintaining a suffix sum \(\text{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{\text{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 \(\text{nums}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
}

Comments