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 Possible Integer After at Most K Adjacent Swaps On Digits

Number: 1629

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string num representing the digits of a very large integer and an integer k, you are allowed to swap any two adjacent digits at most k times. The goal is to return the minimum integer possible (as a string) by performing at most k adjacent swaps.

Key Insights

  • Only adjacent swaps are allowed so the cost to move a digit from index j to index i is (j - i).
  • A greedy strategy works: for each position, choose the smallest digit within the next reachable range (i.e. positions [i, i+k]).
  • Once a digit is selected, update k to account for the swaps used.
  • Efficient implementations for large input sizes may employ data structures like a Binary Indexed Tree or Segment Tree to account for swaps in a more optimal manner.
  • Leading zeros in the result are acceptable even though the input has no leading zeros.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case greedy approach, though it can be optimized to O(n log n) using advanced data structures. Space Complexity: O(n), where n is the number of digits.

Solution

The solution is based on a greedy approach. Iterate over the digits of the number and for each position, look ahead as far as the current remaining swaps (i.e. positions i to min(n-1, i+k)). Identify the smallest digit in that range which can be swapped to the current position. The cost to bring a digit from its current position j to the target i is (j-i) swaps. Deduct that cost from k and continue to the next position. This ensures that at each step we are placing the best possible digit that can be brought from the right while staying within the swap limit.
Data structures used are basic array operations; no extra advanced structures are strictly necessary for this greedy solution. However, for performance improvements on larger inputs, one might use a Binary Indexed Tree (Fenwick Tree) or Segment Tree.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Function to find minimum integer after at most k adjacent swaps on digits
def minInteger(num, k):
    # Convert string to list for mutable operations
    digits = list(num)
    n = len(digits)
    
    # Iterate over each index of the digits list
    for i in range(n):
        # Determine the limit for searching: we cannot move a digit more than k positions,
        # so we search from i to the smaller of (n-1) or (i + k)
        pos = i
        for j in range(i+1, min(n, i+k+1)):
            # Select the smallest digit among digits[i...i+k]
            if digits[j] < digits[pos]:
                pos = j
        # The number of swaps required to move the selected digit to index i
        swaps = pos - i
        # Deduct the swaps used from k
        k -= swaps
        # Bring the selected digit to position i by shifting the intermediate digits rightwards
        while pos > i:
            digits[pos], digits[pos-1] = digits[pos-1], digits[pos]
            pos -= 1
        # Early exit if no swaps remain
        if k <= 0:
            break
    # Return the resulting list as a string
    return ''.join(digits)

# Example usage:
print(minInteger("4321", 4))  # Expected output: "1342"
print(minInteger("100", 1))   # Expected output: "010"
print(minInteger("36789", 1000))   # Expected output: "36789"
← Back to All Questions