2
\$\begingroup\$

Here is my problem statement. An excerpt:

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. You need to find the minimum number of swaps required to sort the array in ascending order.

For example, given the array arr = [7, 1, 3, 2, 4, 5, 6] we perform the following steps:

i   arr                     swap (indices)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

The code:

int minimumSwaps(int arr_count, int* arr) {

long long int i,count=0,j,temp,min,min_index;
for(i=0;i<arr_count;i++)
{
    min=arr[i];
    min_index=i;
    for(j=i+1;j<arr_count;j++)
    {
        if(arr[j]<min)
        {
            min=arr[j];
            min_index=j;
        }
    }
    if(min_index!=i)
    {
        count++;
    temp=arr[min_index];
    arr[min_index]=arr[i];
    arr[i]=temp;
    }
    }
return count;
}

5 out of 15 test-cases are failing. Here is one of the test cases. It is failing with a message as "Terminated due to timeout".

I used selection sort approach as selection sort makes minimum swap operation. My time complexity is O(n^2). Can I reduce it?

\$\endgroup\$
  • \$\begingroup\$ The array length, array elements and return values are all of type int. It doesn't make any sense to use long long int for all local variables; that will just slow down your implementation, which is already a \$O(n^2)\$ slow algorithm. The optimal solution will scale slower than \$O(n^2)\$. \$\endgroup\$ – AJNeufeld Oct 24 '18 at 18:18
3
\$\begingroup\$

Analyzing the problem, finding clues

I used selection sort approach as selection sort makes minimum swap operation.

Really? (I don't know.) More importantly, are you sure sorting is needed here?

My time complexity is \$O(n^2)\$. Can I reduce it?

When the time limit is exceeded, and the program appears to work correctly for non-large inputs, the typical cause of slowness is the algorithm. It can be hard to find an efficient algorithm. To figure out the trick, look for clues. For example, look details in the question that are not used in the current algorithm.

You are given an unordered array consisting of consecutive integers ∈ [1, 2, 3, ..., n] without any duplicates.

Take a closer look. What's in there that your solution is not using?

There's nothing in your implementation that benefits from integers being consecutive, without any duplicates. That is, it's not benefitting from this constraint on the input:

$$ 1 \leq arr[i] \leq n $$

In other words, the input consists of the numbers \$1, 2, 3, ..., n\$, shuffled. Given such input, you can produce a correct ordering in \$O(n)\$. And as such, maybe sorting is not needed here after all.

This is still just a hint, without directly answering how to compute the minimum number of swaps. But this observation must surely be part of the implementation.

(I suggest to stop reading here and try to come up with an algorithm that uses the above observation and implement a passing solution. Continue reading only if you need hints.)

Alternative algorithm

Consider this algorithm:

  • Build an array of indexes of the values in the input: indexes[arr[i] - 1] = i;.
  • Iterate over the input array, and when arr[i] != i + 1, then swap arr[i] with arr[indexes[i]], and update the index of the original value of arr[i].

For example, for [7, 1, 3, 2, 4, 5, 6], the content of indexes would be [1, 3, 2, 4, 5, 6, 0] (indexes[7 - 1] = 0; indexes[1 - 1] = 1; indexes[3 - 1] = 2; ....

Then, the content of arr and indexes will go through these changes:

i       = 0; 7 != 1 so swap it with 1 (the element that belongs here)
arr     = [7, 1, 3, 2, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 0]

i       = 1; 7 != 2 so swap it with 2 (the element that belongs here)
arr     = [1, 7, 3, 2, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 1]

i       = 2; 3 == 3 so no swap
arr     = [1, 2, 3, 7, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 3]

i       = 3; 7 != 4 so swap it with 4 (the element that belongs here)
arr     = [1, 2, 3, 4, 7, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 4]

And so on, two more swaps (total 5) and 7 reaches the end.

Bugs in questions

I don't recall ever finding a bug in an online puzzle (and that should always be the very last thought on your mind), but this puzzle has one. The 3rd sample input [1, 3, 5, 2, 4, 6, 8] (Testcase 14) violates the constraint \$1 \leq arr[i] \leq n\$. The 8 should be replaced with 7. I worked around that by doing this when building indexes:

if (arr[i] > N) arr[i] = N;
\$\endgroup\$
0
\$\begingroup\$

I have faced the same exam as well, and frank honestly I don't understand how these guys assume that someone who doesn't know algorithm will be able to solve it in timed fashion exam

The answer is you don't need to apply sorting, you need to find number of swaps , this one has better performance rather than Selection algorithm , as it reaches o(log(n)) in performance

The idea is find cycles if a needs to replace b and b needs to replace a then this is a cycle of 2 nodes which requires # of swaps = number of nodes -1

Cycle is when you reach a node that requires to be swapped so a=>b, b=>c, c=>d and d=>c since c requires a swap then this is a cycle, to achieve that we create a boolean array size of n, we loop to find cycles, if an element is checked then we found a cycle, if element is placed in its proper position then this is an element that cycles itself and requires 0 swaps

private static int CheckMinNumberOfSwaps(int[] arr)
    {
        var total = 0;
        var @checked = new bool[arr.Length];

        for (var index = 0; index < arr.Length; index++)
        {
            @checked[index] = false;
        }

        for (var index = 0; index < arr.Length; index++)
        {
            var entry = arr[index];
            var entryIndex = entry -1;

            if (@checked[entryIndex])
            {
                continue;
            }

            if (entryIndex == index)
            {  //entry is in the right spot
                @checked[entryIndex] = true;
                continue;
            }

            //draw cycle between nodes 
            var counter = 0;
            while (!@checked[entryIndex])
            {
                counter++;
                @checked[entryIndex] = true;
                entry = arr[entryIndex];
                entryIndex = entry - 1;
            }

            total += counter -1 ;
        }

        return total;
    }
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Aug 9 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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