Skip to main content
Talentd

Stable Subarrays With Equal Boundary and Interior Sum - Solution & Explanation

MediumArrayHash TablePrefix Sum10 min readAsked at: Amazon, Microsoft
Practice this problem

Problem Statement

You are given an integer array capacity.

A subarray capacity[l..r] is considered stable if:

  • Its length is at least 3.
  • The first and last elements are each equal to the sum of all elements strictly between them (i.e., capacity[l] = capacity[r] = capacity[l + 1] + capacity[l + 2] + ... + capacity[r - 1]).

Return an integer denoting the number of stable subarrays.

 

Example 1:

Input: capacity = [9,3,3,3,9]

Output: 2

Explanation:

  • [9,3,3,3,9] is stable because the first and last elements are both 9, and the sum of the elements strictly between them is 3 + 3 + 3 = 9.
  • [3,3,3] is stable because the first and last elements are both 3, and the sum of the elements strictly between them is 3.

Example 2:

Input: capacity = [1,2,3,4,5]

Output: 0

Explanation:

No subarray of length at least 3 has equal first and last elements, so the answer is 0.

Example 3:

Input: capacity = [-4,4,0,0,-8,-4]

Output: 1

Explanation:

[-4,4,0,0,-8,-4] is stable because the first and last elements are both -4, and the sum of the elements strictly between them is 4 + 0 + 0 + (-8) = -4

 

Constraints:

  • 3 <= capacity.length <= 105
  • -109 <= capacity[i] <= 109

Approach Overview

Problem Overview: You are given an integer array and must count subarrays where the sum of the two boundary elements equals the sum of all elements strictly inside the subarray. Formally, for subarray [l...r], the condition is nums[l] + nums[r] == sum(nums[l+1...r-1]). The challenge is evaluating this efficiently across all possible subarrays.

Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)

Enumerate every pair of indices (l, r) such that r - l >= 2 to ensure the subarray has interior elements. For each pair, iterate through the interior range l+1 to r-1 and compute its sum directly. Compare the interior sum with nums[l] + nums[r]. This approach is straightforward and useful for validating correctness during early development, but the triple nested iteration makes it too slow for large inputs.

Approach 2: Prefix Sum + Enumeration (O(n²) time, O(n) space)

Use a prefix sum array so the interior sum can be computed in constant time: interior = prefix[r] - prefix[l+1]. Then enumerate all valid boundary pairs (l, r) and check if nums[l] + nums[r] == interior. This removes the inner summation loop and reduces the complexity from cubic to quadratic. The approach is often acceptable for moderate input sizes and demonstrates a standard optimization technique used in many array problems.

Approach 3: Prefix Sum + Hash Table + Enumeration (O(n) time, O(n) space)

The equality condition can be rearranged algebraically. Since nums[l] + nums[r] = prefix[r] - prefix[l+1], move terms to get prefix[l+1] + nums[l] = prefix[r] - nums[r]. Now the expression on the left depends only on l, and the right side depends only on r. While scanning the array, maintain a hash table that counts values of prefix[l+1] + nums[l] for valid left boundaries. For each index r, compute prefix[r] - nums[r] and look it up in the map to find how many matching l values exist. To enforce the interior constraint (r - l ≥ 2), only insert index l = r - 2 into the map as the scan progresses. Each step performs constant-time hash lookups and updates, producing a linear-time solution.

Recommended for interviews: Start with the prefix-sum enumeration idea to demonstrate you understand how to convert range sums into constant-time queries. Then derive the algebraic transformation that enables the array scan with a hash table. Interviewers typically expect the final O(n) solution because it shows you can combine prefix sums, hash-based counting, and algebraic manipulation to eliminate nested loops.

Solution

We define a prefix sum array s, where s[i] represents the sum of the first i elements in the array capacity, that is, s[i] = capacity[0] + capacity[1] + ldots + capacity[i-1]. Initially, s[0] = 0.

