Skip to main content
Talentd

Minimum Possible Integer After at Most K Adjacent Swaps On Digits - Solution & Explanation

HardStringGreedyBinary Indexed TreeSegment Tree9 min readAsked at: Hashedin
Practice this problem

Problem Statement

You are given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

 

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

 

Constraints:

  • 1 <= num.length <= 3 * 104
  • num consists of only digits and does not contain leading zeros.
  • 1 <= k <= 109

Approach Overview

Problem Overview: You are given a numeric string num and an integer k. Each operation swaps two adjacent digits, and you can perform at most k swaps. The goal is to produce the lexicographically smallest possible integer after these swaps.

Approach 1: Greedy with Permutation Indices + Binary Indexed Tree (O(n log n) time, O(n) space)

The key observation is that the leftmost digits have the greatest impact on the final number. At each position, try to bring the smallest possible digit forward if it can reach the current position within the remaining swap budget. Maintain queues of indices for digits 0–9. For each candidate digit, compute how many swaps are needed to move its next occurrence to the current position.

A Binary Indexed Tree (Fenwick Tree) tracks how many digits have already been moved. This allows you to adjust the effective index after previous shifts. If the required swaps are ≤ k, move that digit to the result, update the tree, reduce k, and continue. The strategy works because a greedy choice of the smallest reachable digit always leads to the optimal prefix.

Approach 2: Segment Tree for Efficient Minimum Finding (O(n log n) time, O(n) space)

Another way to implement the same greedy idea is with a segment tree. Instead of scanning digits 0–9 each step, build a segment tree that stores the minimum digit available in a range along with its index. The tree supports queries to find the smallest digit that can be moved to the current position without exceeding the remaining swaps.

When a digit is selected, update the tree to mark its index as used and adjust swap counts accordingly. The segment tree efficiently handles repeated minimum queries and updates in O(log n). This approach is especially useful in languages where priority structures or index bookkeeping becomes complex.

Recommended for interviews: The greedy strategy combined with a Binary Indexed Tree is the expected optimal solution. It demonstrates understanding of lexicographic minimization, index shifting caused by swaps, and efficient prefix counting. Segment trees solve the same problem but are usually considered an alternative implementation. Showing the greedy reasoning first, then implementing it with a Fenwick Tree, signals strong algorithmic maturity.

Approach 1: Greedy Approach with Permutation Indices

This approach makes use of a greedy algorithm. The idea is to always try to bring the smallest possible digit to the front using the allowed adjacent swaps.

By iterating through the digits of the number, for each position, determine the smallest digit within a distance of k. Then perform the necessary swaps to bring that smallest digit to the current position.

This approach minimizes the resulting integer by always prioritizing the smallest digit to be swapped forward.

We maintain the string as a list for in-place modifications. For each index, find the minimum digit within the next k positions and swap it forward. Update k for the swaps made and break if k runs out.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n*k) in the worst case where k is large.
Space Complexity: O(n) due to the storage of digits.

Try this approach in the editor →

Approach 2: Using Segment Tree for Efficient Minimum Finding

This approach uses a Segment Tree to efficiently find the minimum digit within a segment of the number in logarithmic time. It allows us to store and update the position of digits dynamically.

The Segment Tree helps in reducing the computational bottleneck of finding the minimum digit that can be swapped to the front within 'k' swaps, from linear to log time complexity per query.

This solution is implemented using a Segment Tree wrapped into a class. It builds the tree and uses it to find the minimum index efficiently, re-building as adjustments are made.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n log n) due to segment tree operations.
Space Complexity: O(n) due to the segment tree structure.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Permutation Indices

Time Complexity: O(n*k) in the worst case where k is large.
Space Complexity: O(n) due to the storage of digits.

Using Segment Tree for Efficient Minimum Finding

Time Complexity: O(n log n) due to segment tree operations.
Space Complexity: O(n) due to the segment tree structure.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Binary Indexed TreeO(n log n)O(n)Best general solution. Efficiently tracks index shifts caused by swaps.
Greedy with Segment TreeO(n log n)O(n)Useful when implementing range minimum queries and updates together.

Video Solution

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits (Leetcode Hard) • Programming Live with Larry • 1,918 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Possible Integer After at Most K Adjacent Swaps On Digits easy or hard?
Minimum Possible Integer After at Most K Adjacent Swaps On Digits is classified as Hard on LeetCode. The difficulty comes from combining greedy digit selection with advanced data structures like Binary Indexed Trees or Segment Trees to handle dynamic index shifts efficiently.
Minimum Possible Integer After at Most K Adjacent Swaps On Digits Python/Java solution
Python and Java implementations usually follow the greedy + Fenwick Tree strategy. Maintain queues for each digit (0–9), select the smallest reachable digit, compute its swap cost using prefix sums from the tree, and update the structure after placing the digit. This ensures O(n log n) performance.
How to solve Minimum Possible Integer After at Most K Adjacent Swaps On Digits in O(n)?
A strict O(n) solution is generally not feasible because the algorithm must repeatedly update and query positions after swaps. Efficient implementations rely on a Binary Indexed Tree or Segment Tree, which reduces operations to O(log n). The resulting complexity becomes O(n log n), which is considered optimal for this problem.
What is the best approach for Minimum Possible Integer After at Most K Adjacent Swaps On Digits?
The best approach uses a greedy strategy combined with a Binary Indexed Tree (Fenwick Tree). At each position, choose the smallest digit that can be moved to the front using at most k swaps. The Fenwick Tree tracks how many digits have already shifted so the effective swap distance can be computed quickly. This solution runs in O(n log n) time with O(n) space.
Is Minimum Possible Integer After at Most K Adjacent Swaps On Digits asked at Google/Amazon/Meta?
Problems involving greedy digit selection with Fenwick Trees or segment trees frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem is considered a high-level interview question because it combines greedy reasoning with advanced data structures.
What data structure is used in Minimum Possible Integer After at Most K Adjacent Swaps On Digits?
The most common data structures used are a Binary Indexed Tree (Fenwick Tree) and sometimes a Segment Tree. They help track how many digits have been removed or shifted so the effective swap distance can be calculated efficiently during the greedy selection process.
What is the time complexity of Minimum Possible Integer After at Most K Adjacent Swaps On Digits?
The optimal solution runs in O(n log n) time. Each digit selection requires logarithmic updates and prefix queries in a Binary Indexed Tree or Segment Tree. Space complexity is O(n) for storing digit positions and maintaining the tree structure.

Ready to solve this problem?

Practice Minimum Possible Integer After at Most K Adjacent Swaps On Digits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring