6
\$\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\$
2
  • \$\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, 2018 at 18:18
  • \$\begingroup\$ Does someone know the actual algorithm described in the examples to the question? I always see only alternate algorithms. What is the real algorithm? \$\endgroup\$ Feb 5 at 15:52

3 Answers 3

14
\$\begingroup\$

Look for clues

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

When the program appears to work correctly for all simple examples you tried, but the time limit is exceeded when you submit, that's a clue indicating that the algorithm is too slow.

Another clue is to ask yourself: are you using all the known information about the input? Look closely at the problem description.

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

The current implementation is not using the fact that the input is consecutive integers without duplicates. In other words, the input is basically all the integers 1..n, shuffled.

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ your narrative explaining the clues was nice! Good job 👍 \$\endgroup\$ Apr 30, 2020 at 0:12
  • \$\begingroup\$ Do you know the actual algorithm described in the examples to the question? I always see only alternate algorithms. What is the real algorithm? \$\endgroup\$ Feb 5 at 15:55
1
\$\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];

        /* initializing checked array slots to false, it only sets to true if 
           each elmement is placed in its right slot so checked[1] = true 
           indicates that arr[1] = 1. remember this is n+1 series array you 
           can't have value of 9 when array size is less than 9 */ 
        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, we are not doing swapping but we are 
            //counting how many times this element will be swapped before 
            //residing in its proper slot  
            var counter = 0;
            while (!@checked[entryIndex])
            {
                counter++;
                @checked[entryIndex] = true;
                entry = arr[entryIndex];
                entryIndex = entry - 1;
            }

            total += counter -1 ;
        }

        return total;
    }
\$\endgroup\$
3
  • 1
    \$\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\$ Aug 9, 2019 at 6:56
  • \$\begingroup\$ @Sameh, Thanks for putting snippet, but it is hard to understand. Would you put comment in your code? \$\endgroup\$
    – Cloud Cho
    May 29, 2021 at 22:08
  • \$\begingroup\$ you can watch this video over you tube it will explain how the algo works "youtube.com/watch?v=J9ikRMK8Yhs" \$\endgroup\$
    – Sameh
    Jun 1, 2021 at 20:57
0
\$\begingroup\$

The code is doing much more work than it needs to.

Reading the problem statement carefully, we just need to calculate how many swaps are required. Actually sorting the array and counting as we go is probably the least efficient way to do this.

I think you really need to abandon this attempt (sorry!) and come up with a more efficient algorithm for counting swaps. As a hint, think of the mapping of current position of an element to its required position, and look for cycles. We know how many swaps it takes to resolve a cycle of length n, and we can just add all those together to get the total.

\$\endgroup\$
2
  • \$\begingroup\$ Out of curiosity, let's say I have an array of [3,2,1]. if I only mark the location I will get 2 as a result. However, If I swap, it will be done in one. @Toby correct me if I am wrong. \$\endgroup\$ Apr 17 at 15:16
  • \$\begingroup\$ @Abdul, your example has one cycle with length 2 - that's [3,1]. A length-2 cycle needs just one swap to resolve, giving the expected result. \$\endgroup\$ Apr 18 at 6:57

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