Loading…

easyGreedySometimes asked

Largest Permutation

Q: How do you solve Largest Permutation using the Brute Force — Search All Reachable Permutations approach?

When to use it: Mention to frame the search space, then collapse with the greedy observation. Define the search space as all permutations reachable with at most `k` swaps from the input. Explore it (DFS/BFS), comparing each reachable permutation and keeping the lexicographically largest. **Why it's correct.** Every sequence achievable within the budget is generated, so the maximum among them is the answer. **Why it's hopeless.** Each step can swap any pair — about `n²/2` choices — and we may take up to `k` steps, giving an exponential `(n²/2)^k` tree. For the given constraints this is impossible. **The structure it reveals.** Compare any two reachable permutations: whichever has a larger value at the *first differing position* wins, regardless of everything after. So spending a swap to raise an earlier position always beats spending it later. That single fact says: process positions left to right, and at each one place the largest value you can — no search needed. Time complexity: O(n^(2k) · ...). Space complexity: O(branching).

Q: How do you solve Largest Permutation using the Greedy — Place Largest Value Leftmost with a Value→Index Map (Optimal) approach?

When to use it: The answer they want. Phrase it as 'put n at the front, then n−1, … each costing one swap, until the budget is gone'. The lexicographically largest arrangement of `1..n` is the descending sequence `n, n−1, …, 1`. So at position `i` (0-indexed) the ideal value is `n − i`. Walk positions left to right; at each one, if the ideal value isn't already there, swap it in from its current location and spend one swap. Stop when `k` reaches 0. **Why most-significant-position-first is optimal — the exchange argument.** Lexicographic order is decided at the *first* position where two sequences differ. Suppose an optimal solution does NOT place the largest available value at the leftmost still-improvable position `i`, but instead uses a swap to improve some later position `j > i`. Re-route that one swap to instead place `n − i` at position `i`. The new sequence is larger at position `i` than the optimal was (it now holds the max possible value there), and positions `0..i−1` are unchanged — so it is lexicographically ≥ the supposed optimum, using no more swaps. Hence there's always an optimal solution that fixes the leftmost improvable position first; induction gives the full greedy. **Why a value→index map.** To place `n − i` we must know *where* it currently sits. A map keyed by value gives that in O(1). The naive alternative — scanning for it — is O(n) per position and O(n·k) overall, which is too slow. **Why we update the map after each swap.** Swapping `arr[i]` and `arr[j]` moves two values. The value `n − i` now lives at `i`, and the value previously at `i` now lives at `j`. Both map entries must be corrected, or a later lookup will point at a stale index and corrupt the result. **Why skipping correct positions matters.** If `arr[i]` already equals `n − i`, fixing it would 'cost' a wasted self-swap. We skip it for free, preserving budget for positions that actually need it. Time complexity: O(n). Space complexity: O(n).

Greedy Algorithms · 20 of 23 · 9 min

You are given a permutation of the integers 1 to n and a number k. You may perform at most `k` swaps of any two elements.

Return the lexicographically largest permutation obtainable with at most k swaps.

In plain English