According to the problem statement, a subarray capacity[l..r] is a stable array if:

$ capacity[l] = capacity[r] = capacity[l + 1] + capacity[l + 2] + ldots + capacity[r - 1]

That is:

capacity[l] = capacity[r] = s[r] - s[l + 1]

We can enumerate the right endpoint r. For each r, we calculate the left endpoint l = r - 2, and store the information of the left endpoints that meet the condition in a hash table. Specifically, we use a hash table cnt to record the number of occurrences of each key-value pair (capacity[l], capacity[l] + s[l + 1]).

When we enumerate the right endpoint r, we can query the hash table cnt to get the number of left endpoints that meet the condition, that is, the number of occurrences of the key-value pair (capacity[r], s[r]), and add it to the answer.

The time complexity is O(n) and the space complexity is O(n), where n$ is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n³)O(1)Conceptual baseline or verifying correctness on small inputs
Prefix Sum + Pair EnumerationO(n²)O(n)When constraints allow quadratic solutions and you want simpler implementation
Prefix Sum + Hash TableO(n)O(n)Optimal approach for large arrays using prefix sums and hash lookups

Video Solution

Stable Subarrays With Equal Boundary and Interior Sum | LeetCode 3728 | Weekly Contest 473 • Sanyam IIT Guwahati • 2,633 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Stable Subarrays With Equal Boundary and Interior Sum easy or hard?
This problem is generally classified as Medium difficulty. The brute force idea is simple, but reaching the optimal O(n) solution requires recognizing a prefix sum transformation and using a hash table to count matching expressions efficiently.
Stable Subarrays With Equal Boundary and Interior Sum Python/Java solution
The implementation typically computes prefix sums, then iterates through the array while maintaining a hash map that counts values of prefix[l+1] + nums[l]. For each right index r, compute prefix[r] - nums[r] and add the stored frequency from the map to the answer. The same logic works across Python, Java, C++, Go, and TypeScript with only syntax differences.
How to solve Stable Subarrays With Equal Boundary and Interior Sum in O(n)?
Compute a prefix sum array first. Transform the equation into prefix[l+1] + nums[l] = prefix[r] - nums[r]. While iterating r from left to right, maintain a hash map of values prefix[l+1] + nums[l] for valid left indices (l = r - 2 onward). For each r, look up prefix[r] - nums[r] in the map to count matching subarrays. Insert new left candidates as the window advances.
What is the best approach for Stable Subarrays With Equal Boundary and Interior Sum?
The optimal solution uses Prefix Sum with a Hash Table and a single linear scan. By rearranging the condition nums[l] + nums[r] = sum(l+1..r-1) into prefix[l+1] + nums[l] = prefix[r] - nums[r], the problem becomes counting matching values between left and right expressions. A hash map stores counts of valid left expressions while scanning r. This reduces the complexity to O(n) time with O(n) extra space.
Is Stable Subarrays With Equal Boundary and Interior Sum asked at Google/Amazon/Meta?
Problems combining prefix sums, algebraic transformations, and hash-based counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of subarray counting with prefix sums are especially common because they test both mathematical reasoning and efficient data structure usage.
What data structure is used in Stable Subarrays With Equal Boundary and Interior Sum?
The core data structures are a prefix sum array and a hash table (hash map). The prefix sum enables constant-time range sum queries, while the hash table tracks frequencies of transformed expressions derived from left boundaries. Together they allow counting valid subarrays in linear time.
What is the time complexity of Stable Subarrays With Equal Boundary and Interior Sum?
The optimized solution runs in O(n) time because each index is processed once and hash table operations are O(1) on average. Earlier approaches include O(n²) using prefix sums with pair enumeration and O(n³) brute force with direct summation. Most interview solutions focus on the linear-time hash-based approach.

Ready to solve this problem?

Practice Stable Subarrays With Equal Boundary and Interior Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays