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:
- 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.
- 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:
-
Initialize Position Queues:
- A defaultdict with
deque
is used to store queues (pos
) representing positions of digits 0-9 within thenum
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 thepos
dictionary.
- A defaultdict with
-
Binary Indexed Tree (BIT):
- A helper class
BinaryIndexedTree
is used to manage a Fenwick Tree. Functions within this class, namelyupdate
andquery
, are created to handle modifications of digit counts and cumulative count queries.
- A helper class
-
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 positionj
to the current positioni
. Thedist
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 byj - i
. - If the calculated
dist
is less than or equal tok
, this means we are allowed to move this digit to the positioni
without exceeding ourk
limit. - As we have decided to place this digit in its new position, we subtract
dist
fromk
, 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 digitv
now occupies the new swapped position (tree.update(j, 1)
).
- We check if there are any more occurrences of that digit left in the queue (
- We iterate over the range 1 through the length of
-
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.
- This process is repeated until all positions have been filled or until we run out of 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
Initialize Position Queues:
- We parse
num
and create a dictionarypos
, 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:pos = { '1': deque([5]), '2': deque([7]), '3': deque([1]), '4': deque([4]), '5': deque([2]), '6': deque([8]), '7': deque([6]), '8': deque([3]), '9': deque([0]) }
Note that the indices are 0-based for this illustration but will be 1-based in actual implementation.
- We parse
-
Binary Indexed Tree (BIT):
- We instantiate a Binary Indexed Tree of size equal to the length of
num
.
- We instantiate a Binary Indexed Tree of size equal to the length of
-
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", andk
is 0.
- 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
- We update our
pos
and BIT accordingly.
- We will iterate through each position in
-
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 fromnum
to this list. - The final answer list is
['1', '5', '3', '9', '8', '4', '7', '2', '6']
.
-
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
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
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
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
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:
-
Initialization of
BinaryIndexedTree
:- Time Complexity:
O(n)
since it initializes an array ofn+1
elements to0
. - Space Complexity:
O(n)
for the storage of thec
array.
- Time Complexity:
-
Update and Query Operations in
BinaryIndexedTree
:- Both
update
andquery
operations have a loop that runs proportional to the number of bits in the index, which isO(log n)
in the worst case. - Since
update
andquery
are called multiple times, we will account for them in the overall complexity.
- Both
-
Main loop in
Solution.minInteger
method:- There is a nested loop, where the outer loop runs
n
times and the inner loop runs up to10
times (constant). - Within the inner loop, the
update
operation which isO(log n)
, and thequery
operation which is alsoO(log n)
, are called once each iteration when a suitable digit is found.
- There is a nested loop, where the outer loop runs
-
Complexity of managing the
pos
dictionary:- The
pos
dictionary stores lists of positions for each digit. The positions are stored using adeque
, which allowsO(1)
insertion and removal from both ends.
- The
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)
. Since10
is a constant, we can simplify this toO(n log n)
which is the dominant factor in the time complexity. -
Overall Space Complexity:
- The
pos
dictionary stores up ton
values for each of10
digits, leading toO(10n)
which is equivalent toO(n)
when constants are ignored. - The
ans
list also grows to holdn
characters, so it contributesO(n)
. - The
BinaryIndexedTree
contributes anotherO(n)
space. Combining these factors, the overall space complexity isO(n)
.
- The
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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!