Return Log Entries Within an Inclusive Time Range From a Sorted Log

You are given a log that has already been loaded into memory as a list of entries. Each entry is a pair (timestamp, message), where timestamp is an integer and message is a string. The entries are sorted by timestamp in non-decreasing order, and several entries may share the same timestamp.

Given start_time and end_time, return every entry whose timestamp t satisfies start_time <= t <= end_time.

Function Signature

def logs_in_range(logs: list[tuple[int, str]], start_time: int, end_time: int) -> list[tuple[int, str]]:

Rules

• Both bounds are inclusive.
• Return the matching entries in the same order as they appear in logs. Because logs is sorted, the matching entries form one contiguous run of logs, and that run, in its original order, is the unique correct answer. Entries with equal timestamps keep their input order.
• Return each matching entry unchanged, as the same (timestamp, message) pair. Do not remove duplicates, even if two entries have the same timestamp and the same message.
• If no entry falls in the range, return an empty list. This includes the cases where start_time is greater than the largest timestamp, where end_time is smaller than the smallest timestamp, and where logs is empty.
• Do not modify logs.

Constraints

• 0 <= len(logs) <= 10^5
• 0 <= timestamp <= 10^9 for every entry
• logs[i][0] <= logs[i + 1][0] for every valid i
• 0 <= start_time <= end_time <= 10^9
• Each message is a string of 1 to 100 printable ASCII characters. Messages need not be distinct.
• Every timestamp and bound fits in a 32-bit signed integer.

Examples

Example 1

Input:  logs = [(1, "boot"), (3, "connect"), (3, "retry"), (5, "ready"), (8, "shutdown")]
        start_time = 3, end_time = 5
Output: [(3, "connect"), (3, "retry"), (5, "ready")]

Both entries at timestamp 3 are included, and the entry at 5 is included because the end bound is inclusive.

Example 2

Input:  logs = [(2, "a"), (4, "b"), (6, "c")]
        start_time = 7, end_time = 10
Output: []

start_time is greater than the largest timestamp, 6, so nothing matches.

Example 3

Input:  logs = [(2, "a"), (2, "b"), (4, "c"), (6, "d")]
        start_time = 0, end_time = 2
Output: [(2, "a"), (2, "b")]

The end bound equals the smallest timestamp, so both entries at timestamp 2 match.

Retrieve Log Entries Within an Inclusive Time Window

You are given a log that has already been loaded into memory as a list logs of entries. Each entry is a pair (timestamp, message), where timestamp is an integer and message is a string. The entries are sorted by timestamp in non-decreasing order, and several entries may share the same timestamp.

Given two integers start_time and end_time, return every entry whose timestamp t satisfies start_time <= t <= end_time.

Implement logs_in_range(logs, start_time, end_time).

Rules

• Both bounds are inclusive.
• Return the matching entries in the same order as they appear in logs. Because logs is sorted, the matching entries form one contiguous run of logs, and that run, in its original order, is the unique correct answer. Entries with equal timestamps keep their input order.
• Return each matching entry unchanged, as the same (timestamp, message) pair. Do not remove duplicates, even if two entries have the same timestamp and the same message.
• If no entry falls in the range, return an empty list. This includes the cases where start_time is greater than the largest timestamp, where end_time is smaller than the smallest timestamp, and where logs is empty.
• Do not modify logs.

Entry representation

logs is passed as a single argument, a list of two-element entries, and the result uses the same entry shape:

• Python: a list of (timestamp, message) tuples.
• JavaScript: an array of [timestamp, message] arrays.
• Java: a java.util.List<java.util.List<Object>>; in each entry, element 0 is the timestamp (read it through Number) and element 1 is the String message.
• C++: a std::vector<std::pair<int, std::string>>.

Every timestamp and bound is at most 10^9 and fits in a 32-bit signed integer; no value exceeds 2^31 - 1, so int is sufficient in Java and C++.

Constraints

• 0 <= len(logs) <= 10^5
• 0 <= timestamp <= 10^9 for every entry
• logs[i][0] <= logs[i + 1][0] for every valid i
• 0 <= start_time <= end_time <= 10^9
• Each message is a string of 1 to 100 printable ASCII characters. Messages need not be distinct.
• Every timestamp and bound fits in a 32-bit signed integer.

Examples

Example 1

Input:  logs = [(1, "boot"), (3, "connect"), (3, "retry"), (5, "ready"), (8, "shutdown")]
        start_time = 3, end_time = 5
Output: [(3, "connect"), (3, "retry"), (5, "ready")]

Both entries at timestamp 3 are included, and the entry at 5 is included because the end bound is inclusive.

Example 2

Input:  logs = [(2, "a"), (4, "b"), (6, "c")]
        start_time = 7, end_time = 10
Output: []

start_time is greater than the largest timestamp, 6, so nothing matches.

Hints

1. Because the entries are already sorted by timestamp, all of the matching entries sit next to each other in logs.
2. Several entries can share a timestamp, including timestamps that equal start_time or end_time exactly; both bounds are inclusive, so none of those entries may be dropped.
3. Return the matching entries exactly as they appear: same order, same pairs, duplicates included, and an empty list when nothing matches.

Approach

Because logs is sorted by timestamp in non-decreasing order, the entries with start_time <= t <= end_time form one contiguous block, so it suffices to find the block's two boundaries. The first binary search finds left, the first index whose timestamp is >= start_time; its invariant is that every index before lo has a timestamp < start_time and every index from hi on has a timestamp >= start_time, so when lo == hi it is exactly the boundary. The second binary search finds right, the first index whose timestamp is > end_time, with the analogous invariant. It may start at left because every entry before left has a timestamp < start_time <= end_time, which also guarantees left <= right. Every entry in [left, right) is then >= start_time and <= end_time, and every entry outside it fails one bound, so the slice logs[left:right] is exactly the answer; slicing keeps the original order of equal timestamps and keeps every duplicate untouched, and logs itself is never modified. Edge cases: empty logs gives left = right = 0 and an empty list; a window entirely before the first timestamp, after the last one, or inside a gap gives left == right and an empty list; a bound equal to a timestamp includes every entry with that timestamp because both comparisons are inclusive. A single linear pass that keeps entries inside the window is also correct, in O(n) time.

• Time complexity: O(log n + k), where k is the number of returned entries
• Space complexity: O(k) for the returned list; O(1) extra