Minimum Adjacent Swaps to Reach the Kth Smallest Number

Medium

Asked by:

17 views

Topics:

StringsArraysGreedy Algorithms

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

For example, when num = "5489355142":
- The 1^st smallest wonderful integer is "5489355214".
- The 2^nd smallest wonderful integer is "5489355241".
- The 3^rd smallest wonderful integer is "5489355412".
- The 4^th smallest wonderful integer is "5489355421".

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.

The tests are generated in such a way that k^th smallest wonderful integer exists.

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4^th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355142" -> "5489355412"
- Swap index 8 with index 9: "5489355412" -> "5489355421"

Example 2:

Input: num = "11112", k = 4
Output: 4
Explanation: The 4^th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "11112" -> "11121"
- Swap index 2 with index 3: "11121" -> "11211"
- Swap index 1 with index 2: "11211" -> "12111"
- Swap index 0 with index 1: "12111" -> "21111"

Example 3:

Input: num = "00123", k = 1
Output: 1
Explanation: The 1^st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -> "00132"

Constraints:

2 <= num.length <= 1000
1 <= k <= 1000
num only consists of digits.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of `k` relative to the length of the input string `num`? Could `k` be larger than the total number of permutations?
Can the input string `num` contain leading zeros?
Are all the characters in the input string `num` guaranteed to be distinct digits, or can there be duplicates?
If the `k`th smallest number is the same as the original number, should I return 0?
What data type should I use for counting swaps if the number of swaps could be very large?

Brute Force Solution

Approach

The brute force strategy finds the Kth smallest number by generating all possible number arrangements. For each arrangement, it determines the number of swaps needed to transform the original number into that arrangement. Finally, it identifies the Kth smallest arrangement and its corresponding swap count.

Here's how the algorithm would work step-by-step:

First, create all possible arrangements of the digits of the given number. Think of it like shuffling a deck of cards to get all the possible orders.
For each of these arrangements, compare it to the original number to figure out how many swaps it would take to turn the original number into the current arrangement.
Keep track of all the arrangements and their corresponding swap counts.
Sort the arrangements based on their value (the number they represent), smallest to largest.
Once sorted, find the Kth arrangement in the sorted list.
The swap count associated with that Kth arrangement is the answer.

Code Implementation

from itertools import permutations

def minimum_adjacent_swaps_to_reach_kth_smallest_number(number, k):
    number_string = str(number)
    digits = list(number_string)
    all_permutations = list(permutations(digits))

    arrangements_with_swaps = []
    for permutation_tuple in all_permutations:
        arrangement = "".join(permutation_tuple)
        swap_count = 0
        temp_digits = list(number_string)
        
        # Calculate swaps needed to transform the original number
        for i in range(len(digits)):
            if temp_digits[i] != arrangement[i]:
                j = i + 1
                while j < len(digits) and temp_digits[j] != arrangement[i]:
                    j += 1

                if j < len(digits): 
                    # Perform necessary swaps to match digits
                    for l in range(j, i, -1):
                        temp_digits[l], temp_digits[l-1] = temp_digits[l-1], temp_digits[l]
                        swap_count += 1

        arrangements_with_swaps.append((arrangement, swap_count))

    # Sort arrangements based on their numerical value
    arrangements_with_swaps.sort(key=lambda x: int(x[0]))
    
    # The kth smallest number's swap count is the answer
    kth_smallest_arrangement = arrangements_with_swaps[k - 1]
    return kth_smallest_arrangement[1]

Big(O) Analysis

Time Complexity

