Greedy Algorithm to Find the Lexicographically Smallest Sequences After At Most K Element Swaps

Given 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.

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

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].

Greedy Algorithm to Find Smallest Array after K Element Swapping

We can use greedy algorithm to solve this problem. Every iteration, we find the smallest element and try to move it to the front. Then if we stil can do element swapping after this, we can continue solving a smaller array.

Please note, when we get the smallest element in the unsorted array, we have to consider the K value as well, – as our target is to replace the current element in the front and there is no point to find a smallest element that is more than K steps away.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

vector<int> findMinArray(const vector<int> &arr, int k) {
  vector<int> res(arr);
  for (int i = 0; (i < res.size()) && (k > 0); ++ i) {
    int curIdx = i;
    int kk = k;
    // find current smallest element after at most k swaps
    for (int j = i + 1; (j < res.size()) && (kk > 0); ++ j, --kk) {
      if (res[j] <= res[curIdx]) {
        curIdx = j;        
      }
    }
    // then swap it to the front if possible
    for (int j = curIdx; (j > i) && (k > 0); --j, --k) {
      swap(res[j], res[j - 1]);
    }
  }
  return res;
}

vector<int> findMinArray(const vector<int> &arr, int k) {
  vector<int> res(arr);
  for (int i = 0; (i < res.size()) && (k > 0); ++ i) {
    int curIdx = i;
    int kk = k;
    // find current smallest element after at most k swaps
    for (int j = i + 1; (j < res.size()) && (kk > 0); ++ j, --kk) {
      if (res[j] <= res[curIdx]) {
        curIdx = j;        
      }
    }
    // then swap it to the front if possible
    for (int j = curIdx; (j > i) && (k > 0); --j, --k) {
      swap(res[j], res[j - 1]);
    }
  }
  return res;
}

The time complexity is O(N^2).

–EOF (The Ultimate Computing & Technology Blog) —