Window Sort Maximize

Medium

Greedy · Amazon

Given a permutation order of the integers 1 to n and an integer w, pick exactly one run of w consecutive positions and sort the values in it into ascending order. Return the lexicographically largest array you can end up with.

Two arrays are compared at the first position where they differ, and the larger value there wins.

Example 1

Input:: order = [3, 1, 4, 2, 5], w = 3
Output:: [3, 1, 2, 4, 5]
Explanation: Sorting the first three values gives [1, 3, 4, 2, 5], which starts lower. Sorting the last three gives [3, 1, 2, 4, 5].

Example 2

Input:: order = [4, 1, 3, 2, 5], w = 2
Output:: [4, 1, 3, 2, 5]
Explanation: The values at positions 1 and 2 are already ascending, so sorting them changes nothing.

Example 3

Input:: order = [5, 4, 3, 2, 1], w = 3
Output:: [5, 4, 1, 2, 3]

Constraints

1 <= n <= 2000
order contains each integer from 1 to n exactly once
1 <= w <= n

Code

Output

Run tests to see results.