Problem

At Stripe, you need an in-memory rate limiter that decides whether each request should be allowed.

Implement rate_limit(timestamps, limit, window_seconds) that returns a boolean decision for every request timestamp.

Specification

• Input:
  • timestamps: list[int] (non-decreasing)
  • limit: int maximum number of allowed requests in any window
  • window_seconds: int window size in seconds
• Window rule: for a request at time t, consider the inclusive window [t - window_seconds, t].
• Counting rule: only allowed requests count toward the limit.
• Output: list[bool] where True means allow, False means deny.

Examples

1. timestamps = [1, 1, 1, 2], limit = 3, window_seconds = 1 → [True, True, True, False]

• At t=2, window is [1,2] and already contains 3 allowed requests at time 1, so deny.

2. timestamps = [1, 2, 3, 4], limit = 2, window_seconds = 3 → [True, True, False, True]

• At t=3, window [0,3] has 2 allowed (1,2) so deny; at t=4, window [1,4] has only one allowed (2), so allow.

Constraints

• 0 <= len(timestamps) <= 2 * 10^5
• 0 <= timestamps[i] <= 10^9
• 1 <= limit <= 10^5
• 1 <= window_seconds <= 10^9
• timestamps is non-decreasing