Problem Description
Given a 0-indexed integer array nums, find the leftmost middleIndex where the sum of the numbers to the left of middleIndex equals the sum of the numbers to the right. If no such index exists, return -1.
Key Insights
- Use the total sum of the array to avoid recalculating sums for every index.
- Maintain a running left sum while iterating through the array.
- For each index, compute the right sum as (total sum - left sum - current number).
- Check if left sum equals the computed right sum to determine if the current index is the middle index.
- Edge cases: at index 0, left sum is 0; at the last index, right sum is 0.
Space and Time Complexity
Time Complexity: O(n) Space Complexity: O(1)
Solution
The algorithm first computes the total sum of the array. Then, it iterates through the array, updating a running left sum. For each element at index i, the right sum is calculated by subtracting the left sum and the current element from the total sum. If the left sum equals the right sum, index i is returned as the valid middle index. If no such index exists, the function returns -1. This approach ensures that each element is processed only once, leading to an efficient O(n) solution with constant extra space.