Number of Balanced Subsegments

Amazon Web services has n servers lined up in a row. the ith server has the capacity of capacity[i]. Any application can be deployed on a balanced contiguous subsegment of 3 or more servers.

A contiguous segement, [l, r] of servers is said to be balanced if capacity[l] = capacity[r] = sum[capacity[l + 1]…capacity[r - 1]] i.e. the capacity of the servers at the endpoints of the segment should be equal to the sum of the capacity of all the interior servers.

Given the capacity of each server in a row, find the number of balanced subsegements in it.

Constraints 01 1 <= n <= 10 ^ 5 1 <= capacity[i] <= 10 ^ 9 Samples 01 assert(findBalancedSubsegments([9, 3, 3, 3, 9]) == 2) assert(findBalancedSubsegments([9, 3, 1, 2, 3, 9, 10]) == 2) assert(findBalancedSubsegments([6, 1, 2, 3, 6]) == 1)

Here is Python code to find the number of balanced contiguous subsegments in a given array of server capacities:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def findBalancedSubsegments(capacity):

  n = len(capacity)
  count = 0

  for i in range(n-2):
    left_sum = capacity[i]
    right_sum = capacity[i]

    for j in range(i+1, n-1):
      
      right_sum += capacity[j]
      
      if left_sum == right_sum:
        count += 1

  return count 

The key steps are:

1. Consider all subarrays of length >= 3 (outer loop)

2. Sum from left and right endpoints to find interior sum (inner loop)

3. If left and right sums are equal, we have a balanced subsegment

4. Count the number of balanced subsegments

The nested looping structure checks each potential subarray by aggregating left and right sums until a balanced segment is found.

Here is one way to implement an optimized solution to find the number of balanced contiguous subsegments:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def findBalancedSubsegments(capacity):

  n = len(capacity)
  count = 0
  prefix_sum = [0] * (n + 1)

  for i in range(1, n+1):
    prefix_sum[i] = prefix_sum[i-1] + capacity[i-1]

  for i in range(n-2):
    for j in range(i+2, n):
      left_sum = prefix_sum[i+1] - prefix_sum[i]  
      right_sum = prefix_sum[j+1] - prefix_sum[j]

      if left_sum == right_sum:
        count += 1

  return count

The key optimizations are:

• Store prefix sums in an array to enable constant time range queries

• Use the prefix sum array to calculate left and right segment sums in O(1) instead of O(n)

• This reduces the overall runtime from O(n^3) to O(n^2)

• Space complexity is optimized to O(n) using the prefix sum array

By precomputing prefix sums, we can greatly speed up the nested loop implementation while still maintaining overall quadratic time complexity.