LeetCode 3804 - Number of Centered Subarrays

The problem asks us to count the number of centered subarrays in a given integer array nums. A subarray is called centered if the sum of its elements is equal to at least one element within that subarray.

leetcodemediumarrayhash-tableenumeration

LeetCode Problem 3804

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Enumeration

Solution

Problem Understanding

The problem asks us to count the number of centered subarrays in a given integer array nums. A subarray is called centered if the sum of its elements is equal to at least one element within that subarray. In simpler terms, for every contiguous sequence of numbers in nums, we need to check whether the total sum of that sequence matches any of its individual elements.

The input is a single array of integers, with lengths ranging from 1 to 500 and elements ranging from -10^5 to 10^5. The expected output is a single integer representing the total number of centered subarrays.

Key constraints and observations include:

  • Subarrays can be of length 1. By definition, all single-element subarrays are always centered because the sum equals the element itself.
  • Negative numbers are allowed, so simply comparing sums to positive elements is insufficient.
  • The array is small enough (length ≤ 500) to allow solutions that are quadratic in time complexity.

Important edge cases to keep in mind are:

  • Single-element arrays.
  • Arrays containing only negative numbers.
  • Arrays where no multi-element subarray is centered.

Approaches

The brute-force approach is straightforward: enumerate all subarrays of nums, compute their sum, and check if this sum exists in the subarray. This guarantees correctness because it checks every possible subarray directly against the definition.

However, this approach can be inefficient because there are $O(n^2)$ subarrays and checking for the sum within the subarray takes $O(k)$ for each subarray of length $k$. In the worst case, this results in $O(n^3)$ time complexity.

A more optimal approach leverages the fact that the array length is small enough to allow a quadratic solution. We can generate all subarrays and maintain a running sum. For each subarray, we can use a set to quickly check if the current sum exists among the elements of the subarray, reducing the sum lookup to $O(1)$. This approach reduces the inner check from linear to constant time at the cost of additional space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Enumerate all subarrays, compute sum, check sum within subarray linearly
Optimal O(n^2) O(n) Enumerate all subarrays, maintain running sum and set of elements for O(1) sum lookup

Algorithm Walkthrough

  1. Initialize a counter count to 0 to track the number of centered subarrays.
  2. Loop over each starting index i of the array. For each i, initialize a variable current_sum to 0 and an empty set seen_elements.
  3. For each ending index j starting from i to the end of the array, add nums[j] to current_sum and add nums[j] to seen_elements.
  4. Check if current_sum exists in seen_elements. If it does, increment count.
  5. Continue until all subarrays starting from i are processed.
  6. Return the final count after all starting indices are processed.

Why it works: The algorithm maintains the invariant that current_sum is the sum of the subarray from i to j and seen_elements contains exactly the elements of that subarray. Therefore, checking if current_sum is in seen_elements correctly determines whether the subarray is centered.

Python Solution

from typing import List

class Solution:
    def centeredSubarrays(self, nums: List[int]) -> int:
        count = 0
        n = len(nums)
        
        for i in range(n):
            current_sum = 0
            seen_elements = set()
            for j in range(i, n):
                current_sum += nums[j]
                seen_elements.add(nums[j])
                if current_sum in seen_elements:
                    count += 1
        
        return count

In this implementation, we iterate over each possible starting index i and for each, we extend the subarray to include each j ≥ i. We maintain a running sum and a set of elements in the subarray. Checking current_sum in seen_elements ensures we only count valid centered subarrays. This implementation follows the quadratic approach described above.

Go Solution

func centeredSubarrays(nums []int) int {
    n := len(nums)
    count := 0

    for i := 0; i < n; i++ {
        currentSum := 0
        seenElements := make(map[int]bool)
        for j := i; j < n; j++ {
            currentSum += nums[j]
            seenElements[nums[j]] = true
            if seenElements[currentSum] {
                count++
            }
        }
    }

    return count
}

The Go version uses a map to mimic a set, tracking elements of the current subarray. The running sum is checked against the keys of the map, analogous to the Python set lookup. This preserves the same O(n^2) time complexity and O(n) space per iteration.

Worked Examples

Example 1: nums = [-1,1,0]

Subarray Sum Elements Set Centered?
[-1] -1 {-1} Yes
[1] 1 {1} Yes
[0] 0 {0} Yes
[-1,1] 0 {-1,1} No
[1,0] 1 {1,0} Yes
[-1,1,0] 0 {-1,0,1} Yes

Total = 5

Example 2: nums = [2,-3]

Subarray Sum Elements Set Centered?
[2] 2 {2} Yes
[-3] -3 {-3} Yes
[2,-3] -1 {2,-3} No

Total = 2

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Two nested loops over array indices; inner set operations are O(1)
Space O(n) Set stores up to n elements of current subarray

The algorithm avoids the cubic brute-force approach by using a set for O(1) lookups, ensuring quadratic performance.

Test Cases

sol = Solution()

# Provided examples
assert sol.centeredSubarrays([-1,1,0]) == 5  # Mix of negative, positive, zero
assert sol.centeredSubarrays([2,-3]) == 2    # Only single-element subarrays

# Edge cases
assert sol.centeredSubarrays([0]) == 1       # Single zero
assert sol.centeredSubarrays([-5]) == 1      # Single negative
assert sol.centeredSubarrays([1,1,1]) == 6   # All ones, multiple subarrays sum to 1
assert sol.centeredSubarrays([-1,-2,-3]) == 3 # Negative numbers, only single elements
assert sol.centeredSubarrays([100000,-100000]) == 2 # Max and min numbers
Test Why
[-1,1,0] Mix of negative, positive, zero, multiple centered subarrays
[2,-3] Only single-element subarrays count
[0] Single-element zero
[-5] Single-element negative
[1,1,1] Repeated elements, sums can match subarray elements
[-1,-2,-3] All negative, only single-element subarrays
[100000,-100000] Edge of value constraints

Edge Cases

One important edge case is a single-element array. Since the sum equals the element itself, these subarrays are trivially centered. The implementation correctly counts them.

Another edge case involves arrays where no multi-element subarray is centered, such as strictly decreasing negative sequences. The algorithm correctly counts only single-element subarrays.

A third edge case is arrays with repeated elements, where multiple subarrays may have the same sum as one of their elements. The algorithm correctly handles this by using a set, ensuring that all matches of the sum with any element are counted.

This solution is robust to the entire range of allowed input values, including large positive and negative numbers, as the sum is computed incrementally and checked against the current set of elements.