Minimum Possible Integer After at Most K Adjacent Swaps On Digits

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

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.

Input & Output

Example 1 — Basic Greedy Selection

$ Input: num = "4321", k = 4

› Output: "1342"

💡 Note: Move 1 to front (3 swaps: 4321→4312→4132→1432→1342), then move 2 forward (1 swap: 1342→1324 would exceed k), so result is "1342"

Example 2 — Limited Swaps

$ Input: num = "100", k = 1

› Output: "010"

💡 Note: Can only make 1 swap. Best option is to swap first two digits: 100→010

Example 3 — No Swaps Needed

$ Input: num = "1234", k = 3

› Output: "1234"

💡 Note: Already in minimum order, no swaps needed

Constraints

1 ≤ num.length ≤ 3 × 10⁴
num consists only of digits
0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits and maximum number of adjacent swaps allowed

Process

Greedily move smallest digits forward using adjacent swaps

Output

Lexicographically smallest possible string

Key Takeaway

🎯 Key Insight: Always move the smallest reachable digit to the front first for optimal results

Asked in

G Google 15 f Facebook 8 a Amazon 6

The key insight is to greedily move the smallest available digits to the front first. The optimal approach uses a Fenwick Tree to efficiently track position costs during swaps. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n²)	O(1)	Greedily move smallest digits to front within swap budget
Brute Force with DFS	O(k! × n)	O(k × n)	Try all possible sequences of adjacent swaps recursively
Optimized with Fenwick Tree	O(n log n)	O(n)	Use Fenwick Tree to efficiently track digit positions during swaps

Greedy Approach — Algorithm Steps

Step 1: For each position, find smallest reachable digit
Step 2: Bubble the smallest digit to current position
Step 3: Update remaining swaps and continue

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Window

Find smallest digit within k swaps

Bubble Forward

Move it to front using adjacent swaps

Continue

Repeat for next position with remaining swaps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b) {
    return a < b ? a : b;
}

char* solution(char* num, int k) {
    int n = strlen(num);
    char* result = malloc(n + 1);
    strcpy(result, num);
    
    for (int i = 0; i < n; i++) {
        if (k == 0) break;
        
        // Find the smallest digit within reach
        char minDigit = result[i];
        int minIdx = i;
        
        // Look ahead within the swap budget
        for (int j = i + 1; j < min(i + k + 1, n); j++) {
            if (result[j] < minDigit) {
                minDigit = result[j];
                minIdx = j;
            }
        }
        
        // Bubble the smallest digit to position i
        while (minIdx > i && k > 0) {
            char temp = result[minIdx];
            result[minIdx] = result[minIdx - 1];
            result[minIdx - 1] = temp;
            minIdx--;
            k--;
        }
    }
    
    return result;
}

int main() {
    char num[100001];
    int k;
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    scanf("%d", &k);
    
    char* result = solution(num, k);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position, we scan up to n digits and perform up to n swaps

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

23.4K Views

Medium Frequency

~45 min Avg. Time

542 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler