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

HardGreedyBinary Indexed TreeSegment TreeString
Leetcode Link

Problem Description

In this problem, we are given a string num that represents the digits of a very large integer. Additionally, we are provided with an integer k, which represents the maximum number of times we are allowed to swap two adjacent digits in the integer.

The goal is to determine the smallest possible integer that can be formed by making no more than k swaps of adjacent digits, and to return this smallest integer as a string.

The main difficulty of the problem lies in that we must perform the swaps wisely in order to minimize the integer's value, all while ensuring that we do not exceed the limit of k swaps.

Intuition

The intuition behind the solution starts with the observation that, in order to get the smallest number possible, we want to place the smallest digits as early as possible in the number.

To achieve this, we can iterate over the numbers from 0 to 9 and attempt to bring the smallest available digit to the front of the string. Whenever we move a digit to the front, we count how many swaps it took, and subtract that count from k.

However, considering that the string could be very large, directly simulating the swapping process would be inefficient. Instead, we use a data structure called a Binary Indexed Tree (BIT), also known as a Fenwick Tree, to help us efficiently calculate the number of swaps needed.

The BIT helps us in two ways:

  1. It can quickly calculate the cumulative sum of a range, which in our case helps determine how many swaps are needed to bring a digit to a certain position.
  2. It allows us to update the tree efficiently whenever we make a swap.

So, we start with the least significant digit and look for its occurrences in the number. For each occurrence, we calculate how many swaps are needed to bring it to the current position. If this number does not exceed k, we proceed with the swap, update k, update the BIT to account for the digit's new position and then move to the next position.

We maintain a dictionary pos that maps each digit to a queue of positions where that digit occurs. This allows us to quickly find where the smallest available digit is and how many swaps are needed to bring it to the front.

By repeatedly choosing the smallest digit we can afford to move to the current position, we build our minimum number one digit at a time.

The process is repeated until we either construct the entire number or run out of swaps (k becomes 0).

The given solution is quite efficient and is able to handle large inputs within the given constraints.

Solution Approach

The solution uses a Binary Indexed Tree (BIT), also known as a Fenwick Tree, to keep track of the number of swaps and efficiently update and query the data needed for each operation. The BIT is initialized to have a size equal to the number of digits in num.

Here is how the code works, breaking down the key points:

  1. Initialize Position Queues:

    • A defaultdict with deque is used to store queues (pos) representing positions of digits 0-9 within the num string, indexed by their value.
    • We iterate over the num string, and for each digit encountered, we append the position (index + 1 for 1-based indexing) to its respective queue in the pos dictionary.
  2. Binary Indexed Tree (BIT):

    • A helper class BinaryIndexedTree is used to manage a Fenwick Tree. Functions within this class, namely update and query, are created to handle modifications of digit counts and cumulative count queries.
  3. Swapping Procedure:

    • We iterate over the range 1 through the length of num, attempting to place the smallest digit at each position.
    • For each digit (0 through 9):
      • We check if there are any more occurrences of that digit left in the queue (q).
      • If there is an occurrence, we retrieve its index j.
      • Calculate the dist, the number of swaps needed to move our digit at position j to the current position i. The dist is computed as the difference in the number of swaps we would have after moving all digits (tree.query(n)) versus before (tree.query(j)) adjusted by j - i.
      • If the calculated dist is less than or equal to k, this means we are allowed to move this digit to the position i without exceeding our k limit.
      • As we have decided to place this digit in its new position, we subtract dist from k, indicating that we have used some of our allowed swaps.
      • We then remove the position j from the queue for that digit (q.popleft()).
      • Record that digit to our answer list (ans.append(str(v))).
      • Update the BIT by increasing the count at position j to reflect that digit v now occupies the new swapped position (tree.update(j, 1)).
  4. Termination:

    • This process is repeated until all positions have been filled or until we run out of swaps (k becomes 0).
    • The answer list is then concatenated to form the final string representing the smallest possible integer that can be obtained by at most k swaps.

The use of a Fenwick Tree plays a critical role in managing the time complexity of this solution. It allows both the updates (swaps) and queries (the needed count of swaps) to be performed in logarithmic time, which is essential when dealing with potentially very large strings.

Overall, this approach makes the swapping operation more tractable by keeping the complexity manageable. It ensures that the smallest number is formed by doing the least amount of swaps required to bring smaller digits to the forefront of the string.

Note: Although the Reference Solution Approach mentions Segment Tree, the above solution implements a Fenwick Tree instead, which is a simpler form of a Segment Tree and is optimal for this problem as it efficiently calculates prefix sums and updates the tree.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the string num = "935814726" and we can make at most k = 4 swaps.

