Good Indices in a Digit String - Solution & Explanation

Problem Overview: You are given a string of digits. An index is considered good if the sum of digits on its left equals the sum of digits on its right. The task is to scan the string and return all indices that satisfy this balance condition.

Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)

Check every index independently. For each position i, iterate over the substring [0..i-1] to compute the left digit sum and over [i+1..n-1] to compute the right digit sum. If the two sums match, record the index as good. This approach uses plain iteration and no extra data structures, but it recomputes the same sums repeatedly, leading to quadratic time for long strings.

Approach 2: Prefix Sum Simulation (O(n) time, O(1) space)

Precompute the total sum of all digits. While iterating through the string, maintain a running leftSum. For index i, compute the right side using rightSum = totalSum - leftSum - digit[i]. If leftSum == rightSum, the index is good. After the check, update leftSum += digit[i]. This eliminates repeated summation and reduces the complexity to linear time. The technique is a standard optimization when dealing with cumulative values in math and string problems.

The key insight is that you never need to recompute sums for each side of the index. Maintaining a running prefix value and deriving the suffix value from the total keeps the algorithm efficient and easy to implement.

Recommended for interviews: The prefix-sum simulation is the expected solution. Starting with the brute force method shows you understand the definition of a good index. Transitioning to the prefix-based optimization demonstrates awareness of common mathematical accumulation patterns and how to reduce repeated work from O(n^2) to O(n).