LeetCode 1505 - Minimum Possible Integer After at Most K Adjacent Swaps On Digits

LeetCode Problem 1505

Difficulty: 🔴 Hard
Topics: String, Greedy, Binary Indexed Tree, Segment Tree

Solution

Problem Understanding

The problem gives us a numeric string num and an integer k. Each operation allows us to swap two adjacent digits. We may perform at most k such swaps, and the goal is to construct the smallest possible integer, returned as a string.

The important detail is that swaps are only allowed between adjacent positions. This means moving a digit from index i to index j costs exactly i - j swaps if i > j. We cannot freely rearrange the digits like a normal sorting problem.

For example, if the number is "4321" and k = 4, we can move the digit '1' from the end toward the front using adjacent swaps. Every step moves it one position left. The total number of left moves determines the swap cost.

The constraints are very large:

• num.length can be up to 3 * 10^4
• k can be as large as 10^9

These constraints immediately rule out any brute force simulation of swaps. Even an O(n^2) approach becomes risky at this scale. We need a solution close to O(n log n).

Another important observation is that the output may contain leading zeros. For example, "100" with one swap becomes "010". Therefore, we should not treat the result as an integer type. We must preserve it as a string.

Several edge cases are important:

• Very large k, where we can effectively produce the lexicographically smallest arrangement possible under adjacency constraints.
• Strings with many repeated digits.
• Strings already in optimal order.
• Inputs containing zeros that may move to the front.
• Situations where a smaller digit exists later in the string, but moving it would cost more swaps than we have remaining.

Approaches

Brute Force Approach

A naive approach is to repeatedly look ahead and simulate all possible adjacent swaps. At every position, we try moving every reachable digit to the front and choose the smallest resulting configuration.

One possible brute force method is:

1. For every position in the answer:

• Search the next k positions.
• Find the smallest digit reachable.
• Perform the adjacent swaps explicitly.

2. Repeat until the string is complete.

This approach is logically correct because choosing the smallest reachable digit greedily produces the lexicographically smallest result.

However, explicitly performing adjacent swaps is extremely expensive. Moving digits in arrays or strings repeatedly costs O(n) each time. Since we may do this for many positions, the overall complexity can degrade to O(n^2) or worse.

With n = 30000, this is far too slow.

Key Insight

The core observation is that we do not actually need to simulate every swap.

Instead, we only need to know:

• Where each digit currently exists
• How many positions have already been removed before it

Suppose a digit originally sits at index i. After some earlier digits are extracted and placed into the answer, its effective current position changes.

This is exactly the type of problem that a Binary Indexed Tree, also called a Fenwick Tree, handles efficiently.

The strategy becomes:

• Store the indices of every digit 0-9
• Build the answer greedily from left to right
• At each step, try digits from '0' to '9'
• Compute how many swaps are required to bring that digit forward
• Choose the smallest digit whose swap cost is within the remaining k

The Binary Indexed Tree efficiently tracks how many positions have already been removed before a given index.

