Lexicographically smallest array formed by at most one swap for every pair of adjacent indices | Function to find the lexicographically smallest array ; Maximum swaps possible ; Hash to store swaps performed ; Let current element be the minimum possible ; Find actual position of the minimum element ; Update minimum element and its position ; Perform swaps if possible ; Insert current swap in hash ; Print the required array ; Driver code
def findSmallestArray ( A , n ) : NEW_LINE INDENT count = n - 1 NEW_LINE mp = { ' ' } NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if ( count <= 0 ) : NEW_LINE INDENT break ; NEW_LINE DEDENT mn = A [ i ] NEW_LINE pos = i NEW_LINE for j in range ( i + 1 , n ) : NEW_LINE INDENT if ( A [ j ] < mn ) : NEW_LINE INDENT mn = A [ j ] NEW_LINE pos = j NEW_LINE DEDENT DEDENT while ( pos > i and count > 0 and ( ( pos - 1 , pos ) not in mp ) ) : NEW_LINE INDENT mp . add ( ( pos - 1 , pos ) ) NEW_LINE A [ pos ] , A [ pos - 1 ] = A [ pos - 1 ] , A [ pos ] NEW_LINE pos -= 1 NEW_LINE count -= 1 NEW_LINE DEDENT DEDENT for i in range ( 0 , n ) : NEW_LINE INDENT print ( A [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT A = [ 2 , 1 , 4 , 3 , 6 , 5 ] NEW_LINE n = len ( A ) NEW_LINE findSmallestArray ( A , n ) NEW_LINE