3804. Number of Centered Subarrays

MediumArrayHash TableEnumeration

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

A subarray of nums is a contiguous non-empty sequence of elements within the array. A subarray is called centered if the sum of all its elements is equal to at least one of the elements that lies within that same subarray.

Your task is to return the total number of centered subarrays of nums.

In other words, for each possible subarray nums[i..j], compute the sum s of its elements. If s matches any single element inside that subarray, then this subarray counts as centered. You need to count how many such subarrays exist.

Example walkthrough:

Consider a subarray [1, 2, 3]. The sum of its elements is 1 + 2 + 3 = 6. Since 6 is not equal to any of the elements 1, 2, or 3, this subarray is not centered.

Now consider a subarray [-1, 2, -1]. The sum is -1 + 2 + (-1) = 0. Since 0 is not one of the elements -1 or 2, this subarray is not centered. But for a subarray like [2, -2, 3] with sum 3, the value 3 does appear as an element, so it is centered.

A single-element subarray [x] is always centered, because its sum equals x, which is the only element present.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Storing seen values in a hash table provides constant-time lookup and counting.

Open in Flowchart

Intuition

The most direct way to solve this problem is to examine every possible subarray and check whether it satisfies the centered condition.

The key observation is that for a subarray to be centered, two pieces of information are needed:

The sum s of all elements in the subarray.
The set of distinct elements that appear inside the subarray.

Once we have both, the check becomes simple: the subarray is centered if and only if the sum s exists among the elements of that subarray.

A naive approach would be to recompute the sum and rebuild the element collection from scratch for each subarray, but this wastes a lot of work. Instead, notice that if we fix the starting index i and then let the ending index j slide forward one step at a time, we can build everything incrementally:

The sum s only needs s += nums[j] to extend by one element.
The collection of elements only needs to add nums[j] into a hash set as we extend.

By maintaining a running sum s and a hash set st of elements seen so far in the current subarray, every time we move j forward we update both in constant time. Then we just ask: does s appear in st? Using a hash set makes this membership lookup O(1) on average.

This way, for each starting point i, we sweep j from i to the end, and at every step we instantly know whether the current subarray nums[i..j] is centered. Each valid subarray contributes 1 to the answer.

This incremental enumeration avoids redundant recomputation and turns what could be a heavier process into a clean two-pointer style scan with a hash set, giving an overall O(n^2) time complexity, where n is the length of nums.

Solution Approach

Solution 1: Hash Table + Enumeration

We enumerate all starting indices i of subarrays, then starting from index i, we enumerate the ending index j of the subarray, calculate the sum s of elements in the subarray nums[i..j], and add all elements in the subarray to the hash table st. After each enumeration, we check if s appears in the hash table st. If it does, it means the subarray nums[i..j] is a centered subarray, and we increment the answer by 1.

Here is how the implementation works step by step:

Initialize the answer. Let n be the length of nums, and set ans = 0 to record the total count of centered subarrays.
Outer loop — fix the start i. We iterate i from 0 to n - 1. For each new starting index, we reset two pieces of state:
- An empty hash set st, which will hold the distinct elements of the current subarray.
- A running sum s = 0, which accumulates the sum of the current subarray.
Inner loop — extend the end j. We iterate j from i to n - 1, growing the subarray one element at a time:
- Update the running sum with s += nums[j].
- Insert the new element into the hash set with st.add(nums[j]).
- Check the centered condition: if s in st, then the subarray nums[i..j] is centered, so we do ans += 1.
Return the result. After both loops finish, ans holds the number of centered subarrays.

The reason this works correctly is that at every iteration of the inner loop, s always equals the sum of nums[i..j], and st always contains exactly the distinct elements of nums[i..j]. Both are maintained incrementally, so the check s in st faithfully tests whether the current subarray's sum matches one of its own elements.

Data structures and patterns used:

A hash set (st) is used to store the distinct elements of the current subarray and to perform O(1) average-time membership lookups when checking s in st.
The double enumeration pattern fixes the left endpoint and slides the right endpoint, reusing the partial sum and element set instead of recomputing them.

Complexity Analysis:

Time complexity: O(n^2), since for each of the n starting indices we extend up to n ending indices, with each step doing constant-time work on average.
Space complexity: O(n), because the hash set st may hold up to n distinct elements for a single starting index.

Example Walkthrough

Let's trace through the solution approach using a small example: nums = [2, -2, 3].

We initialize ans = 0 and n = 3. We'll fix each starting index i, then slide the ending index j forward, maintaining a running sum s and a hash set st.

Outer loop iteration i = 0 — reset st = {} and s = 0.

