Debounce With Max Wait

hardcodingJavaScriptTimingState Machines~55 min

Asked at Google, Meta, Stripe

Overview

Standard debounce delays execution until a quiet period elapses. In real-world scenarios (scroll handlers, search-as-you-type), this can starve the callback indefinitely during sustained activity. The maxWait option guarantees the function fires at least once every maxWait milliseconds, even if calls keep arriving.

Given a stream of timestamped invocations and a configuration object, implement debounceMaxWait(events, wait, maxWait) that computes the exact timestamps at which the debounced function would fire.

Constraints

Input events are sorted in ascending order.
wait and maxWait are positive integers in milliseconds.
maxWait >= wait is always true.
Output timestamps must be in ascending order with no duplicates.
Only trailing-edge fires (no leading option for this problem).
Complexity target: $O(n)$.

Examples

// maxWait forces mid-burst fire.
debounceMaxWait([0, 50, 120, 180, 250, 500], 100, 200);
// → [200, 350, 600]
// Events 0–180 keep resetting the debounce timer. But maxWait: 200 forces
// a fire at t=200 (200ms after first call at t=0). Window resets.
// Event at 250: gap from 180 is 70 < wait, but elapsed from 200 is 50 < maxWait.
// Gap 250→500 exceeds wait so trailing fires at 350. Event 500 → trailing at 600.

// Natural gaps — maxWait never triggers.
debounceMaxWait([0, 250, 500], 100, 300);
// → [100, 350, 600]
// Each event spaced > wait, so each fires trailing normally.
// maxWait never kicks in because no window lasts > 300ms.

// Continuous rapid fire with periodic maxWait fires.
debounceMaxWait([0, 30, 60, 90, 130, 160, 190, 220, 400], 50, 120);
// → [120, 250, 450]
// Continuous calls 0–220 trigger maxWait at 120 and 250. Gap to 400 > 50 so trailing at 250.
// Event 400 starts new window with trailing at 450.

Notes

The first event in a window starts both the debounce timer (wait) and the maxWait timer.
When maxWait forces a fire, it closes the current window and the next event starts a new window.
A trailing edge fires at lastEventInWindow + wait unless maxWait fires first.
The fire time is always Math.min(lastEvent + wait, windowStart + maxWait).

Solution

Reveal solution

Resources

debounce-with-max-wait.js

Debounce With Max Wait

hardcodingJavaScriptTiming

Overview

Standard debounce delays execution until a quiet period elapses. In real-world scenarios (scroll handlers, search-as-you-type), this can starve the callback indefinitely during sustained activity. The maxWait option guarantees the function fires at least once every maxWait milliseconds, even if calls keep arriving.

Given a stream of timestamped invocations and a configuration object, implement debounceMaxWait(events, wait, maxWait) that computes the exact timestamps at which the debounced function would fire.

Constraints

Input events are sorted in ascending order.
wait and maxWait are positive integers in milliseconds.
maxWait >= wait is always true.
Output timestamps must be in ascending order with no duplicates.
Only trailing-edge fires (no leading option for this problem).
Complexity target: $O(n)$.

Examples

// maxWait forces mid-burst fire.
debounceMaxWait([0, 50, 120, 180, 250, 500], 100, 200);
// → [200, 350, 600]
// Events 0–180 keep resetting the debounce timer. But maxWait: 200 forces
// a fire at t=200 (200ms after first call at t=0). Window resets.
// Event at 250: gap from 180 is 70 < wait, but elapsed from 200 is 50 < maxWait.
// Gap 250→500 exceeds wait so trailing fires at 350. Event 500 → trailing at 600.

// Natural gaps — maxWait never triggers.
debounceMaxWait([0, 250, 500], 100, 300);
// → [100, 350, 600]
// Each event spaced > wait, so each fires trailing normally.
// maxWait never kicks in because no window lasts > 300ms.

// Continuous rapid fire with periodic maxWait fires.
debounceMaxWait([0, 30, 60, 90, 130, 160, 190, 220, 400], 50, 120);
// → [120, 250, 450]
// Continuous calls 0–220 trigger maxWait at 120 and 250. Gap to 400 > 50 so trailing at 250.
// Event 400 starts new window with trailing at 450.

Notes

The first event in a window starts both the debounce timer (wait) and the maxWait timer.
When maxWait forces a fire, it closes the current window and the next event starts a new window.
A trailing edge fires at lastEventInWindow + wait unless maxWait fires first.
The fire time is always Math.min(lastEvent + wait, windowStart + maxWait).

Solution

Reveal solution

Resources

NameTopicDifficulty

