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

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.

Learn more about Greedy and Segment Tree patterns.

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.

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.

Solution Implementation

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)

Learn more about how to find time and space complexity quickly using problem constraints.