Maximum Requests in a Time Window

Problem Statement

You are given an array of request timestamps (integers representing seconds) and a window size w seconds. Return the maximum number of requests that fall within any w-second window.

Example 1:

Input: timestamps = [1, 2, 3, 5, 8, 10], w = 3
Output: 3
Explanation: Window [1, 4] contains requests at 1, 2, 3 (3 requests). 
             Window [3, 6] contains 3, 5 (2). 
             Window [8, 11] contains 8, 10 (2). Max = 3.

Example 2:

Input: timestamps = [4, 1, 1, 2, 3, 9], w = 2
Output: 4
Explanation: After sorting: [1, 1, 2, 3, 4, 9]. Window [1, 3] covers 1, 1, 2, 3 = 4 requests.

Constraints:

• 1 <= timestamps.length <= 10^5.
• Timestamps are non-negative integers, possibly duplicated.
• 1 <= w <= 10^9.
• Clarify with interviewer: is the window inclusive [t, t+w] or exclusive [t, t+w)?

Difficulty: Medium Round: OA

---

Pattern Recognition

• What is the input structure? Possibly unsorted array of timestamps.
• What are we optimizing? Maximum count of timestamps within any contiguous w-length window.
• What pattern does this fit? Sort + variable-size sliding window.
• Why does this pattern fit? Once sorted, you only need to track left and right. As right advances, move left forward while timestamps[right] - timestamps[left] > w. The count in the window is right - left + 1.

---

Approach

Brute Force — For Each Pair

For every pair (i, j), check if |timestamps[j] - timestamps[i]| <= w and track the max window span.

Time: O(n^2). Space: O(1). Why insufficient: For n = 10^5, quadratic is 10^10 ops — TLE.

Optimal — Sort + Two-Pointer Sliding Window

Key Insight: After sorting, a valid window is a contiguous subarray. The left boundary only moves forward as right advances, so both pointers traverse the array once.

Step-by-step:

1. Sort timestamps ascending.
2. Initialize left = 0, best = 0.
3. For right = 0..n-1:
   • While timestamps[right] - timestamps[left] > w: left++.
   • Update best = max(best, right - left + 1).
4. Return best.

Time: O(n log n) for the sort, O(n) for the window pass. Space: O(1) beyond the sort.

---

Walkthrough

Trace on timestamps = [4, 1, 1, 2, 3, 9], w = 2:

After sort: [1, 1, 2, 3, 4, 9].

right	ts[right]	left	ts[left]	diff	action	count	best
0	1	0	1	0	ok	1	1
1	1	0	1	0	ok	2	2
2	2	0	1	1	ok	3	3
3	3	0	1	2	ok	4	4
4	4	0	1	3 > 2 → left = 1
4	4	1	1	3 > 2 → left = 2
4	4	2	2	2	ok	3	4
5	9	2	2	7 > 2 → left = 3, 4, 5
5	9	5	9	0	ok	1	4

Answer: 4 — four requests at times 1, 1, 2, 3 fit in the window [1, 3] of width 2.

---

Implementation

TypeScript

function maxRequestsInWindow(timestamps: number[], w: number): number {
    // Sort ascending; avoid mutating the input if that matters to the caller.
    const ts = [...timestamps].sort((a, b) => a - b);
    let left = 0;
    let best = 0;

    for (let right = 0; right < ts.length; right++) {
        // Shrink from the left while the window exceeds w.
        while (ts[right] - ts[left] > w) left++;
        best = Math.max(best, right - left + 1);
    }
    return best;
}

C++

#include <vector>
#include <algorithm>

int maxRequestsInWindow(std::vector<int> timestamps, int w) {
    std::sort(timestamps.begin(), timestamps.end());
    int left = 0, best = 0;
    for (int right = 0; right < (int)timestamps.size(); right++) {
        while (timestamps[right] - timestamps[left] > w) left++;
        best = std::max(best, right - left + 1);
    }
    return best;
}

Watch out:

1. Inclusive vs exclusive window. If the problem says "within w seconds," usually ts[right] - ts[left] <= w (inclusive). If it says "strictly less than w," use <. Ask before coding.
2. Duplicates at boundary. If two requests happen at the same second, both count — the sliding window handles this naturally because the diff is 0.
3. Mutating the input array. [...arr].sort() in TypeScript avoids this; std::sort in C++ mutates. Mention if it matters.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(1)
Optimal (Sort + Two-Pointer)	O(n log n)	O(1)

Bottleneck: The sort. If timestamps are already sorted or the range is small and bucketable, you can get O(n).

---

Edge Cases

1. Empty array — return 0.
2. Single timestamp — return 1.
3. All timestamps identical — return n. Window diff is always 0.
4. Window w = 0 — only requests at the exact same timestamp count together.
5. Huge w that covers the whole array — return n.
6. Unsorted input — you must sort, not assume.

---

Related Problems

• LC 209 — Minimum Size Subarray Sum — Variable-size window, sum constraint.
• LC 3 — Longest Substring Without Repeating Characters — Same variable-window shape, different admissibility check.
• LC 1438 — Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — Window with a more complex admissibility using a monotonic deque.

---

OA Strategy Notes

Standard OA problem, 10-20 minutes. The only gotcha is confirming the window bounds (inclusive vs exclusive). Write an explicit comment in your code stating your assumption, so the grader can see the intent even if their test cases flip it.

---

What is Expected at Each Level

Junior: Solves the brute force, realizes sort helps, needs a nudge to the two-pointer sliding window.

Mid-level: Goes to sort + two-pointer directly. Clarifies inclusive vs exclusive with the interviewer.

Senior: Notes that if timestamps are bounded integers and n is huge, a counting-array approach is O(n + max_ts) with better constants. Discusses stability under duplicates.