3 ms·
> Fulcrum. Given a sequence of integers, returns the index i that minimizes |sum(seq[..i]) - sum(seq[i..])|. Does this in O(n) time and O(n) memory. This is do
by dbkaplun 8y ago
> Fulcrum. Given a sequence of integers, returns the index i that minimizes |sum(seq[..i]) - sum(seq[i..])|. Does this in O(n) time and O(n) memory.
This is doable in O(n) time and O(1) memory. Sum the list once. Then start from the beginning, collecting a running total and subtracting from the sum for a running difference.