Valid Elements in an Array

Difficulty: Easy | Acceptance: 57.00% | Paid: No Topics: N/A

You are given an integer array nums. An element nums[i] is valid if it is strictly greater than the sum of all elements to its left. Return the number of valid elements in the array.

• Examples
• Constraints
• Approach 1: Iterative Prefix Sum
• Approach 2: Brute Force Summation

Examples

Example 1:

Input: nums = [1, 2, 3, 4]
Output: 2
Explanation: 
- nums[0] = 1 is valid because sum of elements to its left is 0.
- nums[1] = 2 is valid because 2 > 1.
- nums[2] = 3 is not valid because 3 is not greater than 1 + 2 = 3.
- nums[3] = 4 is not valid because 4 is not greater than 1 + 2 + 3 = 6.

Example 2:

Input: nums = [10, 2, 5, 3]
Output: 1
Explanation:
- nums[0] = 10 is valid.
- nums[1] = 2 is not valid because 2 is not greater than 10.
- nums[2] = 5 is not valid because 5 is not greater than 10 + 2 = 12.
- nums[3] = 3 is not valid because 3 is not greater than 10 + 2 + 5 = 17.

Example 3:

Input: nums = [1, 1, 1]
Output: 1
Explanation:
- nums[0] = 1 is valid.
- nums[1] = 1 is not valid because 1 is not greater than 1.
- nums[2] = 1 is not valid because 1 is not greater than 1 + 1 = 2.

Constraints

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

Approach 1: Iterative Prefix Sum

Intuition We can iterate through the array while maintaining a running sum of all elements encountered so far. For each element, we simply check if it is greater than this running sum.

Steps

• Initialize a variable total_sum to 0 and count to 0.
• Iterate through each number num in the array nums.
• If num is strictly greater than total_sum, increment count.
• Add num to total_sum.
• Return count.

class Solution:
    def countValidElements(self, nums: list[int]) -> int:
        total_sum = 0
        count = 0
        for num in nums:
            if num > total_sum:
                count += 1
            total_sum += num
        return count

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the optimal solution as it requires a single pass through the array.

Approach 2: Brute Force Summation

Intuition For every element at index i, explicitly calculate the sum of all elements from index 0 to i-1 and compare it with the current element.

Steps

• Initialize count to 0.
• Iterate through the array with index i.
• For each i, calculate the sum of elements from 0 to i-1.
• If nums[i] is greater than this sum, increment count.
• Return count.

class Solution:
    def countValidElements(self, nums: list[int]) -> int:
        count = 0
        n = len(nums)
        for i in range(n):
            left_sum = sum(nums[:i])
            if nums[i] > left_sum:
                count += 1
        return count

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: This approach is inefficient for larger arrays but demonstrates the brute force logic clearly.