Categories
General

Element Swapping Facebook

Element SwappingGiven a sequence of n integers arr, determine the lexicographically smallest sequence which may be obtained from it after performing at most k element swaps, each involving a pair of consecutive elements in the sequence.Note: A list x is lexicographically smaller than a different equal-length list y if and only if, for the earliest index at which the two lists differ, x’s element at that index is smaller than y’s element at that index.

Signature

int[] findMinArray(int[] arr, int k)

Input

n is in the range [1, 1000]. Each element of arr is in the range [1, 1,000,000]. k is in the range [1, 1000].

Output

Return an array of n integers output, the lexicographically smallest sequence achievable after at most k swaps.

Example 1

n = 3 k = 2 arr = [5, 3, 1] output = [1, 5, 3]We can swap the 2nd and 3rd elements, followed by the 1st and 2nd elements, to end up with the sequence [1, 5, 3]. This is the lexicographically smallest sequence achievable after at most 2 swaps.

Example 2

n = 5 k = 3 arr = [8, 9, 11, 2, 1] output = [2, 8, 9, 11, 1]We can swap [11, 2], followed by [9, 2], then [8, 2].

   function findMinArray(array $arr, int $k) : array
  {
    #arr = [5, 3, 1]
    # k:2, 1
    while($k >= 1) 
    {
    
      # swapping
      $temp = $arr[$k];        # temp 1      ; 1
      $arr[$k] = $arr[$k - 1]; # $arr[2] = 3; $arr[1] = 5
      $arr[$k - 1] = $temp;    # $arr[1] = 1; $arr[0] = 1

      #arr = [5, 1, 3]
      #arr = [1, 5, 3]
      $k--; #1 #0
    }
    
    return $arr;
    
  }

Leave a Reply