Largest Rider Group Where Every Rider's Companion-Count Limits Hold
Company: Uber Freight
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A car can take a group of riders on a shared trip. There are `N` riders, and each rider has two limits: rider `i` is willing to share the trip with at least `low[i]` and at most `high[i]` other riders. If `k` riders travel together, each of them shares the trip with exactly `k - 1` others, so every chosen rider must satisfy `low[i] <= k - 1 <= high[i]`.
Return the largest `k` for which some group of `k` riders satisfies every rider in the group. The interviewer required `O(N)` time.
### Function Signature
```python
def max_group_size(low: list[int], high: list[int]) -> int:
```
### Rules
- Any subset of the riders may be chosen. Assume the car has room for all `N` riders, so the only limits are the riders' own.
- Riders who are not chosen impose no condition.
- If no group of one or more riders works, return `0`.
### Constraints
- `1 <= N <= 10^5`, where `N = len(low) == len(high)`
- `0 <= low[i] <= high[i] <= 10^9`
- Required time complexity: `O(N)`.
### Examples
**Example 1**
```text
Input: low = [0, 1, 1, 2, 2]
high = [1, 2, 2, 4, 4]
Output: 3
```
Riders 1, 2, 3 and 4 all accept exactly 2 others, so any three of them can travel together. A group of 4 would need every member to accept 3 others, and a group of 5 would need every member to accept 4 others; in both cases only riders 3 and 4 qualify.
**Example 2**
```text
Input: low = [2, 2, 2, 0]
high = [2, 2, 3, 0]
Output: 3
```
Riders 0, 1 and 2 each travel with exactly 2 others. A group of 4 fails because only rider 2 accepts 3 others. Rider 3 only travels alone, and no group of 2 works even though a group of 3 does.
**Example 3**
```text
Input: low = [1, 2]
high = [1, 3]
Output: 0
```
A single rider would need to accept 0 others, and neither does. A pair fails because rider 1 needs at least 2 others.
Overview: A coding problem about forming the largest group of riders for a shared car, where each rider accepts only a minimum and maximum number of fellow passengers. It tests reasoning about per-rider interval constraints, careful handling of group-size edge cases, and meeting a linear-time requirement.
Read the full Uber Freight Software Engineer interview experience this question came from
A car can take a group of riders on a shared trip. There are `N` riders, and each rider has two limits: rider `i` is willing to share the trip with at least `low[i]` and at most `high[i]` other riders. If `k` riders travel together, each of them shares the trip with exactly `k - 1` others, so every chosen rider must satisfy `low[i] <= k - 1 <= high[i]`.
Implement `max_group_size(low, high)`, which returns the largest `k` for which some group of `k` riders satisfies every rider in the group.
**Rules**
- Any subset of the riders may be chosen. Assume the car has room for all `N` riders, so the only limits are the riders' own.
- Riders who are not chosen impose no condition.
- If no group of one or more riders works, return `0`.
**Constraints**
- `1 <= N <= 10^5`, where `N = len(low) == len(high)`
- `0 <= low[i] <= high[i] <= 10^9`
- Required time complexity: `O(N)`.
- No input value or answer exceeds `2^31 - 1` (the answer lies in `[0, N]`), so 32-bit integers suffice in every language.
**Example 1**
```
Input: low = [0, 1, 1, 2, 2]
high = [1, 2, 2, 4, 4]
Output: 3
```
Riders 1, 2, 3 and 4 (0-indexed) all accept exactly 2 others, so any three of them can travel together. A group of 4 would need every member to accept 3 others, and a group of 5 would need every member to accept 4 others; in both cases only riders 3 and 4 qualify.
**Example 2**
```
Input: low = [2, 2, 2, 0]
high = [2, 2, 3, 0]
Output: 3
```
Riders 0, 1 and 2 each travel with exactly 2 others. A group of 4 fails because only rider 2 accepts 3 others. Rider 3 only travels alone, and no group of 2 works even though a group of 3 does.
Constraints
- 1 <= N <= 10^5, where N = len(low) == len(high)
- 0 <= low[i] <= high[i] <= 10^9
- Required time complexity: O(N)
- The answer is an integer in [0, N]; no input or output value exceeds 2^31 - 1
Examples
Input: ([0, 1, 1, 2, 2], [1, 2, 2, 4, 4])
Expected Output: 3
Explanation: Source Example 1: four riders accept exactly 2 others so k = 3 works; k = 4 and k = 5 fail (a feasible size followed by infeasible larger ones).
Input: ([2, 2, 2, 0], [2, 2, 3, 0])
Expected Output: 3
Explanation: Source Example 2: k = 1 works, k = 2 fails, k = 3 works again, k = 4 fails; feasibility is not monotone in k.
Hints
- Fix a group size k. Does it matter which riders you pick, or only how many riders accept exactly k - 1 others?
- Feasibility does not have to grow or shrink steadily with k: Example 2 has a working size of 3 while size 2 fails, so consider every size.
- Only k - 1 values from 0 to N - 1 can ever occur, so a rider's acceptable range can be clipped to that interval before you use it.