We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Adjacent Swaps to Reach the Kth Smallest Number

Number: 1978

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a string num representing a large integer and an integer k, determine the minimum adjacent swaps needed to transform num into the kth smallest "wonderful" number. A "wonderful" number is defined as a permutation of the digits of num that is strictly greater than num. The kth smallest wonderful number is the kth permutation in increasing order among all those that are greater than num.

Key Insights

  • The kth smallest wonderful number can be obtained by performing the next permutation operation on num exactly k times.
  • After finding the target permutation, the problem reduces to counting how many adjacent swaps are needed to transform the original num into this target.
  • A greedy approach is used to simulate the swaps: for each position, locate the required digit in the original list and swap it leftwards one step at a time until it reaches its target position.
  • Care must be taken when swapping duplicate digits, ensuring we always pick the correct occurrence for minimal swaps.

Space and Time Complexity

Time Complexity: O(k * n + n^2) where n is the length of the num string. The O(k * n) comes from generating the kth permutation, and the O(n^2) comes from counting the swaps. Space Complexity: O(n) due to the additional lists used for simulation.

Solution

The solution involves two main steps:

  1. Finding the kth smallest wonderful number from num by performing k iterations of the next permutation algorithm. The next permutation algorithm involves:
    • Scanning from right to left to find the first digit that is smaller than its right neighbor.
    • Finding the smallest digit on its right that is larger than this digit.
    • Swapping them and then reversing the substring to the right of the initial index.
  2. Once the target permutation is found, count the minimum number of adjacent swaps required to convert the original num into this permutation. For every position, find the corresponding digit in the current num (taking into account previous swaps) and swap it leftwards until it reaches its correct place, accumulating the total count.

Data structures used include a mutable list of characters to allow in-place swapping. The greedy adjacent swapping simulation ensures we always make the minimal swaps needed by moving the correct digit into place one adjacent swap at a time.

Code Solutions

# Python solution for Minimum Adjacent Swaps to Reach the Kth Smallest Number

def getMinSwaps(num: str, k: int) -> int:
    # Convert input string to list for mutable operations
    original = list(num)
    target = list(num)
    
    # Function to get the next permutation (in-place modification)
    def next_permutation(arr):
        i = len(arr) - 2
        # Step 1: Find the first digit that is smaller than its successor
        while i >= 0 and arr[i] >= arr[i + 1]:
            i -= 1
        if i >= 0:
            j = len(arr) - 1
            # Step 2: Find the smallest digit on right side of arr[i] that is larger than arr[i]
            while arr[j] <= arr[i]:
                j -= 1
            # Swap the found digits
            arr[i], arr[j] = arr[j], arr[i]
        # Step 3: Reverse the sub-array to the right of index i
        arr[i + 1:] = reversed(arr[i + 1:])
    
    # Get the kth permutation by applying next_permutation k times
    for _ in range(k):
        next_permutation(target)
    
    swaps = 0
    # Count the minimum adjacent swaps required to transform original into target
    for i in range(len(target)):
        if original[i] != target[i]:
            j = i
            # Find the position in original where target[i] is located
            while original[j] != target[i]:
                j += 1
            # Swap the found digit leftwards until it reaches position i
            while j > i:
                original[j], original[j - 1] = original[j - 1], original[j]
                swaps += 1
                j -= 1
    return swaps

# Example test cases
print(getMinSwaps("5489355142", 4))  # Expected output: 2
print(getMinSwaps("11112", 4))       # Expected output: 4
print(getMinSwaps("00123", 1))       # Expected output: 1
← Back to All Questions