Lexicographically Largest Permutation After Sorting One Fixed-Length Window
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A logistics team processes shipments in a fixed order before dispatch. The order is given as `shipment_order`, a permutation of the integers `1` to `n`, and you are also given an integer `window_size`.
You must perform the following operation exactly once: choose a contiguous window of exactly `window_size` positions and rearrange the values inside it into ascending order, leaving every other position unchanged.
Return the lexicographically largest array that can result from this operation.
### Function Signature
```python
def maximize_shipment_order(shipment_order: list[int], window_size: int) -> list[int]:
```
### Rules
- Positions are 0-indexed. A window starting at index `i` covers indices `i` through `i + window_size - 1`, so `0 <= i <= n - window_size`.
- The operation is mandatory and is applied exactly once. Choosing a window that is already in ascending order is allowed; it leaves the array unchanged.
- An array `A` is lexicographically larger than an array `B` of the same length if, at the first index where they differ, `A` has the larger value.
- Several windows may produce the same best array. The answer is that array, which is unique.
- Return the full resulting array of length `n`.
### Constraints
- `1 <= window_size <= n <= 2 * 10^5`, where `n = len(shipment_order)`
- `shipment_order` is a permutation of `1, 2, ..., n`, so `1 <= shipment_order[i] <= n` and all values are distinct.
### Examples
**Example 1**
```text
Input: shipment_order = [5, 1, 4, 3, 2], window_size = 3
Output: [5, 1, 3, 4, 2]
```
Sorting the window that starts at index 0 gives `[1, 4, 5, 3, 2]`, at index 1 gives `[5, 1, 3, 4, 2]`, and at index 2 gives `[5, 1, 2, 3, 4]`. The largest of the three is `[5, 1, 3, 4, 2]`.
**Example 2**
```text
Input: shipment_order = [1, 2, 3, 5, 4], window_size = 2
Output: [1, 2, 3, 5, 4]
```
The windows starting at indices 0, 1 and 2 are already sorted and leave the array unchanged. Sorting the window at index 3 gives `[1, 2, 3, 4, 5]`, which is smaller, so choosing an already sorted window is optimal.
**Example 3**
```text
Input: shipment_order = [3, 1, 2], window_size = 3
Output: [1, 2, 3]
```
The only window is the whole array, so the operation must sort it.
Overview: Given a permutation of 1 to n and a window size, sort exactly one contiguous window of that size into ascending order so that the resulting array is lexicographically as large as possible. It tests careful reasoning about lexicographic comparison, a mandatory operation that may leave the array unchanged, and efficiency on inputs of up to 200,000 elements.
Read the full Amazon Software Engineer interview experience this question came from
A logistics team processes shipments in a fixed order before dispatch. You are given `shipment_order`, a permutation of the integers `1` to `n`, and an integer `window_size`.
You must perform the following operation exactly once: choose a contiguous window of exactly `window_size` positions and rearrange the values inside it into ascending order, leaving every other position unchanged.
Return the lexicographically largest array that can result from this operation.
**Rules**
- Positions are 0-indexed. A window starting at index `i` covers indices `i` through `i + window_size - 1`, so `0 <= i <= n - window_size`.
- The operation is mandatory and is applied exactly once. Choosing a window whose values are already in ascending order is allowed; it leaves the array unchanged.
- An array `A` is lexicographically larger than an array `B` of the same length if, at the first index where they differ, `A` has the larger value.
- Several windows may produce the same best array. The answer is that array, which is unique.
- Return the full resulting array of length `n`.
**Constraints**
- `1 <= window_size <= n <= 2 * 10^5`, where `n = len(shipment_order)`
- `shipment_order` is a permutation of `1, 2, ..., n`, so `1 <= shipment_order[i] <= n` and all values are distinct.
No input or output value exceeds `2 * 10^5`, so every value fits in a 32-bit signed integer.
**Example 1**
```
Input: shipment_order = [5, 1, 4, 3, 2], window_size = 3
Output: [5, 1, 3, 4, 2]
```
Sorting the window that starts at index 0 gives `[1, 4, 5, 3, 2]`, at index 1 gives `[5, 1, 3, 4, 2]`, and at index 2 gives `[5, 1, 2, 3, 4]`. The largest of the three is `[5, 1, 3, 4, 2]`.
**Example 2**
```
Input: shipment_order = [1, 2, 3, 5, 4], window_size = 2
Output: [1, 2, 3, 5, 4]
```
The windows starting at indices 0, 1 and 2 are already sorted and leave the array unchanged. Sorting the window at index 3 gives `[1, 2, 3, 4, 5]`, which is smaller, so choosing an already sorted window is optimal.
Constraints
- 1 <= window_size <= n <= 2 * 10^5, where n = len(shipment_order)
- shipment_order is a permutation of 1, 2, ..., n, so 1 <= shipment_order[i] <= n and all values are distinct
Examples
Input: ([1], 1)
Expected Output: [1]
Explanation: Minimum valid input: n = 1 and window_size = 1; the only window is already sorted.
Input: ([2, 1], 2)
Expected Output: [1, 2]
Explanation: window_size = n = 2: the single window must be sorted.
Hints
- Compare an array with the result of sorting one of its windows. Can sorting a window ever make the array lexicographically larger? What does that say when some window is already in ascending order (Example 2)?
- For a window that does change the array, look at the first index where the result differs from the original. How does that index decide which of two windows gives the larger array?
- When two windows first change the array at the same index, compare how much of the array after that index each one rearranges (Example 1).