minimum_swaps.dart

/// https://www.hackerrank.com/challenges/minimum-swaps-2/
///
/// You are given an unordered array consisting of consecutive integers  [1, 2, 3, ..., n] without any duplicates.
/// You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.

int minimumSwaps(List<int> input) {
  int swaps = 0;
  var list = List.generate(input.length, (index) => index + 1);
  var map = {};
  for (var el in list) {
    map[el] = false;
  }

  for (var i = 0; i < input.length; i++) {
    var el = input[i];
    if (i + 1 == el) {
      continue;
    }
    if (map[el]) {
      continue;
    }
    map[el] = true;
    int counter = 0;
    var next = input[el - 1];
    while (map[next] == false) {
      counter++;
      map[next] = true;
      next = input[next - 1];
    }
    swaps += counter;
  }

  return swaps;
}

void main() {
  print(minimumSwaps([7, 1, 3, 2, 4, 5, 6]));
  print(minimumSwaps([1, 2, 3, 4, 5]));
  print(minimumSwaps([1, 3, 5, 2, 4, 6, 7]));
  print(minimumSwaps([1]));
  print(minimumSwaps([1, 2]));
  print(minimumSwaps([2, 1]));
  print(minimumSwaps([2, 3, 4, 1, 5]));
}