Prefix sums for counting subarrays with a target sum
Count contiguous ranges with a given sum in one C# pass. Follow a signed ledger to see why duplicate prefixes, lookup order and 64-bit counts matter.
A ledger records six balance changes, [2, -2, 3, 0, -3, 3]. How many contiguous runs of transactions increased the balance by exactly 3? There are seven. Three different runs end at the very last transaction, including that single final 3. A running balance can tell you how much has changed since the beginning. To count all the possible beginnings of a run, you also need to know how many times the ledger visited a particular balance.
This is a counting problem. Returning one matching pair of endpoints would miss most of the answer. Trying all possible pairs on a day with 200,000 transactions would mean examining 20,000,100,000 nonempty intervals. There is a way to count all the matches for each end position in a single lookup.
Call the balance immediately before transaction i the prefix sum P[i]. Start at P[0] = 0 and add each transaction to get the next balance. With six transactions there are seven balances, including the closing one. The amount gained from boundary a up to boundary b is P[b] - P[a]. The transaction at index a is included and the one at index b is excluded.
boundary 0 1 2 3 4 5 6
balance 0 2 0 3 3 0 3
change +2 -2 +3 0 -3 +3At closing time P[6] is 3. A gain of 3 therefore requires a starting balance of 0. The ledger shows three eligible starts, at boundaries 0, 2 and 5. The corresponding runs are the full ledger, the last four transactions and the last transaction. Two starts can have the same balance and still describe entirely different transaction ranges. That is the reason for keeping counts of balances.
-
End at boundary 3
- 0
- 2
- 0
Closing balance 3. Two earlier zeros give two runs.
-
End at boundary 4
- 0
- 2
- 0
- 3
The zero transaction leaves the closing balance at 3. Both starts work again with this new end.
-
End at boundary 6
- 0
- 2
- 0
- 3
- 3
- 0
A third zero is available. Three more runs bring the total to seven.
The other boundaries contribute zero. At boundary 1 the balance is 2, so you would need an earlier balance of -1. At boundaries 2 and 5 the balance is zero, which would require an earlier -3. Neither starting balance occurred. With a target of 3, every answer ends at one of boundaries 3, 4 or 6, so the three rows above account for all seven runs.
Rearranging the range equation gives P[a] = P[b] - target. At boundary b, look up that amount in a dictionary of previously seen balances. The value stored there tells you exactly how many qualifying ranges end at b. Then record the balance at b so the next transaction can use it as a starting point.
static long CountNetChanges(int[] changes, int target)
{
var frequency = new Dictionary<long, long> { [0] = 1 };
long balance = 0;
long matches = 0;
foreach (int change in changes)
{
balance += change;
matches += frequency.GetValueOrDefault(balance - target);
frequency[balance] = frequency.GetValueOrDefault(balance) + 1;
}
return matches;
}Just before the lookup for boundary b, the dictionary describes boundaries 0 through b - 1. That one-step gap ensures every counted range contains at least one transaction.
Two implementation details come directly from that statement. First, the dictionary starts with one visit to balance zero. Without it, an array containing just [3] would return zero for target 3. The single transaction begins at the initial boundary. Second, recording the balance before the lookup would let every boundary pair with itself for target zero. With one change of 5, that implementation claims one zero-sum transaction range even though the ledger never stood still for an entire transaction.
A set of previously seen balances would answer an existence question. It would return one hit for the last boundary in the example, losing the other two eligible starts. If you want the longest matching run ending here, store the earliest index for each balance. It gives the greatest distance to the current end. What you keep under the key follows directly from what the caller wants to know about the matching starts.
The dictionary needs at most one key per distinct balance, at most n + 1 for n transactions. That worst case occurs with a strictly increasing balance. The count takes expected O(n) time with hash-table lookups and O(n) auxiliary space in the worst case. It requires only one forward read of each transaction. You can consume a sequence as it arrives provided you can keep all distinct balances observed so far. Dictionary lookup characteristics
The balance may need more bits than an individual change. Take [int.MaxValue, int.MaxValue, 2] with a target of zero. All changes are positive, so there is no nonempty zero-sum run. The closing balance is 4,294,967,296. Under unchecked 32-bit arithmetic that becomes zero and collides with the initial balance. The algorithm would report a match for the entire ledger. A 64-bit balance keeps those boundaries distinct.
The number of matches can overflow even if every single balance is zero. For 100,000 zero-valued transactions and target zero, the first end has one eligible start, the next has two and the last has 100,000. Their total is 100000 * 100001 / 2 = 5,000,050,000, which exceeds a signed 32-bit count. The length alone gives the expected value for this test case. An empty array also tests something different. It has one initial boundary, never performs a lookup and returns zero for every target. C# integer ranges
For more varied checks on a small array, start a fresh total at every index and extend it one element at a time. With six transactions that is only 21 additions. Comparing the dictionary count with those 21 direct decisions gives you a second way to verify negative targets, zeros between matches and intervals ending at the very last element. A shrinking sum window can lose an answer here. Even if the total exceeds the target, a subsequent negative transaction can bring it back. Sliding windows with fixed and variable sizes
Suppose a reconciliation report asks how many runs have a net change divisible by 5. Now a difference of 0, 5, 10 or even -5 is acceptable. Two balances differ by a multiple of 5 exactly when they have the same remainder modulo 5. Use the same lookup-before-insert loop with the normalized remainder as the key. The number of possible keys drops to at most five, however long the ledger grows.
For example, changes of [-2, 5] produce balances 0, -2 and 3. Balances -2 and 3 belong to the same residue class, giving a single match consisting of the second transaction. In C#, the remainder operator gives -2 % 5 == -2 and 3 % 5 == 3. Use a positive divisor and add it back to a negative remainder before the lookup. Doing so maps both balances to the same key, 3. C# remainder operator
The Subarray Sum Equals K exercise uses a signed input and a 64-bit count. Its companion, Subarrays Divisible by K, gives you a way to test which parts of your implementation survive a change in the matching rule. Run both on a string of zeros before trying a mixed-sign case. C# coding challenges · How algorithm submissions are graded
Practice what you just read
- Open in the editor: Subarray Sum Equals K
Algorithm Medium Free, no account needed
Subarray Sum Equals K
Count contiguous subarrays whose elements sum to a target k.
- Open in the editor: Subarrays Divisible by K
Algorithm Medium Free, no account needed
Subarrays Divisible by K
Count the subarrays whose sum is divisible by k.
More like this: C# coding challenges →