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:

1. Convert the integer num to a list of digit characters s.
2. Initialize an array d that records the index of the largest digit to the right of each digit, including itself.
3. Traverse s from right to left (excluding the rightmost digit because a single digit can't be swapped), updating d such that d[i] holds the index of the largest digit to the right of i.
4. Traverse s from left to right this time, along with d. 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.
5. 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.

Learn more about Greedy and Math patterns.

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:

1. Conversion to a list of digits: We start by converting the given integer num into a list s of its digit characters for easy manipulation.

   1s = list(str(num))

2. Initialization of the largest digit indices array: An array d is initialized with the same length as s. Each element at index i of d is intended to hold the index of the largest digit found to the right of i, inclusive of i itself.

   1d = list(range(n))

3. Populating the largest digit indices array: We traverse the digits from right to left, updating d such that d[i] points to the index of the largest digit found from i 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.

   1for i in range(n - 2, -1, -1):
   2    if s[i] <= s[d[i + 1]]:
   3        d[i] = d[i + 1]

4. Finding and performing the optimal swap: Once we have our array d ready, we traverse s from left to right using enumerate to get both the index and the digit. We look for the first digit s[i] that is smaller than the maximum to its right, s[d[i]]. When we find such a digit, we swap s[i] with s[d[i]] then immediately break the loop as only one swap is allowed.

   1for i, j in enumerate(d):
   2    if s[i] < s[j]:
   3        s[i], s[j] = s[j], s[i]
   4        break

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

   1return 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.

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

1. Conversion to a list of digits: We convert num to a list s to get ['2', '7', '3', '6'].

2. Initialization of the largest digit indices array: Our array d is initialized to be [0, 1, 2, 3] with the same length as s, which represents indices of each digit.

3. 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 is 6 at index 3. So, d[2] = 3.
   • At index 1 (7), 7 is larger than 3, hence d[1] remains 1.
   • At index 0 (2), 7 is the largest digit to the right, so d[0] = 1.

   Now d is [1, 1, 3, 3].

4. Finding and performing the optimal swap: We use d to find the first digit to swap:

   • At index 0, s[0] = '2' is smaller than s[d[0]] = '7'. So we swap s[0] with s[1] and break the loop.

   After the swap, s becomes ['7', '2', '3', '6'].

5. Result: We join s to form 7236, 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

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.