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

HardGreedyBinary Indexed TreeSegment TreeString

Problem: #1505
Pattern: Greedy
Reading time: 7 min
Source: leetcode.com

The 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.

Example

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

Python solution

Python

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def minInteger(self, num: str, k: int) -> str:
        pos = defaultdict(deque)
        for i, v in enumerate(num, 1):
            pos[int(v)].append(i)
        ans = []
        n = len(num)
        tree = BinaryIndexedTree(n)
        for i in range(1, n + 1):
            for v in range(10):
                q = pos[v]
                if q:
                    j = q[0]
                    dist = tree.query(n) - tree.query(j) + j - i
                    if dist <= k:
                        k -= dist
                        q.popleft()
                        ans.append(str(v))
                        tree.update(j, 1)
                        break
        return ''.join(ans)

Complexity

Measure	Complexity
Time	O(n log n)
Space	O(1) to O(n) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits?: LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits is rated Hard on LeetCode.
What topics does LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits cover?: LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits is tagged Greedy, Binary Indexed Tree, Segment Tree and String on LeetCode.