LeetCode: 3862. Find the Smallest Balanced Index

Summary

Return an integer denoting the smallest balanced index. If no balanced index exists, return -1.

Definition: An index i is balanced if the sum of elements strictly to the left of i equals the product of elements strictly to the right of i.

Rules:

If there are no elements to the left, the sum is considered as 0.
Similarly, if there are no elements to the right, the product is considered as 1.

Approach

My first approach used DP to store all left sums and right products.

However, this approach failed with a memory-limit exceeded error (O(N) memory).

After that, I found another way with O(1) memory.

The new approach uses two pointers.

We track pointers from both sides while maintaining the left sum and right product. If the condition is balanced, return the answer; otherwise, move one pointer.

Function

Initialization:

left = -1, right = len(nums)
left_sum = 0
right_product = 1

While left < right: if left_sum < right_product, move left to the next index and add nums[left] to left_sum. elif left_sum > right_product, move right to the previous index and multiply right_product by nums[right]. else: if left + 1 == right, we found the balanced index. otherwise, move right to the previous index because we want to find the minimum index.

If not found, return -1.

Complexity

Time Complexity: O(N) where N is the size of nums. The two pointers traverse nums once. Space Complexity: O(1).