`j`	`nums[j]`	`s += nums[j]`	`st.add(nums[j])` → `st`	`s in st`?	`ans`
0	2	`s = 2`	`{2}`	✅ `2 ∈ {2}`	1
1	-2	`s = 0`	`{2, -2}`	❌ `0 ∉ {2, -2}`	1
2	3	`s = 3`	`{2, -2, 3}`	✅ `3 ∈ {2, -2, 3}`	2

[2] has sum 2, which equals its only element → centered.
[2, -2] has sum 0, no matching element → not centered.
[2, -2, 3] has sum 3, which appears in the subarray → centered.

Outer loop iteration i = 1 — reset st = {} and s = 0.

`j`	`nums[j]`	`s += nums[j]`	`st.add(nums[j])` → `st`	`s in st`?	`ans`
1	-2	`s = -2`	`{-2}`	✅ `-2 ∈ {-2}`	3
2	3	`s = 1`	`{-2, 3}`	❌ `1 ∉ {-2, 3}`	3

[-2] has sum -2, equal to its only element → centered.
[-2, 3] has sum 1, no matching element → not centered.

Outer loop iteration i = 2 — reset st = {} and s = 0.

`j`	`nums[j]`	`s += nums[j]`	`st.add(nums[j])` → `st`	`s in st`?	`ans`
2	3	`s = 3`	`{3}`	✅ `3 ∈ {3}`	4

[3] has sum 3, equal to its only element → centered.

Final result: ans = 4.

The four centered subarrays are [2], [2, -2, 3], [-2], and [3].

Notice how the running sum s and the hash set st are never recomputed from scratch — each time j advances, we only do s += nums[j] and st.add(nums[j]), then perform an O(1) membership check. The three single-element subarrays are always centered (their sum equals their lone element), confirming the observation from the intuition section.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def centeredSubarrays(self, nums: List[int]) -> int:
6        n = len(nums)
7        count = 0  # Number of qualifying subarrays
8
9        # Fix the left boundary of the subarray at index 'start'
10        for start in range(n):
11            seen = set()      # Distinct values within the current subarray
12            prefix_sum = 0     # Running sum of nums[start..end]
13
14            # Extend the right boundary to index 'end'
15            for end in range(start, n):
16                prefix_sum += nums[end]   # Update the running sum
17                seen.add(nums[end])       # Record the current element
18
19                # If the running sum equals one of the seen values,
20                # this subarray qualifies
21                if prefix_sum in seen:
22                    count += 1
23
24        return count
25

1class Solution {
2    public int centeredSubarrays(int[] nums) {
3        int n = nums.length;
4        // Stores the count of qualifying subarrays
5        int answer = 0;
6
7        // Fix the starting index of the subarray
8        for (int start = 0; start < n; start++) {
9            // Set to track all distinct elements seen in the current subarray
10            Set<Integer> seenElements = new HashSet<>();
11            // Running prefix sum of the current subarray
12            int prefixSum = 0;
13
14            // Extend the subarray by moving the ending index
15            for (int end = start; end < n; end++) {
16                // Accumulate the current element into the running sum
17                prefixSum += nums[end];
18                // Record the current element as seen
19                seenElements.add(nums[end]);
20
21                // If the running sum equals one of the elements already seen,
22                // this subarray qualifies, so increment the answer
23                if (seenElements.contains(prefixSum)) {
24                    answer++;
25                }
26            }
27        }
28
29        return answer;
30    }
31}
32

1class Solution {
2public:
3    int centeredSubarrays(vector<int>& nums) {
4        int n = static_cast<int>(nums.size());
5        int answer = 0;
6
7        // Fix the left endpoint of the subarray at index 'left'.
8        for (int left = 0; left < n; ++left) {
9            // 'seen' stores every element value encountered in the current subarray.
10            unordered_set<int> seen;
11            // 'sum' is the running sum of the subarray [left, right].
12            int sum = 0;
13
14            // Extend the right endpoint of the subarray.
15            for (int right = left; right < n; ++right) {
16                // Accumulate the current element into the running sum.
17                sum += nums[right];
18                // Record the current element value (inserted before the check,
19                // matching the original behavior).
20                seen.insert(nums[right]);
21
22                // If the running sum equals one of the element values seen so far,
23                // this subarray qualifies and we count it.
24                if (seen.count(sum)) {
25                    ++answer;
26                }
27            }
28        }
29
30        return answer;
31    }
32};
33