We'll go through the main steps of the solution approach using this example.

  1. Initialize Position Queues:

    • We parse num and create a dictionary pos, where the keys are the digits '0' through '9' and their values are queues with the indices of their occurrences.
    • For our string, pos will initially look like this:
      1pos = {
      2    '1': deque([5]),
      3    '2': deque([7]),
      4    '3': deque([1]),
      5    '4': deque([4]),
      6    '5': deque([2]),
      7    '6': deque([8]),
      8    '7': deque([6]),
      9    '8': deque([3]),
      10    '9': deque([0])
      11}

    Note that the indices are 0-based for this illustration but will be 1-based in actual implementation.

  2. Binary Indexed Tree (BIT):

    • We instantiate a Binary Indexed Tree of size equal to the length of num.
  3. Swapping Procedure:

    • We will iterate through each position in num, aiming to place the smallest possible digit there.
    • Starting with the first position (index 0), we look for the smallest digit we can afford to move there:
      • For digit '1', the index is 5. The BIT tells us it would require 4 swaps to move '1' to the first position. Since we can make 4 swaps, we do so and decrement k by 4.
      • Now, num looks like this: "153984726", and k is 0.
    • We update our pos and BIT accordingly.
  4. Termination:

    • Since we have exhausted our swaps (k=0), we can no longer perform any swaps.
    • Our answer list so far would be ['1'], and we proceed by appending the remaining untouched digits from num to this list.
    • The final answer list is ['1', '5', '3', '9', '8', '4', '7', '2', '6'].
  5. Result:

    • By joining the answer list, we get our final string, which represents the smallest integer we can make with at most 4 swaps: "153984726".

This example showcases how through the efficient use of a Binary Indexed Tree and position queues, we can minimize a number by making adjacent digit swaps within a given limit.

Python Solution

1from collections import defaultdict
2
3class BinaryIndexedTree:
4    def __init__(self, size):
5        self.size = size
6        self.tree = [0] * (size + 1)  # Original array was named 'c'. Renaming to 'tree' for clarity.
7
8    @staticmethod
9    def lowbit(x):
10        # This method calculates the rightmost bit of 'x' that is 1 and the bits to the right of it zero.
11        return x & -x
12
13    def update(self, index, delta):
14        # Update the Binary Indexed Tree at the given index by the value 'delta'.
15        while index <= self.size:
16            self.tree[index] += delta
17            index += BinaryIndexedTree.lowbit(index)
18
19    def query(self, index):
20        # Calculate the prefix sum from the start of the array up to the given index.
21        sum_value = 0
22        while index:
23            sum_value += self.tree[index]
24            index -= BinaryIndexedTree.lowbit(index)
25        return sum_value
26
27
28class Solution:
29    def minInteger(self, num: str, k: int) -> str:
30        # A defaultdict of deques to store positions of each digit in 'num'.
31        position = defaultdict(deque)
32        for i, digit in enumerate(num, 1):
33            position[int(digit)].append(i)
34        result = []
35        length = len(num)
36
37        # Initialize a Binary Indexed Tree with 'length' as size.
38        bit = BinaryIndexedTree(length)
39
40        for i in range(1, length + 1):
41            # Try each digit from 0 to 9.
42            for digit in range(10):
43                # Queue of positions for the current digit.
44                current_position_queue = position[digit]
45                if current_position_queue:
46                    # Get the position of the first occurrence of the digit.
47                    j = current_position_queue[0]
48                    # Calculate distance to bring the digit at position 'j' to the front.
49                    distance = bit.query(length) - bit.query(j) + j - i
50                    if distance <= k:
51                        # If the distance is less than or equal to 'k', we can swap the digit to the front.
52                        k -= distance
53                        current_position_queue.popleft()  # Remove the digit from its current queue.
54                        result.append(str(digit))  # Append the digit to the result.
55                        bit.update(j, 1)  # Update the Binary Indexed Tree for the new position.
56                        break  # Move to the next position.
57
58        # Join the list of strings in 'result' to form the final answer.
59        return ''.join(result)
60

Java Solution

