Balanced Subarray Sums

January 11, 2024

Problem #

Given an array of integers nums, find the length of the longest subarray where the sum of the first half of the subarray is equal to the sum of the second half of the subarray. If no such subarray exists, return 0.

Example:

Input: nums = [1, 2, 3, 0, 3, 2, 1]
Output: 6  (The subarray [1, 2, 3, 0, 3, 2] has a balanced sum)

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Solution #

Code: #

def longestBalancedSubarray(nums):
    n = len(nums)
    prefix_sum = [0]

    # Create prefix sum array
    for num in nums:
        prefix_sum.append(prefix_sum[-1] + num)

    max_length = 0

    # Check all possible subarrays
    for i in range(n):
        for j in range(i + 2, n + 1, 2):  # Ensure the subarray length is even
            mid = (i + j) // 2
            if prefix_sum[mid] - prefix_sum[i] == prefix_sum[j] - prefix_sum[mid]:
                max_length = max(max_length, j - i)

    return max_length

# Test the function
print(longestBalancedSubarray([1, 2, 3, 2, 1]))  # Expected Output: 4 (subarray [2, 3, 2, 1])
print(longestBalancedSubarray([1, 2, 3, 4, 5]))  # Expected Output: 0 (no such subarray exists)

Explanation: #

1. Function Definition:

   • longestBalancedSubarray(nums) is a function that takes an array of integers, nums, as input.

2. Initialization:

   • n is the length of the array.
   • prefix_sum is an array to store the cumulative sum of elements up to each index in nums. It starts with [0] to simplify calculations.

3. Creating the Prefix Sum Array:

   • The loop for num in nums: calculates the cumulative sum (prefix sum) of the array nums and appends it to prefix_sum.

4. Finding the Longest Balanced Subarray:

   • The nested loops (for i in range(n): for j in range(i + 2, n + 1, 2):) iterate over all possible subarrays of nums. The condition i + 2 ensures that the subarray length is even (as it’s required to be split into two equal halves).
   • mid = (i + j) // 2 finds the middle index of the current subarray.

5. Checking for Balanced Subarray:

   • if prefix_sum[mid] - prefix_sum[i] == prefix_sum[j] - prefix_sum[mid]: checks if the sum of the first half of the subarray (prefix_sum[mid] - prefix_sum[i]) is equal to the sum of the second half (prefix_sum[j] - prefix_sum[mid]).
   • If the condition is true, max_length is updated to the length of the current subarray if it’s longer than the current max_length.

6. Returning the Result:

   • The function returns max_length, the length of the longest balanced subarray found.

Complexity Analysis: #

• Time Complexity: O(n^2), where n is the number of elements in nums. The nested loops contribute to this quadratic time complexity as they consider all possible subarrays.
• Space Complexity: O(n) for storing the prefix_sum array.