How prefix-sum binary search makes text line-breaking O(log n) with zero allocation
typescript
dev.to
Most text layout implementations find line breaks by scanning forward character by character, accumulating widths until they exceed the container. That's O(n) per line and it allocates intermediate results along the way. There's a better approach using prefix sums and binary search. I used it in a text layout engine I built called ZeroText, and the technique is general enough to be useful anywhere you need to partition a sequence by cumulative weight. The naive approach let x = 0