1class Solution {
2    public String minInteger(String num, int k) {
3        // Array of queues to store positions of digits 0-9 in the string
4        Queue<Integer>[] digitPositions = new Queue[10];
5        for (int i = 0; i < 10; ++i) {
6            digitPositions[i] = new ArrayDeque<>();
7        }
8        // Store all digit positions
9        int length = num.length();
10        for (int i = 0; i < length; ++i) {
11            int digitValue = num.charAt(i) - '0';
12            digitPositions[digitValue].offer(i + 1);
13        }
14        // StringBuilder to create result string
15        StringBuilder result = new StringBuilder();
16        // Binary Indexed Tree to maintain prefix sums efficiently
17        BinaryIndexedTree bit = new BinaryIndexedTree(length);
18        // Iterate over each position in the result string we are building
19        for (int i = 1; i <= length; ++i) {
20            // Check each digit from 0 to 9 to find the smallest digit we can place at position i
21            for (int digit = 0; digit < 10; ++digit) {
22                if (!digitPositions[digit].isEmpty()) {
23                    int positionInNUM = digitPositions[digit].peek();
24                    int adjustment = bit.query(length) - bit.query(positionInNUM) + positionInNUM - i;
25                    // If we can "afford" to move the digit into the current position i within k moves,
26                    // do so and update 'k', the tree, and our result string.
27                    if (adjustment <= k) {
28                        k -= adjustment;
29                        digitPositions[digit].poll();
30                        result.append(digit);
31                        bit.update(positionInNUM, 1);
32                        break;
33                    }
34                }
35            }
36        }
37        return result.toString();
38    }
39}
40
41class BinaryIndexedTree {
42    private int[] binaryIndexedTree;
43    private int size;
44
45    public BinaryIndexedTree(int size) {
46        this.size = size;
47        this.binaryIndexedTree = new int[size + 1];
48    }
49
50    // Updates the Binary Indexed Tree with the given 'delta' value at 'index'.
51    public void update(int index, int delta) {
52        while (index <= size) {
53            binaryIndexedTree[index] += delta;
54            index += lowBit(index);
55        }
56    }
57
58    // Computes and returns the prefix sum up to and including 'index'.
59    public int query(int index) {
60        int sum = 0;
61        while (index > 0) {
62            sum += binaryIndexedTree[index];
63            index -= lowBit(index);
64        }
65        return sum;
66    }
67
68    // Helper method to calculate the least significant bit that is set to '1'.
69    private static int lowBit(int x) {
70        return x & -x;
71    }
72}
73

C++ Solution

1#include <vector>
2#include <queue>
3#include <string>
4
5// Binary Indexed Tree (Fenwick Tree) class for range sum queries and single element updates.
6class BinaryIndexedTree {
7public:
8    // n represents the size of the array and c is the internal BIT.
9    int size;
10    std::vector<int> bit;
11
12    // Constructor that initializes the BIT with the given size.
13    BinaryIndexedTree(int n)
14        : size(n)
15        , bit(n + 1) {}
16
17    // Updates the value at index x by delta.
18    void update(int x, int delta) {
19        while (x <= size) {
20            bit[x] += delta;
21            x += lowBit(x);
22        }
23    }
24
25    // Queries the prefix sum upto index x.
26    int query(int x) {
27        int sum = 0;
28        while (x > 0) {
29            sum += bit[x];
30            x -= lowBit(x);
31        }
32        return sum;
33    }
34
35    // Utility function to get the lowest one bit of x.
36    int lowBit(int x) {
37        return x & -x;
38    }
39};
40
41class Solution {
42public:
43    // Given a string `num` and an integer `k`, returns the lexicographically 
44    // smallest string you could form by applying the operation at most `k` times.
45    std::string minInteger(std::string num, int k) {
46        // Vector of queues to store positions of each digit in the input number.
47        std::vector<std::queue<int>> pos(10);
48        int n = num.size();
49        // Fill the queues with the positions of corresponding digits.
50        for (int i = 0; i < n; ++i) {
51            pos[num[i] - '0'].push(i + 1);
52        }
53
54        // Initialize a Binary Indexed Tree.
55        BinaryIndexedTree tree(n);
56        // This will hold the result, the lexicographically smallest string.
57        std::string ans = "";
58
59        // Start forming the smallest number by selecting digits in increasing order.
60        for (int i = 1; i <= n; ++i) {
61            for (int digitValue = 0; digitValue < 10; ++digitValue) {
62                auto& q = pos[digitValue];
63                // Check if there are positions left for the current digit.
64                if (!q.empty()) {
65                    // Get the nearest occurrence of the current digit.
66                    int index = q.front();
67                    // Calculate the cost of moving the digit to the current position.
68                    int dist = tree.query(n) - tree.query(index) + index - i;
69                    if (dist <= k) {
70                        // If the cost is within the allowed operations 'k',
71                        // choose this digit, remove it from the queue and
72                        // update the BIT and ans string respectively.
73                        k -= dist;
74                        q.pop();
75                        ans += (digitValue + '0');
76                        tree.update(index, 1);
77                        break;
78                    }
79                }
80            }
81        }
82        return ans;
83    }
84};
85