1/**
2 * Counts the number of subarrays that are "centered".
3 * A subarray (from index i to j) is considered centered when the running
4 * prefix sum `sum` of that subarray equals one of the individual elements
5 * already seen within the same subarray.
6 *
7 * @param nums - The input array of numbers.
8 * @returns The total count of centered subarrays.
9 */
10function centeredSubarrays(nums: number[]): number {
11    // Length of the input array.
12    const n = nums.length;
13
14    // Accumulator for the final answer.
15    let ans = 0;
16
17    // Fix the left endpoint of the subarray at index `i`.
18    for (let i = 0; i < n; i++) {
19        // Set holding all distinct element values seen in the current subarray.
20        const seen = new Set<number>();
21
22        // Running sum of elements from index `i` to the current index `j`.
23        let sum = 0;
24
25        // Extend the subarray's right endpoint from `i` to the end.
26        for (let j = i; j < n; j++) {
27            // Update the running sum with the new element.
28            sum += nums[j];
29
30            // Record the current element value.
31            seen.add(nums[j]);
32
33            // If the running sum matches any element already encountered,
34            // this subarray qualifies as centered.
35            if (seen.has(sum)) {
36                ans++;
37            }
38        }
39    }
40
41    return ans;
42}
43

Time and Space Complexity

Time Complexity: O(n^2), where n is the length of the array nums.

The code uses a nested loop structure. The outer loop iterates over each starting index i from 0 to n - 1. For each i, the inner loop iterates over j from i to n - 1. This results in approximately n + (n-1) + ... + 1 = n(n+1)/2 iterations in total.

Within the inner loop, each operation—including the accumulation s += nums[j], the set insertion st.add(nums[j]), and the membership check s in st—runs in average O(1) time. Therefore, the overall time complexity is dominated by the nested loops, yielding O(n^2).

Space Complexity: O(n), where n is the length of the array nums.

The primary additional space is consumed by the set st, which is reset at the start of each outer-loop iteration. In the worst case, when all elements within a subarray starting at index i are distinct, the set can hold up to n elements. The scalar variables s and ans occupy constant O(1) space. Hence, the dominant space usage is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Recomputing the sum or rebuilding the element set inside the inner loop

A very common mistake is to recompute the subarray sum and rebuild the set of elements from scratch for every (start, end) pair, instead of maintaining them incrementally as the right boundary extends.

Incorrect approach:

class Solution:
    def centeredSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        for start in range(n):
            for end in range(start, n):
                sub = nums[start:end + 1]   # O(n) slice each time
                s = sum(sub)                # O(n) recomputation
                if s in set(sub):           # O(n) set rebuild
                    count += 1
        return count

This is logically correct but degrades the time complexity from O(n^2) to O(n^3), which can cause a Time Limit Exceeded on large inputs.

Solution: Maintain the running sum prefix_sum and the set seen incrementally, as in the reference code. Each step from end to end + 1 only adds one element to both, keeping the per-step cost O(1) on average.

Pitfall 2: Resetting `seen` and `prefix_sum` in the wrong scope

If the hash set and running sum are initialized outside the outer loop (or never reset when start advances), they will accumulate stale elements and sums from previous starting indices, producing wrong counts.

Incorrect approach:

class Solution:
    def centeredSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        seen = set()        # WRONG: shared across all 'start' values
        prefix_sum = 0       # WRONG: never reset
        for start in range(n):
            for end in range(start, n):
                prefix_sum += nums[end]
                seen.add(nums[end])
                if prefix_sum in seen:
                    count += 1
        return count

Solution: Both seen and prefix_sum represent state for the current starting index. They must be re-initialized at the top of the outer loop, before the inner loop begins, so each fixed start works with a clean slate.

Pitfall 3: Misunderstanding the "matches an element" condition with duplicates

A subtle conceptual trap is assuming the matched element must be a distinct value, or worrying that storing values in a set loses information. The problem only asks whether the sum equals any one element's value in the subarray. Membership testing with a set is sufficient — you never need to know how many times the value occurs, only whether it occurs at least once.

Example: For [2, -2, 3], the sum is 3 and 3 appears in seen, so it qualifies. The duplicate counts of 2 and -2 are irrelevant. Using a set instead of a list is intentional and gives O(1) average lookups.

Solution: Trust that if prefix_sum in seen correctly captures the condition. Do not overcomplicate it with frequency maps unless the problem variant explicitly requires counting occurrences.

Pitfall 4: Forgetting that single-element subarrays always qualify

Single-element subarrays [x] always satisfy the condition because the sum equals the only element. Some implementations accidentally start the inner loop at end = start + 1, skipping the single-element case and undercounting by exactly n.

Solution: Always begin the inner loop at end = start so that the length-1 subarray (where prefix_sum == nums[start] and nums[start] is in seen) is included.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering