Smallest Integer After K Adjacent Swaps

The idea behind the greedy approach:

• The most significant (leftmost) digit should be the minimum of the first ‘K + 1’ digits (given that ‘K + 1 <= N’).
• If there are multiple such values, then we must swap the leftmost digit (let’s say at index ‘ID’), as it would consume less number of swaps.
• After that, swap the digits from ‘ID’ to the leftmost digit one by one, such that the digit at ‘ID’ becomes the leftmost digit.
  • Update the value of ‘K’ accordingly and perform the same steps for each digit until we reach the last digit or ‘K’ is exhausted.

We need two levels of loops, the outer loop to traverse the integer ‘NUM’, and the inner (nested) loop to find the smallest leftmost digit among the next ‘K’ digits and swap the digits in between.

Algorithm:

• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
  • Set ‘index = i’.
  • Run a loop where ‘j’ ranges from ‘i + 1’ to ‘K - 1’:
    • If ‘K < j - i’, then the digit at ‘j’ needs more than ‘K’ swaps to move to position ‘i’:
      • Break the loop.
    • If ‘NUM[index] > NUM[j]’, then update ‘index’ as the digit at ‘j’ is smaller than the digit at ‘index’:
      • ‘index = j’.
  • Run a loop where ‘j’ ranges from ‘index’ to ‘i’, to swap the digits between ‘index’ to ‘i’:
    • ‘swap(NUM[j], NUM[j - i])’.
  • ‘K -= (index - i)’. The number of swaps to move ‘NUM[index]’ to position ‘i’.
• Return ‘NUM’ as the answer.

We use ten stacks ‘POS[10]’ (using array implementation) to store the indexes of digits from ‘0’ to ‘9’. The stack ‘POS[i]’ stores the indexes of the digit ‘i’ in descending order where the back of the array/top of the stack is the leftmost (smallest) index. This can be achieved by traversing ‘NUM’ in reverse, and for every index ‘i’ push ‘i’ into ‘POS[NUM[i]]’. 

Prerequisite: Lower bound. To count the number of elements smaller or equal in a sorted array.
 

The number of digits ‘i’ to the left of an index ‘ID’ in ‘NUM’ can be found by doing a binary search to count the number of elements in ‘POS[i]’, which are smaller than ‘ID’. If we do this for all the digits from ‘0’ to ‘9’, we can find the number of digits to the left of index ‘ID’.

Create an empty string ‘RES’ to store the minimum possible number. As per the previous approach, the most significant (leftmost) digit should be the minimum of the first ‘K + 1’ digits (given that ‘K + 1 <= N’). So, starting to traverse ‘POS’ from ‘0’ to ‘9’ until we find a digit ‘D’ that has not more than ‘K’ digits to its left. When we find ‘D’, append ‘D’ to the ‘res’, mark the location of ‘D’ in ‘NUM’, update the value of ‘K’, and pop ‘POS[D]’. If all the stacks become empty before performing the ‘K’ swaps, then ‘RES’ stores the answer.
 

Otherwise, after the ‘K’ swaps are exhausted, append the unmarked digits from ‘0’ to ‘N - 1’ for ‘NUM’ to ‘RES’ (as we always swap the digits from right to left the order of unmarked digits in the final answer and ‘NUM’ is the same).
 

Algorithm:

• Create ten arrays ‘pos[10]’ and use them as a stack. Here, ‘pos[i]’ will store the indexes of digit ‘i’.
• Run a loop where ‘i’ ranges from ‘N - 1’ to ‘0’:
  • ‘pos[NUM[i]].push(i)’.
• Create a string ‘res’ to store the answer.
• Initialize a boolean array ‘seen[n]’ set to ‘False’. Use it to track the indexes that have been inserted into ‘res’.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
  • If ‘K = 0’, then we cannot do any more swaps:
    • Break the loop.
  • Run a loop where ‘d’ ranges from ‘0’ to ‘9’, to find the smallest leftmost digit after ‘i’:
    • If the stack ‘pos[d]’ is empty, then there are no more digits ‘d’:
      • Continue the loop.
    • Set ‘cur = pos[d].top()’. Index of the leftmost digit ‘d’ after ‘i’.
    • Set ‘count = 0’. Use it to count the number of swaps required to move ‘NUM[cur]’ to index ‘i’.
    • Run a loop where ‘j’ ranges from ‘0’ to ‘9’, to count the digits between ‘i’ and ‘cur’:
      • If ‘d != j’, then (as ‘NUM[cur]’ is the first digit ‘d’ after ‘i’):
        • ‘count += pos[j].top() - lower_bound(pos[j], cur)’. The number of ‘d’ digits between ‘cur’ and ‘i’.
    • If ‘count <= k’, then:
      • ‘res += NUM[cur]’. Append the ‘NUM[cur]’ to ‘res’ string.
      • ‘pos[d].pop()’. Pop the top element (index ‘cur’) from ‘pos[d]’.
      • ‘seen[cur] = True’. Mark the index ‘cur’.
      • ‘k -= count’. The number of swaps to move ‘NUM[cur]’ to position ‘i’.
      • Break the loop as we have found the leftmost smallest digit after ‘i’.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’, to append the remaining digits to ‘res’:
  • If ‘seen[i]’ is equal to ‘False’, then:
    • ‘res += num[i]’.
• Return ‘res’ as the answer.

Prerequisite: The segment tree. To perform the following two operations on an array:

• MODIFY(L, R, V): Increment a range of elements from ‘[L to R]’ by value ‘V’.
• QUERY(P): Find the value at index ‘P’.

Similar to the previous approach, creating ten stacks ‘POS[10]’ (using array implementation) to store the indexes of digits from ‘0’ to ‘9’. The stack ‘POS[i]’ stores the indexes of the digit ‘i’ in descending order where the back of the array/top of the stack is the leftmost (smallest) index. 
 

Create a segment tree for an array of size ‘N’ with each element set to ‘0’ and use it to count the right shifts in digits. Whenever we move a digit from index ‘ID’ to ‘i’, increment the indexes from ‘0’ to ‘ID - 1’ by ‘1’. As after performing the ‘ID - i - 1’ swaps, the digits from ‘i’ to ‘ID - 1’ move right by one position. We increment the indexes from ‘0’ because:

• In the previous iteration, some indexes before ‘i’ might have moved to a location after ‘i’ by moving right.
• For those indexes that didn’t make it to the right of ‘i’, it doesn’t matter if we increment or decrement their indexes as we have already inserted these indexes into ‘RES’.

The number of digits from an index ‘i’ to an index ‘ID’ in is equal to = ‘ID + QUERY(ID) - i’. Here, ‘QUERY(ID)’ will return the number of positions that ‘ID’ has been shifted to the right.
 

Create an empty string ‘RES’ to store the minimum possible number. As per the previous approach, the most significant (leftmost) digit should be the minimum of the first ‘K + 1’ digits (given that ‘K + 1 <= N’). So, starting to traverse ‘POS’ from ‘0’ to ‘9’ until we find a digit ‘D’ that has not more than ‘K’ digits to its left. When we find ‘D’, append ‘D’ to the ‘res’ and mark the location of ‘D’ in ‘NUM’. Increase the indexes from ‘[0 to (the index of ‘D’ - 1)] by ‘1’, pop ‘POS[D]’, and update the value of ‘K’. If all the stacks become empty before performing the ‘K’ swaps, then ‘RES’ stores the answer.
 

Otherwise, after the ‘K’ swaps are exhausted, append the unmarked digits from ‘0’ to ‘N - 1’ for ‘NUM’ to ‘RES’ (as we always swap the digits from right to left the order of unmarked digits in the final answer and ‘NUM’ is the same).

Algorithm:

• Create ten arrays ‘pos[10]’ and use them as a stack. Here, ‘pos[i]’ will store the indexes of digit ‘i’.
• Run a loop where ‘i’ ranges from ‘N - 1’ to ‘0’:
  • ‘pos[NUM[i]].push(i)’.
• Create a string ‘res’ to store the answer.
• Initialize a boolean array ‘seen[n]’ set to ‘False’. Use it to track the indexes that have been inserted into ‘res’.
• Create a segment tree of size ‘st’ for an empty array of size ‘N’. Use it to count the number of the right shifts in digits.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
  • If ‘K = 0’, then we cannot do any more swaps:
    • Break the loop.
  • Run a loop where ‘d’ ranges from ‘0’ to ‘9’, to find the smallest leftmost digit after ‘i’:
    • If the stack ‘pos[d]’ is empty, then there are no more digits ‘d’:
      • Continue the loop.
    • Set ‘cur = pos[d].top()’. Index of the leftmost digit ‘d’ after ‘i’.
    • ‘count = cur + st.query(cur) - i’. The number of swaps required to move ‘NUM[cur]’ to index ‘i’.
    • If ‘count <= k’, then:
      • ‘res += NUM[cur]’. Append the ‘NUM[cur]’ to ‘res’ string.
      • ‘pos[d].pop()’. Pop the top element (index ‘cur’) from ‘pos[d]’.
      • ‘seen[cur] = True’. Mark the index ‘cur’.
      • ‘st.modify(0, cur, 1)’. Shift all the digits before index ‘cur’ to the right by one.
      • ‘k -= count’. The number of swaps to move ‘NUM[cur]’ to position ‘i’.
      • Break the loop as we have found the leftmost smallest digit after ‘i’.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’, to append the remaining digits to ‘res’:
  • If ‘seen[i]’ is equal to ‘False’, then:
    • ‘res += num[i]’.
• Return ‘res’ as the answer.