Count Dominant Indices

Difficulty: Easy | Acceptance: 66.00% | Paid: No Topics: Array, Enumeration

You are given a 0-indexed integer array nums. An index i is called dominant if nums[i] is strictly greater than the sum of all elements to its left and strictly greater than the sum of all elements to its right.

Return the number of dominant indices.

• Examples
• Constraints
• Brute Force
• Prefix and Suffix Sums
• Optimized Single Pass

Examples

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 <= 10⁵
1 <= nums[i] <= 10⁹

Brute Force

Intuition For each index i, we can explicitly calculate the sum of elements to the left and the sum of elements to the right by iterating through the array.

Steps

• Iterate through each index i from 0 to n-1.
• For each i, initialize leftSum and rightSum to 0.
• Iterate from 0 to i-1 to calculate leftSum.
• Iterate from i+1 to n-1 to calculate rightSum.
• Check if nums[i] > leftSum and nums[i] > rightSum. If yes, increment the count.
• Return the total count.

from typing import List

class Solution:
    def dominantIndices(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        for i in range(n):
            left_sum = 0
            right_sum = 0
            for j in range(i):
                left_sum += nums[j]
            for j in range(i + 1, n):
                right_sum += nums[j]
            if nums[i] > left_sum and nums[i] > right_sum:
                count += 1
        return count

Complexity

• Time: O(n²) - For each element, we traverse the array.
• Space: O(1) - We only use a few variables.
• Notes: This approach will time out for large inputs (n = 10⁵).

Prefix and Suffix Sums

Intuition We can precompute the cumulative sums from the left (prefix) and from the right (suffix). This allows us to find the sum of elements to the left and right of any index i in constant time.

Steps

• Create an array prefix where prefix[i] is the sum of elements from 0 to i-1.
• Create an array suffix where suffix[i] is the sum of elements from i+1 to n-1.
• Iterate through the array. For each index i, the left sum is prefix[i] and the right sum is suffix[i].
• Check the dominance condition and update the count.

from typing import List

class Solution:
    def dominantIndices(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        suffix = [0] * (n + 1)
        
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
            
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] + nums[i]
            
        count = 0
        for i in range(n):
            left_sum = prefix[i]
            right_sum = suffix[i + 1]
            if nums[i] > left_sum and nums[i] > right_sum:
                count += 1
                
        return count

Complexity

• Time: O(n) - Three passes through the array.
• Space: O(n) - To store the prefix and suffix arrays.
• Notes: We can optimize space further by calculating the total sum first and deriving the right sum on the fly.

Optimized Single Pass

Intuition We can calculate the total sum of the array once. As we iterate through the array, we maintain the leftSum. The rightSum can be calculated as totalSum - leftSum - nums[i]. This eliminates the need for extra arrays.

Steps

• Calculate the totalSum of all elements in nums.
• Initialize leftSum to 0 and count to 0.
• Iterate through each element num in nums:
  • Calculate rightSum as totalSum - leftSum - num.
  • Check if num > leftSum and num > rightSum.
  • If true, increment count.
  • Add num to leftSum.
• Return count.

from typing import List

class Solution:
    def dominantIndices(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0
        count = 0
        
        for num in nums:
            right_sum = total_sum - left_sum - num
            if num > left_sum and num > right_sum:
                count += 1
            left_sum += num
            
        return count

Complexity

• Time: O(n) - Two passes through the array (one for sum, one for check).
• Space: O(1) - Only a few variables used.
• Notes: This is the optimal solution. Note that we use long (Java) or long long (C++) for sums to prevent integer overflow, as the sum can exceed the range of a 32-bit integer.