I have been trying to solve this question.

Given an unordered array consisting of consecutive integers [1, 2, 3, …, n], find the minimum number of two-element swaps to sort the array.

I was able to solve it but my solution's complexity is not good enough that it terminated due to a timeout when it runs with bigger arrays. This is a typical problem for me, I always solve the problem somehow but the complexity is not optimal and the solution does not pass the all the cast cases. If you have any suggestions for me for the future interview questions like that, I'd appreciate knowing how should I approach the questions.

function findIndice(arr,i){
  let iterator=0
  return iterator

function swap(arr,x,y){
  let temp=arr[x]

function minimumSwaps(arr){
  let i=0;
  let counter=0;
  let size=arr.length;

      let index=findIndice(arr,i)
  return counter
  • \$\begingroup\$ This is a totally different question... @Gerrit0 \$\endgroup\$ Commented Aug 12, 2018 at 2:26
  • \$\begingroup\$ Oh shoot, you are totally right. I must have sent the wrong link as I looked at several... sorry about that! \$\endgroup\$
    – Gerrit0
    Commented Aug 12, 2018 at 2:48
  • \$\begingroup\$ That's okay, Thanks for trying to help :) @Gerrit0 \$\endgroup\$ Commented Aug 12, 2018 at 3:50

2 Answers 2


Your algorithm can be summarized by the pseudocode:

for each position in the array
    if a position is occupied by the wrong number
        find the number that fits into the position
        perform a swap

A better algorithm would be:

for each position in the array
    if a number is in the wrong location
        find the position the number should go
        perform a swap

This is because finding a number for a given location requires a linear scan, but finding the location for a given number is as simple as it gets: the number five should go into the fifth position.

The full program could look like this (in python, as I don't speak js):

def minimumSwaps(arr):
    def swap(i, j):
        arr[i], arr[j] = arr[j], arr[i]
    swaps = 0
    for i in range(0, len(arr)):
        while arr[i]-1 != i:
            swap(i, arr[i]-1)
            swaps += 1
    return swaps
  • \$\begingroup\$ This is a great solution but it fails if the numbers are not consecutive. To illustrate; 1 3 5 2 4 6 8 does not pass this test case @Rainer P. \$\endgroup\$ Commented Aug 12, 2018 at 17:25
  • 2
    \$\begingroup\$ @UgurYilmaz - Your question literaly says [...] consisting of consecutive integers [...]. \$\endgroup\$
    – Rainer P.
    Commented Aug 12, 2018 at 18:55
  • \$\begingroup\$ I know but there should be an error in hackerRank, then. Because there is a test case with that input and it seems to fail. Do you have any idea how to implement a solution efficiently if it is not a consecutive array integers @Rainer P. \$\endgroup\$ Commented Aug 12, 2018 at 19:50
  • \$\begingroup\$ There aren't such cases, I tried the solution above and it was accepted. \$\endgroup\$
    – user158037
    Commented Oct 12, 2018 at 16:07
  • \$\begingroup\$ Hi, I used exactly this method: ``` let swaps = 0; for (let i = 0; i < arr.length; i++) { if (arr[i] === i + 1) continue; arr.splice(i, 1, arr.splice(arr.indexOf(i + 1), 1, arr[i])[0]); swaps++; } return swaps; ``` But it still have huge large complexity and timeouts with very large input \$\endgroup\$ Commented Nov 7, 2019 at 11:32

The fastest way so far I tried is

  1. For each iteration of "i"
  2. Try to find out from the list ( i - 1, arr.length ) if there is an item misplaced
  3. If there is an misplaced item, swap it

const minimalSwap = (arr) => {
    // don't mutate the original array
    let list = [...arr]
    // length of the list
    const listLen = list.length
    // state - total swap
    let totalSwap = 0
    if (listLen <= 1) {
        return totalSwap
    function swap(items, idxOne, idxTwo) {
        let tempNode = items[idxOne]
        items[idxOne] = items[idxTwo]
        items[idxTwo] = tempNode
        totalSwap += 1
        return items
    for (let i = 0; i < listLen; i++) {
        // for each iteration, we find the
        // number that should go to the correct position
        let idToSwap = false
        const correctNumber = i + 1
        // iterate through starting next item
        // and find if the correct number is misplaced
        for (let j = i + 1; j < listLen; j++) {
            // if it is misplaced, swap it
            if (correctNumber === list[j]) {
                idToSwap = j
        if (idToSwap) {
            list = swap(list, i, idToSwap)

    return totalSwap

// test case
minimalSwap([14, 15, 16, 4, 8, 3, 1, 2, 5, 7, 9, 10, 11, 12, 13, 6])


Not the answer you're looking for? Browse other questions tagged or ask your own question.