Stable Subarrays With Equal Boundary and Interior Sum

Stable Subarrays With Equal Boundary and Interior Sum

What is this problem about?

The Stable Subarrays With Equal Boundary and Interior Sum coding problem is a specialized array task. A subarray is considered "stable" if the sum of its boundary elements (the first and last elements of the subarray) is equal to the sum of its interior elements (all elements between the first and last). You need to count how many such subarrays exist in a given array of integers.

Why is this asked in interviews?

This problem is asked at Microsoft and Amazon to test a candidate's ability to manipulate mathematical equations to find efficient solutions. A brute-force $O(N^2)$ solution would be too slow. The problem requires you to rewrite the "stability" condition in a way that allows you to use a Hash Table to count valid pairs in $O(N)$ time.

Algorithmic pattern used

The pattern is Prefix Sum combined with a Hash Table. Let the subarray be from index $i$ to $j$. Boundary sum = $arr[i] + arr[j]$. Interior sum = $\text{TotalSum}(i, j) - (arr[i] + arr[j])$. The condition is $arr[i] + arr[j] = \text{TotalSum}(i, j) - (arr[i] + arr[j])$. This simplifies to $2 \times (arr[i] + arr[j]) = \text{TotalSum}(i, j)$. Using prefix sums $P$, $\text{TotalSum}(i, j) = P[j] - P[i-1]$. So, $2 \times arr[i] + 2 \times arr[j] = P[j] - P[i-1]$, which can be rearranged to $2 \times arr[j] - P[j] = -2 \times arr[i] - P[i-1]$. By storing values of $(-2 \times arr[i] - P[i-1])$ in a hash map as we iterate, we can count matches in one pass.

Example explanation (use your own example)

Array: [1, 2, 3, 1].

• i=0, j=3: Boundary = 1+1=2. Interior = 2+3=5. 2 != 5. Not stable.
• i=0, j=2: Boundary = 1+3=4. Interior = 2. 4 != 2. Not stable. By applying the rearranged formula, we can quickly check all pairs. If we had an array [1, 1, 0, 1, 1], we might find several stable subarrays where the boundaries and interior sums align.

Common mistakes candidates make

• Brute Force: Checking every possible $(i, j)$ pair, which is $O(N^2)$.
• Math errors: Misinterpreting "interior" or failing to correctly rearrange the stability equation.
• Prefix sum indexing: Being off-by-one with prefix sum calculations (e.g., $P[i]$ vs $P[i-1]$).
• Ignoring boundaries: Not considering that a subarray must have at least 2 elements to have an "interior" (though the interior sum could be zero for a 2-element array).

Interview preparation tip

When you see a problem involving subarray sums and a specific condition, try to write out the condition as an equation. Then, move all terms related to the start index $i$ to one side and all terms related to the end index $j$ to the other. This often reveals a Hash Table, Prefix Sum interview pattern.