This reduces the complexity to O(n log n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(n)	Explicitly simulates adjacent swaps
Optimal	O(n log n)	O(n)	Greedy construction with Binary Indexed Tree

Algorithm Walkthrough

1. Create a queue for each digit from 0 to 9.

For every character in num, store its index in the queue corresponding to that digit. This allows us to quickly locate the leftmost unused occurrence of any digit. 2. Initialize a Binary Indexed Tree.

The Fenwick Tree tracks how many digits have already been removed from earlier positions. This lets us compute the effective current position of a digit after previous operations. 3. Build the answer one position at a time.

For each position in the final result, we attempt to place the smallest possible digit. 4. Try digits from 0 through 9.

For each candidate digit:

• Check whether any unused occurrence exists.
• Let original_index be the first unused occurrence.

5. Compute the effective swap cost.

Some earlier positions may already have been removed and placed into the answer.

If:

• removed_before = number of removed indices before original_index

then the digit's effective current position becomes:

$\text{effective position} = \text{original index} - \text{removed before}$

The number of swaps required equals this effective position relative to the current front. 6. Check whether the cost fits within k.

If the required swaps are less than or equal to k, we choose this digit immediately because trying digits in increasing order guarantees lexicographical minimality. 7. Update the data structures.

After selecting a digit:

• Append it to the result
• Subtract its cost from k
• Mark its original index as removed in the Fenwick Tree
• Remove the index from that digit's queue

8. Repeat until all positions are filled.

Why it works

At every step, we choose the smallest digit that can legally be moved to the current position within the remaining swap budget.

Lexicographical order is determined from left to right. Therefore, once we can place a smaller digit earlier, any alternative choice would produce a larger final result regardless of future decisions.

The Binary Indexed Tree guarantees that swap costs are computed correctly even after earlier digits have been extracted and removed from the middle of the string.

Python Solution

from collections import deque
from typing import List

class FenwickTree:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index: int, delta: int) -> None:
        index += 1

        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        index += 1
        result = 0

        while index > 0:
            result += self.tree[index]
            index -= index & -index

        return result

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        n = len(num)

        positions = [deque() for _ in range(10)]

        for index, digit in enumerate(num):
            positions[int(digit)].append(index)

        fenwick = FenwickTree(n)

        result = []

        for _ in range(n):

            for digit in range(10):

                if not positions[digit]:
                    continue

                original_index = positions[digit][0]

                removed_before = fenwick.query(original_index)

                swaps_needed = original_index - removed_before

                if swaps_needed <= k:
                    k -= swaps_needed

                    result.append(str(digit))

                    fenwick.update(original_index, 1)

                    positions[digit].popleft()

                    break

        return "".join(result)

The implementation begins by storing the positions of each digit in separate queues. Since digits are processed from left to right, queues allow efficient retrieval of the next unused occurrence.

The FenwickTree class supports two operations:

• update(index, delta) marks a position as removed
• query(index) returns how many removed positions exist up to that index

During construction of the result, we iterate through digits 0 to 9 and test whether the leftmost occurrence can be moved into the current position within the remaining swap budget.

The expression:

$\text{swaps needed} = \text{original index} - \text{removed before}$

computes the effective number of adjacent swaps required after accounting for already extracted digits.

Once a digit is chosen:

• It becomes permanently fixed in the answer
• Its position is marked removed in the Fenwick Tree
• The swap budget decreases

The greedy process repeats until the entire answer is built.

Go Solution

package main

import (
	"strings"
)

type FenwickTree struct {
	tree []int
	size int
}

func NewFenwickTree(size int) *FenwickTree {
	return &FenwickTree{
		tree: make([]int, size+1),
		size: size,
	}
}

func (f *FenwickTree) Update(index int, delta int) {
	index++

	for index <= f.size {
		f.tree[index] += delta
		index += index & -index
	}
}

func (f *FenwickTree) Query(index int) int {
	index++

	result := 0

	for index > 0 {
		result += f.tree[index]
		index -= index & -index
	}

	return result
}

func minInteger(num string, k int) string {
	n := len(num)

	positions := make([][]int, 10)

	for i, ch := range num {
		digit := int(ch - '0')
		positions[digit] = append(positions[digit], i)
	}

	usedIndex := make([]int, 10)

	fenwick := NewFenwickTree(n)

	var result strings.Builder

	for i := 0; i < n; i++ {

		for digit := 0; digit < 10; digit++ {

			if usedIndex[digit] >= len(positions[digit]) {
				continue
			}

			originalIndex := positions[digit][usedIndex[digit]]

			removedBefore := fenwick.Query(originalIndex)

			swapsNeeded := originalIndex - removedBefore

			if swapsNeeded <= k {

				k -= swapsNeeded

				result.WriteByte(byte(digit + '0'))

				fenwick.Update(originalIndex, 1)

				usedIndex[digit]++

				break
			}
		}
	}

	return result.String()
}

The Go implementation follows the same algorithmic structure as the Python version.

One difference is that Go does not have a built in deque type in the standard library. Instead, we store all indices in slices and maintain a pointer array called usedIndex to track the next unused occurrence for each digit.

The result string is constructed using strings.Builder, which is more efficient than repeated string concatenation.

Since all values remain within standard integer limits for Go on LeetCode, regular int types are sufficient.

Worked Examples

Example 1

Input:

num = "4321"
k = 4

Initial digit positions:

Digit	Positions
1	[3]
2	[2]
3	[1]
4	[0]