O(n! * n log n) – Generating all permutations of an n-digit number takes O(n!) time because there are n! possible arrangements. For each permutation, calculating the number of swaps needed takes O(n) in the worst case since we may need to iterate through all digits to find the correct position to swap. Sorting the permutations, which are n! in number, takes O(n! log(n!)) time. Since log(n!) is approximately n log n (by Stirling's approximation), the sorting step can be seen as O(n! * n log n). The dominant operation is the generation and processing of all permutations, where each swap calculation and the sorting takes place, therefore the complexity simplifies to O(n! * n log n).

Space Complexity

O(N! * N) – The brute force solution generates all permutations of the input number's digits. There are N! such permutations, where N is the number of digits. Each permutation is stored as a string of length N. Therefore, storing all permutations requires O(N! * N) space. Additionally, a sorting algorithm is used which might use O(N! * log(N!)) space in the worst-case for comparison-based sorting (although in-place sorting is possible). However, the storage of all permutations dominates the space complexity.

Optimal Solution

Approach

The goal is to find the specific number that is the Kth smallest rearrangement of the digits of the original number and then to count the fewest swaps to achieve it. We can find the Kth smallest by generating permutations in lexicographical order without generating all possible permutations. After finding this Kth smallest number, we directly compute the minimum swaps needed to reach it from the original.

Here's how the algorithm would work step-by-step:

Calculate the Kth smallest permutation of the digits of the original number. We don't generate *all* permutations. We incrementally determine the digits from left to right.
To find each digit, we count how many permutations start with each of the remaining digits (digits not yet used).
The Kth smallest permutation will start with the digit that corresponds to the right count. Update K to reflect the remaining permutations we still need to traverse.
Once we have the Kth smallest permutation, we compare it to the original number, digit by digit, from left to right.
For each digit in the original number, find the first matching digit in the Kth smallest permutation, located at or after the current place.
Swap the digits between the current place in the original number and the location of the matching digit in the Kth smallest permutation, keeping track of the swap count.
Repeat until the original number is transformed into the Kth smallest permutation.

Code Implementation

def minimum_adjacent_swaps_to_reach_the_kth_smallest_number(number_string, k_value):
    number_list = list(number_string)
    number_length = len(number_list)

    kth_smallest_number = find_kth_smallest_permutation(number_list, k_value)

    swap_count = 0
    for i in range(number_length):
        if number_list[i] != kth_smallest_number[i]:
            j = i + 1
            while number_list[j] != kth_smallest_number[i]:
                j += 1

            # Find the position of the digit that should be at the current index
            while j > i:
                number_list[j], number_list[j - 1] = number_list[j - 1], number_list[j]
                swap_count += 1
                j -= 1

    return swap_count

def find_kth_smallest_permutation(number_list, k_value):
    number_length = len(number_list)
    available_digits = number_list[:]
    result = []
    k_value -= 1

    for _ in range(number_length):
        number_of_permutations_starting_with_digit = factorial(len(available_digits) - 1)

        # Determine which digit to use at the current position
        index = k_value // number_of_permutations_starting_with_digit
        digit = available_digits[index]
        result.append(digit)
        available_digits.remove(digit)
        k_value %= number_of_permutations_starting_with_digit

    return result

def factorial(number):
    if number == 0:
        return 1
    else:
        result = 1
        for i in range(1, number + 1):
            result *= i
        return result

Big(O) Analysis

Time Complexity

O(n²) – The algorithm consists of two main parts: finding the Kth smallest permutation and swapping digits. Finding the Kth smallest permutation involves iterating through the digits of the input number (of length n) and calculating permutation counts. The swap part involves iterating through each digit of the original number (n) and, for each, searching at most n digits in the Kth smallest permutation to find a match. In the worst case, for each of the n digits, we might iterate up to n times in the inner loop. This leads to approximately n * n/2 operations, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm primarily uses space to store the Kth smallest permutation of the digits. This permutation is stored as a string or a list of digits, requiring space proportional to the number of digits in the original number, which we denote as N. Additionally, intermediate variables are used during the permutation finding process. Therefore, the overall auxiliary space is O(N).

Edge Cases

Case	How to Handle
Null input string	Throw an IllegalArgumentException or return an appropriate error value like -1 to indicate invalid input.
Empty input string	Return 0, as no swaps are needed to reach the 'kth' permutation of an empty string which only has one permutation.
k is zero or negative	Return 0, as the 0th smallest element is the original string.
k is larger than the total number of permutations	Return -1 or throw an exception since the Kth permutation can not be found.
Input string with all identical characters	Return 0 immediately, as no swaps are required to obtain any permutation because all permutations are identical.
Integer overflow when calculating factorials (used to determine the Kth permutation)	Use long data types for factorial calculations and check for overflow conditions, potentially using a BigInteger class if long isn't sufficient.
Large input string (performance consideration)	Ensure the algorithm has a time complexity that scales reasonably; optimizing permutation generation and swap counting are crucial.
String with duplicate characters affecting permutation order	Account for duplicate characters by dividing factorial results by the factorial of the counts of each duplicate character when determining which digit to select for the Kth permutation.

Null input string

How to Handle:

Throw an IllegalArgumentException or return an appropriate error value like -1 to indicate invalid input.

Empty input string

How to Handle:

Return 0, as no swaps are needed to reach the 'kth' permutation of an empty string which only has one permutation.

k is zero or negative

How to Handle:

Return 0, as the 0th smallest element is the original string.

k is larger than the total number of permutations

How to Handle:

Return -1 or throw an exception since the Kth permutation can not be found.

Input string with all identical characters

How to Handle:

Return 0 immediately, as no swaps are required to obtain any permutation because all permutations are identical.

Integer overflow when calculating factorials (used to determine the Kth permutation)

How to Handle:

Use long data types for factorial calculations and check for overflow conditions, potentially using a BigInteger class if long isn't sufficient.

Large input string (performance consideration)

How to Handle:

Ensure the algorithm has a time complexity that scales reasonably; optimizing permutation generation and swap counting are crucial.

String with duplicate characters affecting permutation order

How to Handle:

Account for duplicate characters by dividing factorial results by the factorial of the counts of each duplicate character when determining which digit to select for the Kth permutation.