Largest Lexicographic Array with At-Most K Consecutive Swaps

Largest Lexicographic Array with At-Most K Consecutive Swaps is a classic greedy problem. It teaches a core move: when you can only afford a limited budget of cheap operations, spend each unit on the position that matters most — the leftmost one — and grab the biggest thing within reach.

The slow way first

The brute-force instinct is to try every sequence of up to k swaps and keep the best array. The number of swap sequences explodes combinatorially, so this is hopeless for anything but tiny inputs.

The question to ask: which position should I care about most? Lexicographic order is decided left to right — a bigger value at index 0 beats any improvement further right. So the leftmost position dominates, and we should spend our budget there first.

The idea: greedily fill from the left

Walk the array left to right. At index i, you can reach any element up to k positions away (because it costs one adjacent swap per step to bring it over). Look in that window [i, i + k], find the maximum, and bubble it left into position i with adjacent swaps. Each swap moves it one step and costs one unit of k, so the distance it travels is exactly the budget you spend. Then move on with the reduced k.

The key insight: because earlier positions dominate the ordering, being greedy here is optimal — never save a swap for later when spending it now makes an earlier slot bigger.

Walk through it

Step through the animation. The pointer i marks the slot we are filling and window end marks how far k lets us reach. For [3, 1, 4, 2] with k = 2, the window at index 0 is [3, 1, 4]; the max is 4, two steps away. We bubble it left through two swaps — [3, 4, 1, 2] then [4, 3, 1, 2] — which uses up both swaps, so k hits 0 and we stop.

Pseudocode

n = length of nums
for i from 0 to n - 1:
    if k <= 0: stop                      # budget gone
    end = min(i + k, n - 1)              # furthest reachable index
    best = index of max value in nums[i..end]
    while best > i and k > 0:            # bubble it left
        swap nums[best] and nums[best - 1]
        best = best - 1
        k = k - 1
return nums

The Python solution

def largest_lex(nums, k):
    n = len(nums)
    for i in range(n):
        if k <= 0:
            break
        end = min(i + k, n - 1)
        best = max(range(i, end + 1), key=lambda j: nums[j])
        # bubble nums[best] left into position i
        while best > i and k > 0:
            nums[best], nums[best - 1] = nums[best - 1], nums[best]
            best -= 1
            k -= 1
    return nums

• The outer loop fills positions left to right; we stop early once k runs out.
• end = min(i + k, n - 1) is the furthest index reachable from i within the remaining budget.
• Line 7 picks the index of the maximum value in the window [i, end] — max with a key returns the winning index.
• The inner while bubbles that maximum leftward one adjacent swap at a time, decrementing k on each swap.
• Because lexicographic order is decided by the earliest differing position, spending swaps on the leftmost slot first is always optimal.

Complexity

The work is dominated by scanning each window and bubbling, giving O(n · k) time with only O(1) extra space (we modify the array in place). The greedy choice keeps it simple — no need to explore alternatives.

When this pattern shows up

Practice