Add BinaryAlgorithmseasy Balanced Binary TreeAlgorithmseasy Balanced BracketsAlgorithmseasy Binary SearchAlgorithmseasy Binary Search Tree Lowest Common AncestorAlgorithmseasy Binary Tree Maximum DepthAlgorithmseasy Binary Tree SubtreeAlgorithmseasy Bit CountingAlgorithmseasy Bit ReversalAlgorithmseasy Count Set Bits in a Binary NumberAlgorithmseasy Diameter of Binary TreeAlgorithmseasy Find Duplicates in ArrayAlgorithmseasy First Bad VersionAlgorithmseasy Flip Binary TreeAlgorithmseasy Flood FillAlgorithmseasy Linked List Detect CycleAlgorithmseasy Linked List ReversalAlgorithmseasy Linked Lists Combine Two SortedAlgorithmseasy Longest PalindromeAlgorithmseasy Middle of the Linked ListAlgorithmseasy Most Common ElementsAlgorithmseasy Optimal Stock TradingAlgorithmseasy Pair SumAlgorithmseasy Ransom NoteAlgorithmseasy Staircase Climbing CombinationsAlgorithmseasy String AnagramAlgorithmseasy String PalindromeAlgorithmseasy 01 MatrixAlgorithmsmedium Accounts MergeAlgorithmsmedium Array Product Excluding CurrentAlgorithmsmedium Binary Search Tree Kth Smallest ElementAlgorithmsmedium Binary Tree Level Order TraversalAlgorithmsmedium Binary Tree Rebuilding from Preorder and Inorder TraversalsAlgorithmsmedium Binary Tree Right Side ViewAlgorithmsmedium Combinations for Target SumAlgorithmsmedium Count Islands in a GridAlgorithmsmedium Course DependencyAlgorithmsmedium Decode MessageAlgorithmsmedium Disjoint IntervalsAlgorithmsmedium Distinct Paths in GridAlgorithmsmedium Evaluate Reverse Polish NotationAlgorithmsmedium Find All Anagrams in a StringAlgorithmsmedium Find Element in Rotated ArrayAlgorithmsmedium Find the Longest Palindromic SubstringAlgorithmsmedium Find Word in GridAlgorithmsmedium Graph CloneAlgorithmsmedium Graph Count Connected ComponentsAlgorithmsmedium Is the Graph a TreeAlgorithmsmedium K Closest Points to OriginAlgorithmsmedium Letter Combinations of a Phone NumberAlgorithmsmedium Longest Increasing SubsequenceAlgorithmsmedium Longest Non-repeating SubstringAlgorithmsmedium Longest Repeating Substring After ReplacementsAlgorithmsmedium Lowest Common Ancestor of a Binary TreeAlgorithmsmedium Matrix RotationAlgorithmsmedium Matrix Spiral TraversalAlgorithmsmedium Matrix ZeroingAlgorithmsmedium Maximum Sum in Contiguous ArrayAlgorithmsmedium Maximum Water Trapped Between WallsAlgorithmsmedium Merge New IntervalAlgorithmsmedium Merge Overlapping IntervalsAlgorithmsmedium Minimum Coins for ChangeAlgorithmsmedium Minimum Height TreesAlgorithmsmedium Palindromic SubstringsAlgorithmsmedium Partition Equal Subset SumAlgorithmsmedium PermutationsAlgorithmsmedium Rotting OrangesAlgorithmsmedium Segment WordsAlgorithmsmedium Sort ColorsAlgorithmsmedium String Anagram GroupsAlgorithmsmedium String to Integer (atoi)Algorithmsmedium SubsetsAlgorithmsmedium Sum Without AdditionAlgorithmsmedium Task CoordinationAlgorithmsmedium Trie (Prefix Tree)Algorithmsmedium Triplet SumAlgorithmsmedium Validate Binary Search TreeAlgorithmsmedium Basic CalculatorAlgorithmshard Binary Tree EqualAlgorithmshard Binary Tree Maximum Total PathAlgorithmshard Delete Nth Node from End of Linked ListAlgorithmshard End of Array ReachableAlgorithmshard Extraterrestrial LanguageAlgorithmshard Find Missing Number in SequenceAlgorithmshard Find Words in GridAlgorithmshard Largest Rectangle in HistogramAlgorithmshard Linked Lists Combine K SortedAlgorithmshard Longest Common SubsequenceAlgorithmshard Longest Consecutive Number SequenceAlgorithmshard Maximum Product in Contiguous ArrayAlgorithmshard Maximum Profit in Job SchedulingAlgorithmshard Meeting CalendarAlgorithmshard Minimum Meeting Rooms NeededAlgorithmshard Neighborhood TheftAlgorithmshard Neighborhood Theft (Circular)Algorithmshard Number Stream MedianAlgorithmshard Ocean FlowAlgorithmshard Rearrange Linked ListAlgorithmshard Shortest Substring Containing CharactersAlgorithmshard Smallest Element in Rotated Sorted ArrayAlgorithmshard Trapping Rain WaterAlgorithmshard Word FinderAlgorithmshard Word LadderAlgorithmshard

103 of 103 problems