Lexicographically largest means the first position should be as large as possible, then the second, and so on. Since the values are exactly 1..n, the ideal sequence is n, n−1, n−2, …. Each position we fix to its ideal value costs one swap (unless it's already correct). With only k swaps, we fix the k most significant out-of-place positions, left to right.

Examples

Example 1

Input: arr = [4, 2, 3, 5, 1], k = 1
Output: [5, 2, 3, 4, 1]
Note: Largest value 5 belongs at position 0. It's at index 3; swap arr[0]↔arr[3] → [5,2,3,4,1]. k is now 0, so stop.

Example 2

Input: arr = [2, 1, 3], k = 1
Output: [3, 1, 2]
Note: Position 0 wants 3 (currently 2). 3 is at index 2; swap → [3,1,2]. Budget exhausted.

Example 3

Input: arr = [2, 1, 3], k = 0
Output: [2, 1, 3]
Note: No swaps allowed — return the array unchanged.

Constraints

1 ≤ n ≤ 100000
1 ≤ k ≤ 10⁹ (effectively capped at n − 1 useful swaps)
The input is a permutation of 1..n (each value 1..n appears exactly once)

Clarifying questions4First question: Are swaps limited to adjacent elements?Explore questions

Q1.Are swaps limited to adjacent elements?
No — any two positions can be swapped. That's why one swap can place the global maximum directly at position 0.
Q2.Is the input guaranteed to be a permutation of 1..n?
Yes. That's what makes the target at position i exactly n − i (0-indexed), with no duplicates or gaps.
Q3.Do we use exactly k swaps or at most k?
At most k. If the array is already largest, or becomes largest before k runs out, we stop early — wasting a swap can only hurt.
Q4.What if k exceeds n?
At most n − 1 swaps are ever useful (the last position auto-fixes once the rest are correct). Extra budget is simply unused.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You have a permutation of 1..n and at most k swaps; produce the lexicographically largest result. Greedily walk positions left to right: position i should hold the value n − i (the largest value not yet locked). If it already does, move on; otherwise swap in that value from wherever it currently sits, using a value→index map for O(1) lookup, and spend one swap. Stop when k runs out. O(n) time and space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you see that the largest permutation fills positions left to right with n, n−1, n−2, …, and whether you keep a value→index map so each swap is O(1) rather than scanning.

Where candidates slip

Linear-scanning for the desired value each step (making it O(n·k) or worse), or forgetting to update the map after a swap so later lookups point to stale indices.

How to stand out

Justify greedy with an exchange argument: a swap that raises an earlier position outranks any number of swaps improving later positions, because earlier positions are more significant.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Search All Reachable Permutations	`O(n^(2k) · ...)`	`O(branching)`	Mention to frame the search space, then collapse with the greedy observation.	Read
2	Greedy — Place Largest Value Leftmost with a Value→Index Map (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'put n at the front, then n−1, … each costing one swap, until the budget is gone'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewPermutation of 1..n, budget kk > 0 and positions remain?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Search All Reachable Permutations

TimeO(n^(2k) · ...)SpaceO(branching)

Mention to frame the search space, then collapse with the greedy observation.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

With at most k swaps, the reachable set is every permutation within k swaps of the start. You could BFS/DFS that space and keep the largest.

2Hint 2Explore hint

Each state branches into C(n,2) ≈ n²/2 possible swaps; depth up to k. The tree has on the order of (n²)^k leaves.

3Hint 3Explore hint

Even n = 100 and k = 5 is astronomically large. It only confirms what greedy gives directly.

A · Core idea

Define the search space as all permutations reachable with at most k swaps from the input. Explore it (DFS/BFS), comparing each reachable permutation and keeping the lexicographically largest.

Why it's correct. Every sequence achievable within the budget is generated, so the maximum among them is the answer.

Why it's hopeless. Each step can swap any pair — about n²/2 choices — and we may take up to k steps, giving an exponential (n²/2)^k tree. For the given constraints this is impossible.

The structure it reveals. Compare any two reachable permutations: whichever has a larger value at the first differing position wins, regardless of everything after. So spending a swap to raise an earlier position always beats spending it later. That single fact says: process positions left to right, and at each one place the largest value you can — no search needed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [2, 1, 3], k = 1

swap (0,2)

[3,1,2]

Statebest = [3,1,2]

Final result[3, 1, 2]

C · Code with teaching comments

Reference implementation previewpublic int[] largestPermBrute(int n, int[] arr, int k) { int[] best = arr.clone(); search(arr.clone(), k, best); return best; }Explore the full code

solution.javaJava

Brute Force — Search All Reachable Permutations — reference

2 teaching notes

1
public int[] largestPermBrute(int n, int[] arr, int k) {
2
    int[] best = arr.clone();
3
    search(arr.clone(), k, best);
4
    return best;
5
}
6
 
7
private void search(int[] cur, int k, int[] best) {
8
    // Keep the lexicographically largest permutation seen.
9
    if (compare(cur, best) > 0) System.arraycopy(cur, 0, best, 0, cur.length);
10
    if (k == 0) return;
11
    for (int i = 0; i < cur.length; i++) {
12
        // Try every pair swap at this depth — the source of the exponential blow-up.
13
        for (int j = i + 1; j < cur.length; j++) {
14
            int t = cur[i]; cur[i] = cur[j]; cur[j] = t;
15
            search(cur, k - 1, best);
16
            t = cur[i]; cur[i] = cur[j]; cur[j] = t;
17
        }
18
    }
19
}
20
 
21
private int compare(int[] a, int[] b) {
22
    for (int i = 0; i < a.length; i++) if (a[i] != b[i]) return Integer.compare(a[i], b[i]);
23
    return 0;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n^(2k) · ...) timeO(branching) spaceOpen the invariant and proofExplore the proof

Lexicographic comparison is dominated by the earliest differing position, so a swap that improves an earlier index is worth more than any swap improving a later one. Greedy left-to-right placement is therefore optimal — the brute-force tree collapses to a single pass.

ComplexityO(n^(2k) · ...) time, O(branching) space — Each of up to k swap levels branches over ~n²/2 swaps; the reachable-permutation tree is roughly (n²/2)^k states. Exponential in k.

E · Edge cases and pitfalls3(n²)^k state explosion — only for tiny n and k.Explore edge cases

Pitfalls

(n²)^k state explosion — only for tiny n and k.
Comparing arrays the wrong way (not lexicographically by first difference).
Re-exploring identical states without memoisation — still exponential.

03.2

Approach 2 of 2 · Optimal

Greedy — Place Largest Value Leftmost with a Value→Index Map (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'put n at the front, then n−1, … each costing one swap, until the budget is gone'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The largest permutation of 1..n is n, n−1, …, 1. So position i (0-indexed) wants the value n − i.

2Hint 2Explore hint

If position i already holds n − i, it's free — move on. Otherwise you must bring n − i here, which costs one swap.

3Hint 3Explore hint

To swap in O(1), keep a map from value to its current index. After swapping, update the map for BOTH values that moved, then decrement k.

A · Core idea

The lexicographically largest arrangement of 1..n is the descending sequence n, n−1, …, 1. So at position i (0-indexed) the ideal value is n − i. Walk positions left to right; at each one, if the ideal value isn't already there, swap it in from its current location and spend one swap. Stop when k reaches 0.

Why most-significant-position-first is optimal — the exchange argument. Lexicographic order is decided at the first position where two sequences differ. Suppose an optimal solution does NOT place the largest available value at the leftmost still-improvable position i, but instead uses a swap to improve some later position j > i. Re-route that one swap to instead place n − i at position i. The new sequence is larger at position i than the optimal was (it now holds the max possible value there), and positions 0..i−1 are unchanged — so it is lexicographically ≥ the supposed optimum, using no more swaps. Hence there's always an optimal solution that fixes the leftmost improvable position first; induction gives the full greedy.

Why a value→index map. To place n − i we must know where it currently sits. A map keyed by value gives that in O(1). The naive alternative — scanning for it — is O(n) per position and O(n·k) overall, which is too slow.

Why we update the map after each swap. Swapping arr[i] and arr[j] moves two values. The value n − i now lives at i, and the value previously at i now lives at j. Both map entries must be corrected, or a later lookup will point at a stale index and corrupt the result.

Why skipping correct positions matters. If arr[i] already equals n − i, fixing it would 'cost' a wasted self-swap. We skip it for free, preserving budget for positions that actually need it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [4, 2, 3, 5, 1], k = 1

Array state

i=0, want 5

arr[0]=4 ≠ 5; 5 at index 3

i ↓

[0]

[1]

[2]

j ↓

[3]

[4]

Current pointerResolved stateNot processed

Final result[5, 2, 3, 4, 1]

C · Code with teaching comments

solution.javaJava

Greedy — Place Largest Value Leftmost with a Value→Index Map (Optimal) — optimal

4 teaching notes

1
public int[] largestPermutation(int n, int[] arr, long k) {
2
    Map<Integer, Integer> pos = new HashMap<>();
3
    // Value→index map so we can locate any value in O(1).
4
    for (int i = 0; i < n; i++) pos.put(arr[i], i);
5
    for (int i = 0; i < n && k > 0; i++) {
6
        // The largest value that belongs at position i in the descending ideal.
7
        int want = n - i;
8
        if (arr[i] != want) {
9
            // Where the desired value currently lives — O(1) via the map.
10
            int j = pos.get(want);
11
            int moved = arr[i];
12
            arr[i] = want;
13
            arr[j] = moved;
14
            pos.put(moved, j);
15
            pos.put(want, i);
16
            k--;
17
        }
18
    }
19
    return arr;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

This is most-significant-digit-first greedy. Because the array is a permutation, the target at each index is known (n − i), so there's no search — just locate-and-swap with an O(1) map. The reusable kernel: 'maximise lexicographically under a move budget' → fix earliest positions first, each move buying the biggest legal improvement.

ComplexityO(n) time, O(n) space — Building the value→index map is O(n); the single left-to-right pass does O(1) work per position (map lookup + swap + two map updates). Total O(n) time, O(n) space for the map.

E · Edge cases and pitfalls6arr = [1,2,3], k = 100 — Position 0 wants 3 (swap with idx2 → [3,2,1]), position 1 wants 2 (already there). Result [3,2,1] using 1 swap; extra budget unused.Explore edge cases

Edge cases handled

arr = [1,2,3], k = 100Position 0 wants 3 (swap with idx2 → [3,2,1]), position 1 wants 2 (already there). Result [3,2,1] using 1 swap; extra budget unused.
already largest, e.g. [3,2,1]Every arr[i] == n − i → no swaps spent → returned unchanged.
k = 0Loop body never runs → array returned as-is.

Pitfalls

Linear-scanning for the desired value each step → O(n·k), too slow.
Forgetting to update BOTH map entries after a swap → stale indices corrupt later placements.
Spending a swap when arr[i] already equals n − i → wastes budget (guard with the equality check).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] largestPermutation(int n, int[] arr, long k) { Map<Integer, Integer> pos = new HashMap<>(); for (int i = 0; i < n; i++) pos.put(arr[i], i); for (int i = 0; i < n && k > 0; i++) { int want = n - i;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Linear scan instead of a value→index map

Searching the array for n − i every step is O(n) per position → O(n·k) overall, which TLEs for large n.

Explore the code comparison

Don't write this

for i in range(n):
    want = n - i
    if arr[i] != want:
        j = arr.index(want)   # O(n) scan
        arr[i], arr[j] = arr[j], arr[i]
        k -= 1
        if k == 0: break

Write this instead

pos = {v: i for i, v in enumerate(arr)}
for i in range(n):
    if k == 0: break
    want = n - i
    if arr[i] != want:
        j = pos[want]
        moved = arr[i]
        arr[i], arr[j] = want, moved
        pos[moved] = j; pos[want] = i
        k -= 1

Stale map after swap

After swapping, both moved values changed index. Updating only one (or neither) makes future lookups point to the wrong slot.

Explore the code comparison

Don't write this

int j = pos.get(want);
int moved = arr[i];
arr[i] = want; arr[j] = moved;
pos.put(want, i);   // forgot to update 'moved'

Write this instead

int j = pos.get(want);
int moved = arr[i];
arr[i] = want; arr[j] = moved;
pos.put(moved, j);
pos.put(want, i);

Wasting a swap on an already-correct position

If arr[i] already equals n − i, performing a self-swap decrements k for no gain, possibly leaving a later position unfixed.

Explore the code comparison

Don't write this

for i in range(n):
    if k == 0: break
    j = pos[n - i]
    arr[i], arr[j] = arr[j], arr[i]   # swaps even when i == j
    k -= 1

Write this instead

for i in range(n):
    if k == 0: break
    want = n - i
    if arr[i] != want:
        j = pos[want]
        arr[i], arr[j] = arr[j], arr[i]
        pos[arr[j]] = j; pos[want] = i
        k -= 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy left-to-right placement of the largest remaining value, with a value→index map for O(1) swaps

Code pattern to memorize

pos[v] = index of value v   # build once
for i in 0..n-1:
    if k == 0: break
    want = n - i              # largest value that belongs at position i
    if arr[i] != want:
        j = pos[want]
        swap arr[i], arr[j]
        pos[arr[j]] = j; pos[want] = i   # update the map for both moved values
        k -= 1
return arr

Rules to remember

1The input is a permutation of 1..n, so the largest possible value for position i is exactly n − i (0-indexed positions).
2Greedy is correct: fixing the most significant position with the biggest available value beats any other use of a swap.
3Use a value→index map so you can find where the desired value lives in O(1), then swap it into place.
4Each productive placement costs exactly one swap; skip positions already holding the right value (they cost nothing).
5Stop as soon as k hits 0 — remaining positions stay as they are.

Use this pattern when

Maximise (or minimise) a sequence lexicographically under a bounded number of swaps
Values are a permutation so the target at each position is known in advance
Most-significant-position-first greedy with O(1) locate-and-swap
A swap budget caps how many positions you can fix

Choose another pattern when

Only adjacent swaps allowed → bubble-style / inversion counting, not direct placement
Values aren't a permutation → the target at each position isn't simply n − i
You must minimise total swap DISTANCE rather than count → different cost model
Unlimited swaps → just sort, no greedy budget reasoning needed

Interview takeaway

Lexicographic maximisation under a swap budget is a most-significant-digit-first greedy: place the largest legal value at the leftmost position, each fix costing one swap, and keep a value→index map so locating the swap partner is O(1). The exchange argument proves fixing earlier positions first is optimal.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternMost-significant-position-first greedy under a move budget: since the input is a permutation, each position's ideal value is known (n − i), so place it directly with an O(1) value→index map. The exchange argument — improving an earlier position dominates any later improvement — proves optimality.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sherlock and the Beast
Constructive greedy that also front-loads the largest symbol for the biggest number.
Maximum Swap
Coming soon
One swap to maximise a number's digits — same 'biggest digit to the front' greedy.
Minimum Adjacent Swaps to Sort
Coming soon
When only adjacent swaps are allowed the cost model changes to inversion counting.
Jim and the Orders
Another permutation-of-indices problem solved by ordering on a derived key.

Same pattern

←

Jim and the Orders

Continue · Next problem

Permuting Two Arrays

easyGreedySometimes asked

Largest Permutation

Greedy Algorithms · 20 of 23 · 9 min

You are given a permutation of the integers 1 to n and a number k. You may perform at most `k` swaps of any two elements.

Return the lexicographically largest permutation obtainable with at most k swaps.

In plain English

Examples

Example 1

Input: arr = [4, 2, 3, 5, 1], k = 1
Output: [5, 2, 3, 4, 1]
Note: Largest value 5 belongs at position 0. It's at index 3; swap arr[0]↔arr[3] → [5,2,3,4,1]. k is now 0, so stop.

Example 2

Input: arr = [2, 1, 3], k = 1
Output: [3, 1, 2]
Note: Position 0 wants 3 (currently 2). 3 is at index 2; swap → [3,1,2]. Budget exhausted.

Example 3

Input: arr = [2, 1, 3], k = 0
Output: [2, 1, 3]
Note: No swaps allowed — return the array unchanged.

Constraints

1 ≤ n ≤ 100000
1 ≤ k ≤ 10⁹ (effectively capped at n − 1 useful swaps)
The input is a permutation of 1..n (each value 1..n appears exactly once)

Clarifying questions4First question: Are swaps limited to adjacent elements?Explore questions

Q1.Are swaps limited to adjacent elements?
No — any two positions can be swapped. That's why one swap can place the global maximum directly at position 0.
Q2.Is the input guaranteed to be a permutation of 1..n?
Yes. That's what makes the target at position i exactly n − i (0-indexed), with no duplicates or gaps.
Q3.Do we use exactly k swaps or at most k?
At most k. If the array is already largest, or becomes largest before k runs out, we stop early — wasting a swap can only hurt.
Q4.What if k exceeds n?
At most n − 1 swaps are ever useful (the last position auto-fixes once the rest are correct). Extra budget is simply unused.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you see that the largest permutation fills positions left to right with n, n−1, n−2, …, and whether you keep a value→index map so each swap is O(1) rather than scanning.

Where candidates slip

Linear-scanning for the desired value each step (making it O(n·k) or worse), or forgetting to update the map after a swap so later lookups point to stale indices.

How to stand out

Justify greedy with an exchange argument: a swap that raises an earlier position outranks any number of swaps improving later positions, because earlier positions are more significant.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Search All Reachable Permutations	`O(n^(2k) · ...)`	`O(branching)`	Mention to frame the search space, then collapse with the greedy observation.	Read
2	Greedy — Place Largest Value Leftmost with a Value→Index Map (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'put n at the front, then n−1, … each costing one swap, until the budget is gone'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Search All Reachable Permutations

TimeO(n^(2k) · ...)SpaceO(branching)

Mention to frame the search space, then collapse with the greedy observation.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

With at most k swaps, the reachable set is every permutation within k swaps of the start. You could BFS/DFS that space and keep the largest.

2Hint 2Explore hint

Each state branches into C(n,2) ≈ n²/2 possible swaps; depth up to k. The tree has on the order of (n²)^k leaves.

3Hint 3Explore hint

Even n = 100 and k = 5 is astronomically large. It only confirms what greedy gives directly.

A · Core idea

Define the search space as all permutations reachable with at most k swaps from the input. Explore it (DFS/BFS), comparing each reachable permutation and keeping the lexicographically largest.

Why it's correct. Every sequence achievable within the budget is generated, so the maximum among them is the answer.

Why it's hopeless. Each step can swap any pair — about n²/2 choices — and we may take up to k steps, giving an exponential (n²/2)^k tree. For the given constraints this is impossible.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [2, 1, 3], k = 1

swap (0,2)

[3,1,2]

Statebest = [3,1,2]

Final result[3, 1, 2]

C · Code with teaching comments

Reference implementation previewpublic int[] largestPermBrute(int n, int[] arr, int k) { int[] best = arr.clone(); search(arr.clone(), k, best); return best; }Explore the full code

solution.javaJava

Brute Force — Search All Reachable Permutations — reference

2 teaching notes

1
public int[] largestPermBrute(int n, int[] arr, int k) {
2
    int[] best = arr.clone();
3
    search(arr.clone(), k, best);
4
    return best;
5
}
6
 
7
private void search(int[] cur, int k, int[] best) {
8
    // Keep the lexicographically largest permutation seen.
9
    if (compare(cur, best) > 0) System.arraycopy(cur, 0, best, 0, cur.length);
10
    if (k == 0) return;
11
    for (int i = 0; i < cur.length; i++) {
12
        // Try every pair swap at this depth — the source of the exponential blow-up.
13
        for (int j = i + 1; j < cur.length; j++) {
14
            int t = cur[i]; cur[i] = cur[j]; cur[j] = t;
15
            search(cur, k - 1, best);
16
            t = cur[i]; cur[i] = cur[j]; cur[j] = t;
17
        }
18
    }
19
}
20
 
21
private int compare(int[] a, int[] b) {
22
    for (int i = 0; i < a.length; i++) if (a[i] != b[i]) return Integer.compare(a[i], b[i]);
23
    return 0;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n^(2k) · ...) timeO(branching) spaceOpen the invariant and proofExplore the proof

ComplexityO(n^(2k) · ...) time, O(branching) space — Each of up to k swap levels branches over ~n²/2 swaps; the reachable-permutation tree is roughly (n²/2)^k states. Exponential in k.

E · Edge cases and pitfalls3(n²)^k state explosion — only for tiny n and k.Explore edge cases

Pitfalls

(n²)^k state explosion — only for tiny n and k.
Comparing arrays the wrong way (not lexicographically by first difference).
Re-exploring identical states without memoisation — still exponential.

03.2

Approach 2 of 2 · Optimal

Greedy — Place Largest Value Leftmost with a Value→Index Map (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'put n at the front, then n−1, … each costing one swap, until the budget is gone'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The largest permutation of 1..n is n, n−1, …, 1. So position i (0-indexed) wants the value n − i.

2Hint 2Explore hint

If position i already holds n − i, it's free — move on. Otherwise you must bring n − i here, which costs one swap.

3Hint 3Explore hint

To swap in O(1), keep a map from value to its current index. After swapping, update the map for BOTH values that moved, then decrement k.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [4, 2, 3, 5, 1], k = 1

Array state

i=0, want 5

arr[0]=4 ≠ 5; 5 at index 3

i ↓

[0]

[1]

[2]

j ↓

[3]

[4]

Current pointerResolved stateNot processed

Final result[5, 2, 3, 4, 1]

C · Code with teaching comments

solution.javaJava

Greedy — Place Largest Value Leftmost with a Value→Index Map (Optimal) — optimal

4 teaching notes

1
public int[] largestPermutation(int n, int[] arr, long k) {
2
    Map<Integer, Integer> pos = new HashMap<>();
3
    // Value→index map so we can locate any value in O(1).
4
    for (int i = 0; i < n; i++) pos.put(arr[i], i);
5
    for (int i = 0; i < n && k > 0; i++) {
6
        // The largest value that belongs at position i in the descending ideal.
7
        int want = n - i;
8
        if (arr[i] != want) {
9
            // Where the desired value currently lives — O(1) via the map.
10
            int j = pos.get(want);
11
            int moved = arr[i];
12
            arr[i] = want;
13
            arr[j] = moved;
14
            pos.put(moved, j);
15
            pos.put(want, i);
16
            k--;
17
        }
18
    }
19
    return arr;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Edge cases handled

arr = [1,2,3], k = 100Position 0 wants 3 (swap with idx2 → [3,2,1]), position 1 wants 2 (already there). Result [3,2,1] using 1 swap; extra budget unused.
already largest, e.g. [3,2,1]Every arr[i] == n − i → no swaps spent → returned unchanged.
k = 0Loop body never runs → array returned as-is.

Pitfalls

Linear-scanning for the desired value each step → O(n·k), too slow.
Forgetting to update BOTH map entries after a swap → stale indices corrupt later placements.
Spending a swap when arr[i] already equals n − i → wastes budget (guard with the equality check).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Linear scan instead of a value→index map

Searching the array for n − i every step is O(n) per position → O(n·k) overall, which TLEs for large n.

Explore the code comparison

Don't write this

for i in range(n):
    want = n - i
    if arr[i] != want:
        j = arr.index(want)   # O(n) scan
        arr[i], arr[j] = arr[j], arr[i]
        k -= 1
        if k == 0: break

Write this instead

pos = {v: i for i, v in enumerate(arr)}
for i in range(n):
    if k == 0: break
    want = n - i
    if arr[i] != want:
        j = pos[want]
        moved = arr[i]
        arr[i], arr[j] = want, moved
        pos[moved] = j; pos[want] = i
        k -= 1

Stale map after swap

After swapping, both moved values changed index. Updating only one (or neither) makes future lookups point to the wrong slot.

Explore the code comparison

Don't write this

int j = pos.get(want);
int moved = arr[i];
arr[i] = want; arr[j] = moved;
pos.put(want, i);   // forgot to update 'moved'

Write this instead

int j = pos.get(want);
int moved = arr[i];
arr[i] = want; arr[j] = moved;
pos.put(moved, j);
pos.put(want, i);

Wasting a swap on an already-correct position

If arr[i] already equals n − i, performing a self-swap decrements k for no gain, possibly leaving a later position unfixed.

Explore the code comparison

Don't write this

for i in range(n):
    if k == 0: break
    j = pos[n - i]
    arr[i], arr[j] = arr[j], arr[i]   # swaps even when i == j
    k -= 1

Write this instead

for i in range(n):
    if k == 0: break
    want = n - i
    if arr[i] != want:
        j = pos[want]
        arr[i], arr[j] = arr[j], arr[i]
        pos[arr[j]] = j; pos[want] = i
        k -= 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy left-to-right placement of the largest remaining value, with a value→index map for O(1) swaps

Code pattern to memorize

pos[v] = index of value v   # build once
for i in 0..n-1:
    if k == 0: break
    want = n - i              # largest value that belongs at position i
    if arr[i] != want:
        j = pos[want]
        swap arr[i], arr[j]
        pos[arr[j]] = j; pos[want] = i   # update the map for both moved values
        k -= 1
return arr

Rules to remember

1The input is a permutation of 1..n, so the largest possible value for position i is exactly n − i (0-indexed positions).
2Greedy is correct: fixing the most significant position with the biggest available value beats any other use of a swap.
3Use a value→index map so you can find where the desired value lives in O(1), then swap it into place.
4Each productive placement costs exactly one swap; skip positions already holding the right value (they cost nothing).
5Stop as soon as k hits 0 — remaining positions stay as they are.

Use this pattern when

Maximise (or minimise) a sequence lexicographically under a bounded number of swaps
Values are a permutation so the target at each position is known in advance
Most-significant-position-first greedy with O(1) locate-and-swap
A swap budget caps how many positions you can fix

Choose another pattern when

Only adjacent swaps allowed → bubble-style / inversion counting, not direct placement
Values aren't a permutation → the target at each position isn't simply n − i
You must minimise total swap DISTANCE rather than count → different cost model
Unlimited swaps → just sort, no greedy budget reasoning needed

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sherlock and the Beast
Constructive greedy that also front-loads the largest symbol for the biggest number.
Maximum Swap
Coming soon
One swap to maximise a number's digits — same 'biggest digit to the front' greedy.
Minimum Adjacent Swaps to Sort
Coming soon
When only adjacent swaps are allowed the cost model changes to inversion counting.
Jim and the Orders
Another permutation-of-indices problem solved by ordering on a derived key.

Same pattern

←

Jim and the Orders

Continue · Next problem

Permuting Two Arrays