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

Master LeetCode problem 1505 (Minimum Possible Integer After at Most K Adjacent Swaps On Digits), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Hard

String Greedy Binary Indexed Tree Segment Tree

Problem Explanation

Explanation:

To solve this problem, we can use a greedy approach. We iterate over each digit of the input number from left to right. For each digit, we check the range of possible positions where it can be moved based on the remaining swaps available. We choose the smallest digit that can be moved to the current position and update the remaining swaps accordingly.

Algorithm:

Initialize an array pos to keep track of the positions of each digit in the input number.
Iterate over each digit of the input number from left to right.
For the current digit, determine the range of positions it can be moved to based on the remaining swaps available.
Choose the smallest digit that can be moved to the current position within the range and update the remaining swaps accordingly.
Update the pos array to reflect the new position of the digit.
Construct the minimum possible integer using the updated positions in the pos array.

Time Complexity:

The time complexity of this approach is O(n^2) where n is the length of the input number.

Space Complexity:

The space complexity is O(n) where n is the length of the input number. :

Solution Code

class Solution {
    public String minInteger(String num, int k) {
        char[] arr = num.toCharArray();
        int n = arr.length;
        int[] pos = new int[10];
        
        for (int i = 0; i < n; i++) {
            if (k == 0) break;
            for (int j = 0; j < 10; j++) {
                if (pos[j] == 0) continue;
                int steps = pos[j] - i;
                if (steps <= k) {
                    k -= steps;
                    for (int l = j; l > arr[i] - '0'; l--) {
                        pos[l]--;
                    }
                    pos[arr[i] - '0']++;
                    arr[pos[j]] = arr[i];
                    break;
                }
            }
            pos[arr[i] - '0'] = i;
        }
        
        return new String(arr);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1505 (Minimum Possible Integer After at Most K Adjacent Swaps On Digits)?

This page provides optimized solutions for LeetCode problem 1505 (Minimum Possible Integer After at Most K Adjacent Swaps On Digits) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1505 (Minimum Possible Integer After at Most K Adjacent Swaps On Digits)?

The time complexity for LeetCode 1505 (Minimum Possible Integer After at Most K Adjacent Swaps On Digits) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1505 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1505 in Java, C++, or Python.

Back to LeetCode Solutions