Rate limiter counter
Hard
Java
Variables
21 views
Problem Statement
Task: given timestamps in seconds, allow at most limit events in last window seconds. Return allowed count.
Input Format
• First line: Integer n (number of events)
• Second line: n space-separated integers (timestamps in seconds, sorted)
• Third line: Integer limit (maximum allowed events)
• Fourth line: Integer window (window size in seconds)
• Second line: n space-separated integers (timestamps in seconds, sorted)
• Third line: Integer limit (maximum allowed events)
• Fourth line: Integer window (window size in seconds)
Output Format
• Print one integer: number of allowed events
Example
7 1 2 3 5 6 8 9 3 4
123
Constraints
• 1 ≤ n ≤ 10^5
• 0 ≤ timestamps ≤ 10^9
• 1 ≤ limit ≤ 10^5
• 1 ≤ window ≤ 10^9
• Timestamps are sorted in non-decreasing order
• 0 ≤ timestamps ≤ 10^9
• 1 ≤ limit ≤ 10^5
• 1 ≤ window ≤ 10^9
• Timestamps are sorted in non-decreasing order
Concept Explanation
Window = 4 seconds
Limit = 3 events
We allow at most 3 events in the last 4 seconds.
Process events one by one:
• 1 → allowed (count in window = 1)
• 2 → allowed (count = 2)
• 3 → allowed (count = 3)
• 5 → window is [2 to 5], events = 2,3,5 → allowed
• 6 → window is [3 to 6], events = 3,5,6 → allowed
• 8 → window is [5 to 8], events = 5,6,8 → allowed
• 9 → window is [6 to 9], events = 6,8,9 → allowed
Total allowed events = 7
Limit = 3 events
We allow at most 3 events in the last 4 seconds.
Process events one by one:
• 1 → allowed (count in window = 1)
• 2 → allowed (count = 2)
• 3 → allowed (count = 3)
• 5 → window is [2 to 5], events = 2,3,5 → allowed
• 6 → window is [3 to 6], events = 3,5,6 → allowed
• 8 → window is [5 to 8], events = 5,6,8 → allowed
• 9 → window is [6 to 9], events = 6,8,9 → allowed
Total allowed events = 7
Step-by-Step Explanation
1.Read n, timestamps array, limit, and window.
2.Use two pointers: left = 0.
3.Initialize allowedCount = 0.
4.For each event at index right:
• While timestamps[right] - timestamps[left] >= window,
move left forward.
• If (right - left + 1) ≤ limit,
increment allowedCount.
5.After processing all events, print allowedCount.
2.Use two pointers: left = 0.
3.Initialize allowedCount = 0.
4.For each event at index right:
• While timestamps[right] - timestamps[left] >= window,
move left forward.
• If (right - left + 1) ≤ limit,
increment allowedCount.
5.After processing all events, print allowedCount.
Concept Explanation
Window = 4 seconds
Limit = 3 events
We allow at most 3 events in the last 4 seconds.
Process events one by one:
• 1 → allowed (count in window = 1)
• 2 → allowed (count = 2)
• 3 → allowed (count = 3)
• 5 → window is [2 to 5], events = 2,3,5 → allowed
• 6 → window is [3 to 6], events = 3,5,6 → allowed
• 8 → window is [5 to 8], events = 5,6,8 → allowed
• 9 → window is [6 to 9], events = 6,8,9 → allowed
Total allowed events = 7
Limit = 3 events
We allow at most 3 events in the last 4 seconds.
Process events one by one:
• 1 → allowed (count in window = 1)
• 2 → allowed (count = 2)
• 3 → allowed (count = 3)
• 5 → window is [2 to 5], events = 2,3,5 → allowed
• 6 → window is [3 to 6], events = 3,5,6 → allowed
• 8 → window is [5 to 8], events = 5,6,8 → allowed
• 9 → window is [6 to 9], events = 6,8,9 → allowed
Total allowed events = 7
Step-by-Step Explanation
1.Read n, timestamps array, limit, and window.
2.Use two pointers: left = 0.
3.Initialize allowedCount = 0.
4.For each event at index right:
• While timestamps[right] - timestamps[left] >= window,
move left forward.
• If (right - left + 1) ≤ limit,
increment allowedCount.
5.After processing all events, print allowedCount.
2.Use two pointers: left = 0.
3.Initialize allowedCount = 0.
4.For each event at index right:
• While timestamps[right] - timestamps[left] >= window,
move left forward.
• If (right - left + 1) ≤ limit,
increment allowedCount.
5.After processing all events, print allowedCount.
Input / Output Format
Input Format
• First line: Integer n (number of events)
• Second line: n space-separated integers (timestamps in seconds, sorted)
• Third line: Integer limit (maximum allowed events)
• Fourth line: Integer window (window size in seconds)
• Second line: n space-separated integers (timestamps in seconds, sorted)
• Third line: Integer limit (maximum allowed events)
• Fourth line: Integer window (window size in seconds)
Output Format
• Print one integer: number of allowed events
Constraints
• 1 ≤ n ≤ 10^5
• 0 ≤ timestamps ≤ 10^9
• 1 ≤ limit ≤ 10^5
• 1 ≤ window ≤ 10^9
• Timestamps are sorted in non-decreasing order
• 0 ≤ timestamps ≤ 10^9
• 1 ≤ limit ≤ 10^5
• 1 ≤ window ≤ 10^9
• Timestamps are sorted in non-decreasing order
Examples
Input:
7
1 2 3 5 6 8 9
3
4
Output:
123
Example Solution (Public)
static int allowedEvents(int[] t,int window,int limit){int l=0;int ok=0;for(int r=0;r<t.length;r++){while(t[r]-t[l]>=window) l++;int inWindow=r-l+1; if(inWindow<=limit) ok++;}return ok;}
Official Solution Code
static int allowedEvents(int[] t,int window,int limit){int l=0;int ok=0;for(int r=0;r<t.length;r++){while(t[r]-t[l]>=window) l++;int inWindow=r-l+1; if(inWindow<=limit) ok++;}return ok;}
Please login to submit solutions.