Step 1

Try digits from 0 to 9.

Digit 1 is at index 3.

Removed before index 3 = 0

Cost:

$3 - 0 = 3$

Since 3 <= 4, choose 1.

Updated state:

Variable	Value
Result	"1"
k	1
Removed indices	{3}

Step 2

Try digit 2.

Removed before index 2 = 0

Cost:

$2 - 0 = 2$

Too expensive.

Try digit 3.

Cost:

$1 - 0 = 1$

Choose 3.

Variable	Value
Result	"13"
k	0
Removed indices	{1, 3}

Remaining digits

No swaps remain, so digits stay in relative order.

Final answer:

"1342"

Example 2

Input:

num = "100"
k = 1

Digit positions:

Digit	Positions
0	[1, 2]
1	[0]

Step 1

Try digit 0 at index 1.

Cost:

$1 - 0 = 1$

Choose 0.

Variable	Value
Result	"0"
k	0

Remaining digits

Order remains "10".

Final result:

"010"

Example 3

Input:

num = "36789"
k = 1000

The number is already lexicographically minimal because digits are increasing from left to right.

Every earlier digit is already the smallest possible choice.

Final answer:

"36789"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each digit selection performs Fenwick Tree operations
Space	O(n)	Queues and Fenwick Tree store linear data

The algorithm processes each character exactly once. For every character, we may test up to 10 digits, which is constant. Each Fenwick Tree query and update costs O(log n).

Therefore, the total complexity is:

$O(n \log n)$

The space complexity is linear because we store:

• The digit position queues
• The Fenwick Tree
• The output string

Test Cases

solution = Solution()

assert solution.minInteger("4321", 4) == "1342"  # provided example
assert solution.minInteger("100", 1) == "010"  # leading zero case
assert solution.minInteger("36789", 1000) == "36789"  # already minimal

assert solution.minInteger("22", 1) == "22"  # repeated digits
assert solution.minInteger("9438957234785635408", 23) == "0345989723478563548"  # large complex case

assert solution.minInteger("10", 1) == "01"  # single swap
assert solution.minInteger("10", 100) == "01"  # excessive k

assert solution.minInteger("12345", 1) == "12345"  # already sorted
assert solution.minInteger("54321", 10) == "12345"  # enough swaps for full sort

assert solution.minInteger("9090", 2) == "0990"  # moving zero forward
assert solution.minInteger("1111", 5) == "1111"  # identical digits

assert solution.minInteger("21", 1) == "12"  # smallest nontrivial case
assert solution.minInteger("10200", 1) == "01200"  # zero moved to front

Test Summary

Test	Why
"4321", 4	Validates core greedy logic
"100", 1	Confirms leading zeros are allowed
"36789", 1000	Tests already optimal ordering
"22", 1	Ensures duplicates work correctly
Large mixed input	Stress test for Fenwick logic
"10", 1	Minimal adjacent swap example
"10", 100	Excessively large k
"12345", 1	Already sorted input
"54321", 10	Full reordering possible
"9090", 2	Multiple zeros and movement
"1111", 5	All digits identical
"21", 1	Smallest meaningful input
"10200", 1	Zero moved forward with limited swaps

Edge Cases

One important edge case occurs when the input already represents the smallest possible arrangement. For example, "12345" cannot be improved regardless of the swap budget. A buggy implementation might still attempt unnecessary operations or incorrectly reorder equal digits. This solution handles the case naturally because the greedy scan always finds the current front digit to be optimal.

Another important case involves leading zeros. In many integer problems, leading zeros are invalid or automatically removed. Here they are explicitly allowed. For example, "100" with one swap becomes "010". Since the implementation always treats the number as a string and never converts it into an integer type, leading zeros are preserved correctly.

Repeated digits are another common source of bugs. Consider "1111" or "9090". We must always use the leftmost unused occurrence of each digit because choosing a later occurrence could waste swaps and break optimality. The queues ensure occurrences are processed in correct order.

A final critical edge case involves very large values of k. Since k can be up to 10^9, implementations that simulate swaps one by one become infeasible. This solution only computes swap counts mathematically using the Fenwick Tree, so performance remains efficient even for enormous swap budgets.