Typescript Solution

1// TypeScript does not natively support <vector> or <queue> like C++, so we would need to use
2// arrays and manual queue management techniques.
3
4// Binary Indexed Tree (Fenwick Tree) for range sum queries and single element updates.
5let size: number;
6let bit: number[];
7
8// Initialize the BIT with the given size `n`.
9function initializeBIT(n: number): void {
10    size = n;
11    bit = Array(n + 1).fill(0);
12}
13
14// Update the value at index `x` by `delta`.
15function update(x: number, delta: number): void {
16    while (x <= size) {
17        bit[x] += delta;
18        x += lowBit(x);
19    }
20}
21
22// Query the prefix sum up to index `x`.
23function query(x: number): number {
24    let sum = 0;
25    while (x > 0) {
26        sum += bit[x];
27        x -= lowBit(x);
28    }
29    return sum;
30}
31
32// Utility function to get the lowest one bit of `x`.
33function lowBit(x: number): number {
34    return x & -x;
35}
36
37// Given a string `num` and an integer `k`, returns the lexicographically
38// smallest string you could form by applying the operation at most `k` times.
39function minInteger(num: string, k: number): string {
40    // Array of queues to store positions of each digit in the input number.
41    let pos: number[][] = Array.from({ length: 10 }, () => []);
42    let n: number = num.length;
43
44    // Fill the arrays with the positions of the corresponding digits.
45    num.split('').forEach((digit, index) => {
46        pos[parseInt(digit)].push(index + 1);
47    });
48
49    // Initialize the Binary Indexed Tree.
50    initializeBIT(n);
51    // Will hold the result, the lexicographically smallest string.
52    let ans: string = "";
53
54    // Start forming the smallest number by selecting digits in increasing order.
55    for (let i = 1; i <= n; ++i) {
56        for (let digitValue = 0; digitValue < 10; ++digitValue) {
57            let q = pos[digitValue];
58            // Check if there are positions left for the current digit.
59            if (q.length > 0) {
60                // Get the nearest occurrence of the current digit.
61                let index = q[0];
62                // Calculate the cost of moving the digit to the current position.
63                let dist = query(n) - query(index) + index - i;
64                if (dist <= k) {
65                    // If the cost is within the allowed operations `k`,
66                    // choose this digit, remove it from the array and
67                    // update the BIT and `ans` string respectively.
68                    k -= dist;
69                    q.shift();
70                    ans += digitValue.toString();
71                    update(index, 1);
72                    break;
73                }
74            }
75        }
76    }
77    return ans;
78}
79
80// Usage
81const result = minInteger("4321", 4);
82console.log(result); // Output should be the lexicographically smallest string after operations.
83

Time and Space Complexity

The provided code involves a number of different operations whose complexities need to be considered separately. After breaking down the code, the following are the time complexity and space complexity analyses:

  1. Initialization of BinaryIndexedTree:

    • Time Complexity: O(n) since it initializes an array of n+1 elements to 0.
    • Space Complexity: O(n) for the storage of the c array.
  2. Update and Query Operations in BinaryIndexedTree:

    • Both update and query operations have a loop that runs proportional to the number of bits in the index, which is O(log n) in the worst case.
    • Since update and query are called multiple times, we will account for them in the overall complexity.
  3. Main loop in Solution.minInteger method:

    • There is a nested loop, where the outer loop runs n times and the inner loop runs up to 10 times (constant).
    • Within the inner loop, the update operation which is O(log n), and the query operation which is also O(log n), are called once each iteration when a suitable digit is found.
  4. Complexity of managing the pos dictionary:

    • The pos dictionary stores lists of positions for each digit. The positions are stored using a deque, which allows O(1) insertion and removal from both ends.

Considering all of the above, we can derive the overall complexities as follows:

  • Overall Time Complexity: The nested loop gives us O(10 * n * log n). Since 10 is a constant, we can simplify this to O(n log n) which is the dominant factor in the time complexity.

  • Overall Space Complexity:

    • The pos dictionary stores up to n values for each of 10 digits, leading to O(10n) which is equivalent to O(n) when constants are ignored.
    • The ans list also grows to hold n characters, so it contributes O(n).
    • The BinaryIndexedTree contributes another O(n) space. Combining these factors, the overall space complexity is O(n).

In conclusion, the computation complexity for the code is:

  • Time Complexity: O(n log n)
  • Space Complexity: O(n)
😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