--- title: Two-Stack Sliding-Window Aggregation | daily.dev description: An algorithm for maintaining a running aggregate over a sliding window using two stacks is explained, offering amortized O(1) performance for any associative... canonical: https://daily.dev/posts/two-stack-sliding-window-aggregation-4i5ga0thx twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: Two-Stack Sliding-Window Aggregation | daily.dev og:description: An algorithm for maintaining a running aggregate over a sliding window using two stacks is explained, offering amortized O(1) performance for any associative... og:url: https://daily.dev/posts/two-stack-sliding-window-aggregation-4i5ga0thx og:image: https://api.daily.dev/og/posts/4I5gA0thx.png og:image:alt: Two-Stack Sliding-Window Aggregation og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # Two-Stack Sliding-Window Aggregation **[Lobsters](https://daily.dev/sources/lobsters)** · 7 min read · 0 upvotes · 0 comments ## Summary An algorithm for maintaining a running aggregate over a sliding window using two stacks is explained, offering amortized O(1) performance for any associative combine operation, not just invertible ones like sums. The technique generalizes to minimum, quantiles, approximate unique counts (HyperLogLog), and more by abstracting aggregation into empty, unit, combine, and finalize functions. The author traces the algorithm's folklore origins to a 2011 Stack Overflow post crediting a 2001 lecture on amortized two-stack FIFO queues, walks through a worked example summing a window of four elements, and explains why the approach also mitigates floating-point error accumulation since each aggregate only ever combines values currently inside the window. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### How can I compute a sliding window minimum or maximum efficiently without an invertible operator? A two-stack algorithm achieves amortized O(1) time per push and pop for any associative aggregation, including minimum, maximum, quantiles, and approximate unique counts, without requiring an inverse operation. It works by maintaining two stacks: one holding incoming values with their combined aggregate, and another holding cumulative aggregates of older values in reverse order, draining and rebuilding only every w operations. _Readers building streaming analytics features track algorithm deep dives like this on daily.dev._ ### Why does a naive rolling sum produce wrong results when large and small floating-point values enter and leave the window? Naive rolling sums accumulate error because subtracting a value that left the window does not undo its floating-point addition exactly; for example, 1e20 + 1 - 1e20 - 1 evaluates to -1.0 instead of 0. A two-stack aggregation approach avoids this since each window's aggregate is recomputed strictly from elements currently inside it, so outliers like NaN or infinity only poison windows containing them rather than propagating indefinitely. _Developers debugging numerical drift in streaming sums can revisit aggregation patterns like this via daily.dev._ ## Similar posts on daily.dev - [Medium](https://daily.dev/posts/medium-tjownsknq) · Medium · 0 upvotes · 0 comments - [Rate Limiting Algorithms: Token Bucket vs Sliding Window vs Fixed Window](https://daily.dev/posts/rate-limiting-algorithms-token-bucket-vs-sliding-window-vs-fixed-window-c6i3q4jdl) · Arcjet · 0 upvotes · 0 comments - [Sliding-Window Rate Limiters with TypeScript & Redis](https://daily.dev/posts/sliding-window-rate-limiters-with-typescript-redis-johtnq4x1) · SitePoint · 0 upvotes · 0 comments - [Managing Small Context Windows in Language Models](https://daily.dev/posts/managing-small-context-windows-in-language-models-n3u1axvbz) · Machine Learning Mastery · 1 upvotes · 0 comments --- Tags: [#algorithms](https://daily.dev/tags/algorithms), [#data-structures](https://daily.dev/tags/data-structures) [View this post on daily.dev](https://daily.dev/posts/two-stack-sliding-window-aggregation-4i5ga0thx) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"Two-Stack Sliding-Window Aggregation","url":"https://daily.dev/posts/two-stack-sliding-window-aggregation-4i5ga0thx","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/two-stack-sliding-window-aggregation-4i5ga0thx"},"datePublished":"2026-10-04T06:46:49.413Z","dateModified":"2026-10-04T06:47:11.129Z","description":"An algorithm for maintaining a running aggregate over a sliding window using two stacks is explained, offering amortized O(1) performance for any associative...","image":"https://media.daily.dev/image/upload/s--VDukGCjf--/f_auto/v1722860399/public/Placeholder%2002","thumbnailUrl":"https://media.daily.dev/image/upload/s--VDukGCjf--/f_auto/v1722860399/public/Placeholder%2002","isAccessibleForFree":true,"articleSection":"Lobsters","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Lobsters","logo":"https://media.daily.dev/image/upload/s--tl8v_Fku--/f_auto,t_logo/v1698841318/logos/lobste.jpg","url":"https://daily.dev/sources/lobsters"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/two-stack-sliding-window-aggregation-4i5ga0thx","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"algorithms,data-structures","timeRequired":"PT7M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Lobsters","item":"https://daily.dev/sources/lobsters"},{"@type":"ListItem","position":3,"name":"Two-Stack Sliding-Window Aggregation"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/two-stack-sliding-window-aggregation-4i5ga0thx#faq","mainEntity":[{"@type":"Question","name":"How can I compute a sliding window minimum or maximum efficiently without an invertible operator?","acceptedAnswer":{"@type":"Answer","text":"A two-stack algorithm achieves amortized O(1) time per push and pop for any associative aggregation, including minimum, maximum, quantiles, and approximate unique counts, without requiring an inverse operation. It works by maintaining two stacks: one holding incoming values with their combined aggregate, and another holding cumulative aggregates of older values in reverse order, draining and rebuilding only every w operations. Readers building streaming analytics features track algorithm deep dives like this on daily.dev."}},{"@type":"Question","name":"Why does a naive rolling sum produce wrong results when large and small floating-point values enter and leave the window?","acceptedAnswer":{"@type":"Answer","text":"Naive rolling sums accumulate error because subtracting a value that left the window does not undo its floating-point addition exactly; for example, 1e20 + 1 - 1e20 - 1 evaluates to -1.0 instead of 0. A two-stack aggregation approach avoids this since each window's aggregate is recomputed strictly from elements currently inside it, so outliers like NaN or infinity only poison windows containing them rather than propagating indefinitely. Developers debugging numerical drift in streaming sums can revisit aggregation patterns like this via daily.dev."}}]} ```