Tejav
#3728

Stable Subarrays With Equal Boundary and Interior Sum

Medium
ArrayHash TablePrefix SumHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

Utilize prefix sums to efficiently compute the sum of subarrays and a hashmap to track indices of elements for quick access.

⚙️

Algorithm

3 steps
  1. 1Step 1: Create a prefix sum array to store cumulative sums.
  2. 2Step 2: Use a hashmap to store the last seen index of each element.
  3. 3Step 3: For each element, check if it can form a stable subarray with previously seen elements using the prefix sum condition.
solution.py14 lines
1def stableSubarrays(capacity):
2    n = len(capacity)
3    prefix_sum = [0] * (n + 1)
4    for i in range(n):
5        prefix_sum[i + 1] = prefix_sum[i] + capacity[i]
6    count = 0
7    last_seen = {}
8    for r in range(n):
9        if r >= 2:
10            l = last_seen.get(capacity[r], -1)
11            if l != -1 and prefix_sum[r] - prefix_sum[l + 1] == capacity[l]:
12                count += 1
13        last_seen[capacity[r]] = r
14    return count
ℹ

Complexity note: Single pass through the array with hashmap and prefix sums leads to linear time complexity.

  • 1Stable subarrays require matching boundaries and correct interior sums.
  • 2Prefix sums allow for efficient sum calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.