670. Maximum Swap
Problem Description
In this problem, you are given an integer num
. Your task is to figure out how to make this number the largest possible by swapping any two of its digits. However, you can only do this once. If the number is already the largest it can be, then no swaps are needed. The aim is to find the maximum value that can be created from num
by making at most one swap between any two digits.
Intuition
The intuition behind the solution is to find the first pair of digits where a smaller digit precedes a larger digit when traversing from the rightmost digit towards the left. This guarantees that we will increase the value of the number by swapping a smaller digit in a more significant position with a larger digit in a less significant position.
To achieve this efficiently, we can traverse the numberās digits from right to left and record the index of the largest digit seen so far at each step (called d[i]
in the code). After we have this information, we then traverse the array of digits from left to right, looking for the first digit (s[i]
) that is smaller than the maximum digit that comes after it (s[d[i]]
). When we find such a digit, we perform the swapāan operation that will result in the maximum possible value after the swapāand then convert the list of digits back into an integer. If no such pair of digits is found, it means the number is already at its maximum value, and no swap is performed.
Here's a step-by-step breakdown of the provided code:
- Convert the integer
num
to a list of digit characterss
. - Initialize an array
d
that records the index of the largest digit to the right of each digit, including itself. - Traverse
s
from right to left (excluding the rightmost digit because a single digit can't be swapped), updatingd
such thatd[i]
holds the index of the largest digit to the right ofi
. - Traverse
s
from left to right this time, along withd
. If a digit is found that's smaller than the largest digit to its right (s[d[i]]
), perform a swap and break because further swaps are not allowed. - Join the list of characters
s
back to form the resulting maximum integer and return it.
This approach ensures we only perform a swap that results in the largest possible increase in the number's value, fulfilling the goal of the problem efficiently.
Solution Approach
To implement the solution given in the code, we will use simple list and array manipulation techniques. The procedure follows a greedy algorithm approach because it makes a locally optimal choice at each step that we hope will lead to a globally optimal solution.
Here's the detailed implementation of the solution:
-
Conversion to a list of digits: We start by converting the given integer
num
into a lists
of its digit characters for easy manipulation.s = list(str(num))
-
Initialization of the largest digit indices array: An array
d
is initialized with the same length ass
. Each element at indexi
ofd
is intended to hold the index of the largest digit found to the right ofi
, inclusive ofi
itself.d = list(range(n))
-
Populating the largest digit indices array: We traverse the digits from right to left, updating
d
such thatd[i]
points to the index of the largest digit found fromi
to the end of the list. This step uses dynamic programming to save the index of the largest digit seen so far at each position.for i in range(n - 2, -1, -1): if s[i] <= s[d[i + 1]]: d[i] = d[i + 1]
-
Finding and performing the optimal swap: Once we have our array
d
ready, we traverses
from left to right using enumerate to get both the index and the digit. We look for the first digits[i]
that is smaller than the maximum to its right,s[d[i]]
. When we find such a digit, we swaps[i]
withs[d[i]]
then immediately break the loop as only one swap is allowed.for i, j in enumerate(d): if s[i] < s[j]: s[i], s[j] = s[j], s[i] break
-
Result: The list
s
should now represent the digits of the maximum value we can get. We join the list and convert it back to an integer to return it.return int(''.join(s))
It's worth noting that the traversal from right to left to populate d
and the logic used to decide when to swap are both guided by the algorithm's greediness. Greedy algorithms don't always guarantee an optimal solution for every kind of problem, but in this case, because of the problem's constraints (only one swap allowed), the greedy approach works perfectly to give the maximum value after one swap.
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 num
is 2736
and we want to find the largest number possible by swapping at most one pair of digits.
-
Conversion to a list of digits: We convert
num
to a lists
to get['2', '7', '3', '6']
. -
Initialization of the largest digit indices array: Our array
d
is initialized to be[0, 1, 2, 3]
with the same length ass
, which represents indices of each digit. -
Populating the largest digit indices array: We update
d
by traversing from right to left:Starting from the second to the last index:
- At index 2 (
3
), the largest digit to the right is6
at index 3. So,d[2] = 3
. - At index 1 (
7
),7
is larger than3
, henced[1]
remains1
. - At index 0 (
2
),7
is the largest digit to the right, sod[0] = 1
.
Now
d
is[1, 1, 3, 3]
. - At index 2 (
-
Finding and performing the optimal swap: We use
d
to find the first digit to swap:- At index 0,
s[0] = '2'
is smaller thans[d[0]] = '7'
. So we swaps[0]
withs[1]
and break the loop.
After the swap,
s
becomes['7', '2', '3', '6']
. - At index 0,
-
Result: We join
s
to form7236
, which is returned as the largest number possible after one swap.
Thus, the solution to increase our number 2736
to its maximum by a single swap is to swap the digits 2
and 7
to get 7236
.
Solution Implementation
1class Solution:
2 def maximumSwap(self, num: int) -> int:
3 # Convert the number to a list of its digits in string form.
4 digits = list(str(num))
5 # Get the length of the list of digits.
6 length = len(digits)
7 # Create a list to keep track of the indices of the digits
8 # that should be considered for swapping.
9 max_digit_indices = list(range(length))
10
11 # Populate the max_digit_indices list with the index of the maximum digit
12 # from the current position to the end of the list.
13 for i in range(length - 2, -1, -1):
14 # If the current digit is less than or equal to the maximum digit found
15 # to its right, update the max_digit_indices for the current position.
16 if digits[i] <= digits[max_digit_indices[i + 1]]:
17 max_digit_indices[i] = max_digit_indices[i + 1]
18
19 # Loop through each digit to find the first instance where a swap would
20 # increase the value of the number. Swap and break the loop.
21 for i in range(length):
22 max_index = max_digit_indices[i]
23 # If the current digit is smaller than the maximum digit to its right,
24 # swap the two digits.
25 if digits[i] < digits[max_index]:
26 # Swap the current digit with the maximum digit found.
27 digits[i], digits[max_index] = digits[max_index], digits[i]
28 # Only one swap is needed, so break after swapping.
29 break
30
31 # Convert the list of digits back to a string and then to an integer.
32 return int(''.join(digits))
33
34# The preceding code defines a member function `maximumSwap` within the class `Solution`,
35# which takes an integer `num` and returns the maximum value integer obtained by swapping
36# two digits once.
37
1class Solution {
2 public int maximumSwap(int num) {
3 // Convert the number to a character array to manipulate single digits
4 char[] digits = String.valueOf(num).toCharArray();
5 int length = digits.length;
6 // Initialize an array to hold the indices of the 'max right' elements
7 int[] maxRightIndex = new int[length];
8
9 // Fill the array with the corresponding indices initially
10 for (int i = 0; i < length; ++i) {
11 maxRightIndex[i] = i;
12 }
13
14 // Populate the maxRightIndex array with the index of the greatest digit
15 // to the right of each position i, inclusive
16 for (int i = length - 2; i >= 0; --i) {
17 // Update the index only if the current digit is less than or equal to
18 // the maximum digit to the right
19 if (digits[i] <= digits[maxRightIndex[i + 1]]) {
20 maxRightIndex[i] = maxRightIndex[i + 1];
21 }
22 }
23
24 // Iterate through each digit to find the first occurrence where the current
25 // digit is less than the maximum digit to its right
26 for (int i = 0; i < length; ++i) {
27 int maxIndex = maxRightIndex[i];
28 // If such a digit is found, swap it with the maximum digit to its right
29 if (digits[i] < digits[maxIndex]) {
30 char temp = digits[i];
31 digits[i] = digits[maxIndex];
32 digits[maxIndex] = temp;
33 // Only the first such swap is needed for the maximum number, so break
34 break;
35 }
36 }
37
38 // Convert the modified character array back to an integer and return
39 return Integer.parseInt(new String(digits));
40 }
41}
42
1class Solution {
2public:
3 // This method returns the maximum value by swapping two digits of the given number
4 int maximumSwap(int num) {
5 // Convert the number to a string for easy digit manipulation
6 string numStr = to_string(num);
7 int n = numStr.size(); // Get the length of the string representation of num
8 vector<int> maxIndex(n); // Initialize a vector to store the indices of maximum digits following current
9
10 // Initialize maxIndex with the indices from the string's end to the beginning
11 iota(maxIndex.begin(), maxIndex.end(), 0);
12
13 // Populate the maxIndex vector with the index of the maximum digit from current to the end
14 for (int i = n - 2; i >= 0; --i) {
15 if (numStr[i] <= numStr[maxIndex[i + 1]]) {
16 maxIndex[i] = maxIndex[i + 1];
17 }
18 }
19
20 // Traverse the string and find the first instance where swapping can maximize the number
21 for (int i = 0; i < n; ++i) {
22 int j = maxIndex[i]; // Get the index of the maximum digit we're considering for swap
23 if (numStr[i] < numStr[j]) {
24 // If the current digit is less than the max digit found, then swap and break
25 swap(numStr[i], numStr[j]);
26 break;
27 }
28 }
29
30 // Convert the modified string back to an integer and return it
31 return stoi(numStr);
32 }
33};
34
1function maximumSwap(num: number): number {
2 // Convert the input number into an array of its digits.
3 const digits = [];
4 while (num !== 0) {
5 digits.push(num % 10);
6 num = Math.floor(num / 10);
7 }
8
9 // The length of the digits array.
10 const length = digits.length;
11
12 // An array to store the index of the maximum digit encountered so far from right to left.
13 const maxIndex = new Array(length);
14
15 for (let i = 0, maxDigitIndex = 0; i < length; i++) {
16 // Update the maximum digit index if a larger digit is found.
17 if (digits[i] > digits[maxDigitIndex]) {
18 maxDigitIndex = i;
19 }
20 // Assign the current maximum digit's index to the corresponding position in the array.
21 maxIndex[i] = maxDigitIndex;
22 }
23
24 // Traverse the array from the last (most significant) digit to the first (least significant) digit.
25 for (let i = length - 1; i >= 0; i--) {
26 // Swap the current digit with the largest digit to its right, if there's any.
27 if (digits[maxIndex[i]] !== digits[i]) {
28 [digits[maxIndex[i]], digits[i]] = [digits[i], digits[maxIndex[i]]];
29 // Only the first swap is performed, so we break out of the loop after that.
30 break;
31 }
32 }
33
34 // Reconstruct the number from the array of digits.
35 let resultNum = 0;
36 for (let i = length - 1; i >= 0; i--) {
37 resultNum = resultNum * 10 + digits[i];
38 }
39
40 // Return the final number after performing the maximum swap possible.
41 return resultNum;
42}
43
Time and Space Complexity
The time complexity of the code is O(n)
where n
is the number of digits in the input number. This is because the code consists of two separate for-loops that iterate over the digits. The first loop goes from the second-to-last digit to the first, updating an array of index positions, and the second loop goes once through the digits to find the first swap opportunity. Both loops have a maximum of n
iterations, thus resulting in linear time complexity.
The space complexity of the code is also O(n)
because it stores the digits in a list s
of size n
and another list d
which is also of size n
. Thus the total space used is proportional to the length of the input number.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
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
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
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!