Rate Limiter

You are given an array of timestamps representing API requests and need to implement a rate limiter that allows at most limit requests within a windowSize time period. The rate limiter should use a sliding window approach.

Function Signature

function rateLimiter(requests, limit, windowSize) {
  // Your code here
}

Parameters

• requests: An array of integers representing timestamps of API requests
• limit: The maximum number of requests allowed within the window
• windowSize: The time window size in seconds

Return Value

Return an array of indices representing which requests should be allowed (0-indexed).

Examples

The outputs in the question are incorrect, but the explanations are mostly correct. Here are the corrected examples.

---

Example 1

Input

requests = [1, 2, 3, 4, 5]
limit = 3
windowSize = 2

Output

[0, 1, 2, 3, 4]

Explanation

• Request 0 at timestamp 1 → Allowed (queue: [1])

• Request 1 at timestamp 2 → Allowed (queue: [1, 2])

• Request 2 at timestamp 3

  • Remove expired requests (<= 3 - 2 = 1)
  • Remove timestamp 1
  • Queue becomes [2]
  • Allow request (queue: [2, 3])

• Request 3 at timestamp 4

  • Remove expired requests (<= 4 - 2 = 2)
  • Remove timestamp 2
  • Queue becomes [3]
  • Allow request (queue: [3, 4])

• Request 4 at timestamp 5

  • Remove expired requests (<= 5 - 2 = 3)
  • Remove timestamp 3
  • Queue becomes [4]
  • Allow request (queue: [4, 5])

Since the queue size never reaches the limit after removing expired requests, all requests are allowed.

---

Example 2

Input

requests = [1, 2, 3, 4, 5]
limit = 2
windowSize = 3

Output

[0, 1, 3, 4]

Explanation

• Request 0 at timestamp 1 → Allowed (queue: [1])

• Request 1 at timestamp 2 → Allowed (queue: [1, 2])

• Request 2 at timestamp 3

  • Remove expired requests (<= 3 - 3 = 0) → None
  • Queue size is 2 (limit reached)
  • Reject request

• Request 3 at timestamp 4

  • Remove expired requests (<= 4 - 3 = 1)
  • Remove timestamp 1
  • Queue becomes [2]
  • Allow request (queue: [2, 4])

• Request 4 at timestamp 5

  • Remove expired requests (<= 5 - 3 = 2)
  • Remove timestamp 2
  • Queue becomes [4]
  • Allow request (queue: [4, 5])

Constraints

• 0 ≤ requests.length ≤ 1000
• 1 ≤ limit ≤ 100
• 1 ≤ windowSize ≤ 1000
• All timestamps are non-negative integers
• Timestamps are in ascending order

Algorithm

1. Use a queue to maintain the timestamps of allowed requests.
2. For each request timestamp:
   • Remove expired timestamps from the queue (timestamps ≤ currentTime - windowSize).
   • If the queue length is less than the limit, allow the request.
   • Add the current timestamp to the queue if allowed.

Test Cases

• Empty requests array
• Single request
• Multiple requests within a window
• Requests spanning multiple windows
• Edge cases with minimum/maximum values