Count dominant indices

Array Enumeration

65.8% acceptance

Mar 16, 2026

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn dominant_indices(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n <= 1 {
      return 0;
    }

    // Compute suffix sum from right
    let mut suffix_sum: Vec<i64> = vec![0; n + 1];
    for i in (0..n).rev() {
      suffix_sum[i] = suffix_sum[i + 1] + nums[i] as i64;
    }

    let mut count = 0;
    for i in 0..n - 1 {
      let remaining = (n - 1 - i) as i64;
      let sum_right = suffix_sum[i + 1];
      // nums[i] > sum_right / remaining
      // equivalent to: nums[i] * remaining > sum_right (since remaining > 0)
      if (nums[i] as i64) * remaining > sum_right {
        count += 1;
      }
    }

    count
  }
}