HackerRank Interview Prep Kit - Problem 8: Minimum Swaps 2
Вставка
- Опубліковано 11 жов 2024
- Hello, my name is Brian Dyck, I am a full-time software engineer and a Computer Science graduate walking through HackerRank problems for new and old programmers alike. My goal is to help programmers build up skills and not just see the solutions to problems, but to learn how to think through the problems. Many new videos to come, so stay tuned!
Problem: Minimum Swaps 2
Description:
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.
Ah! This made my day! I did not know that array will always have integers starting from 1. This makes sense now!
Glad you enjoyed it! If you have any special requests please let him know! He is great at that!
Amazing! Thanks Brian, with your explanation, I was able to debug my code and passed all tests! I had tried pointers, bubble sort, selection and insertion sort. This was so easy and straight to the point.
No problem! Glad to help!
Hi, I write javascript but your solution was so basic and straight forward, was able to convert the syntax, thanks alot
You made my day😍, I was flabbergasted by the question and was having an existential crisis 😣
Haha glad to make your day!
Hi, your solution is really straight forward and is basically using the idea of using temp variable in a more smarter way. Anyways regarding the time complexity of the problem, a more simple way of looking at it, is that the for loop will only loop once letting the while loop handle the business. Not to mention that the while loop condition won't be/can't be fulfilled a second time after the first run.
You made my day :). I was fed up with the solutions available in the internet. Your solution is a optimized one :). Thank you
Superb Solution, Straight, and very easy to understand.
No doubt this is THE best explanation online! Thank You!
He also helps others with any other questions they might have! Please share with friends in CS!
Glad it was helpful!
Thanks! I was wondering why the hacker rank site was swapping those numbers seemingly randomly.
Here is a simpler python solution following the logic in the video (1 while loop):
def minimumSwaps(arr):
i = 0
count = 0
while i < len(arr):
#Is the current element in the correct position?
#Yes
if arr[i] - 1 == i:
#Iterate to the next element
i += 1
#No
else:
#Swap current element to its true position
k = arr[i] - 1
arr[k], arr[i] = arr[i], arr[k]
count += 1
return count
Great solution!
I think what they trying to do was to swap the numbers with the most potential value... Potential value being (Potential val : (i + 1) - arr[i])
for example: arr = [7, 1, 3, 2, 4, 5, 6]
potential_arr = [-6, 1, 0, 2, 1, 1, 1]
The smallest val is -6 cause needs to 6 right to the position it is... and max val is 2 in cause it needs to be 2 left of its pos... Thats how they did it!! I went ahead with this logic but it is too complex... And the interview is near
To proof this algorithm is correct, we need to understand that an optimal way to do this would be to find cycles of swaps required, i.e. a1 -> a2 -> a3 and then for each cycle we need (length of cycle - 1) swaps. The while loop is exactly doing that for each pair of nodes of the loop at a time.
Adding that it requires x-1 swaps to correct a cycle of x elements, as the last two elements of the cycle to be swapped puts them both in place. Minus the elements already in place, if m is the # of elements not in place, it would be O(n+m) time as m is bounded by n, and m is at worst a single cycle of n elements requiring m-1 swaps. If there are k cycles, then that becomes m-k swaps.
Send suggestions & he will do videos over it! :)
FML lol, been killing myself over this. I had EXACTLY the same idea, and the first sample tests were passing. However, the rest had runtime errors because of my print statements.....
Noooooooo I hate it when that happens.. non-programmers will never understand that pain 🥺
Nice, on my first attempt I got a different answer but this was a cool solution.
Great explanation. Definitely helped me
Glad to help!
I didn't get it at first,
The numbers are in the interval [ 1, n ]
so looking at a number, you just know what is the index it should go to
Equivalent JS solution
function(arr)
{
let numSwaps = 0;
for(let i = 0; i < arr.length; i++)
{
while(arr[i] != (i + 1))
{
let swapIndex = arr[i] - 1;
let valAtIndex = arr[i];
let valAtSwapIndex = arr[swapIndex];
arr[i] = valAtSwapIndex;
arr[swapIndex] = valAtIndex;
numSwaps++;
}
}
return numSwaps;
}
Great approach, thanks for sharing
hi, thanks for the explanation, it was great and easy to understand. however, i have several questions:
1. What if the elements are not restricted to the values of (index + 1)? ex:
[5, 9, 7, 8, 6]
2. What if the elements does not have a consistent step? consider the following array:
[1, 10, 8, 4, 3]
How would we solve for these?
thank you
As long as the elements are consecutive, the same trick applies of knowing that the ordinal position that an element belongs is the difference between its value and the lowest value. It would be the same algorithm to calculate the minimum number of swaps, but you'd need an O(n) search to determine the minimum element.
The quick method relies on knowing the position of elements in their sorted order. The problem gives us this automatically by giving us a sequence counted from 1. If you didn't have the sequence, you could find it by sorting the array. Then you just assign a mapping between the element and its proper ordinal position and reconstruct the original problem using the ordinal positions instead of the values. In your example, [1, 10, 8, 4, 3] would map to [1, 5, 4, 3, 2]. Now it's the same problem again.
If your loops aren't creating additional storage, and only the cursors for tracking the position of the iteration are allocated, wouldn't it be O(1) space complexity? Or are you counting the space allocated by the input parameter? It doesn't seem like that space should be counted as part of the solution.
In JavaScript i think we can do more simpler by using sort() method and push() the number into array.
Yes, you are right! C++ makes it more complicated
The second constraint made this FAR easier. Wtf do you do if its {2,4,9,6,5,3) ?
Hmm.. I mean the first thing that popped into my head was creating a mapping where we assign each element of the array a key corresponding to it’s ordered position - in other words it’s correct place, then run the same algo - because the it’s sort + same time complexity, which is not terrible, but there’s probably a much more optimal solution 🤔
Great explanation thank you.
Thanks a lot!
Glad to help!
Thank you ❤️
How do you prove the solution, even though it passes all tests
To prove the algorithm rigorously you would have to perform a mathematical proof that shows it being true for all instances of the given constraints. If you have taken a class on Algorithms you would probably be required to do so, or if you are interested in learning on your own I can point you in the right direction.
@@briandyck8828 Thaks Brian. That would be much appreciated. Please point to the resources
Making it harder than it has to be -that's what she said
thankyou
You're welcome!
... The "minimum" keyword is basically unnecessary and there I was trying to formulate a super algorithm busting my brain out... Hackerrank explanations are completely flawed and I've failed an job interview because of it, paid the ultimate price... Here's my solution which didn't work, too slow...
def minimumSwaps(arr):
def swapper(counter, arr2):
out_of_place = []
for i in range(len(arr2)):
if arr2[i] is not i + 1:
out_of_place.append([abs(arr2[i] - (i + 1)), arr2[i], i])
if len(out_of_place) == 0:
print(counter, arr2)
return counter
max1 = out_of_place.pop(out_of_place.index(max(out_of_place)))
max2 = out_of_place.pop(out_of_place.index(max(out_of_place)))
arr2[max1[2]] = max2[1]
arr2[max2[2]] = max1[1]
counter += 1
return swapper(counter, arr2)
return swapper(0, arr)
That's sad, but yeah, they do not have good explanations
I’m trying to understand how it’s not O(n)^2
I understand the confusion, but the key difference is because of two special properties. 1) we know the correct index of a number in the wrong index, in other words, we do no iterate through the array to find the correct position of the number out of place. 2) Since we are swapping two indices on each change, and since once we pass an index when we have the correct value in a given index the absolute worse case is swapping in the 0 index N times until the 0 index is correct in which case it then iterates over N indices which each value is now in the proper place. Therefore, it would be 2 N in the worse case meaning order N. For it to be O(N^2) it would have to be the opposite order of steps. Let’s say, when at 0 we ‘look’ for the 0, then the 1, etc. N places. In that case the algorithm would be O(N^2) because it could take N operations at each index. Make sense?
I think more importantly there are constraints for this hackerrank question - the numbers are always consecutive. unlike for usual sorting algorithms where that is not guaranteed.
Why can't we use "IF Condition" instead of "WHILE" ?
The while condition is necessary because when we perform the swap, we’re grabbing whatever was in the place the previous number was supposed to be at, but the number we now have at index may be incorrect as well. If that is the case, it would need to also be swapped to its correct spot until the value at index is equal to index + 1. Then and only then can we increment the index to the next spot. The edge case that would cause this is if you swap a number into a position behind then current index, then in normal course of swaps, swaps the number that the other number is needing to be at behind the index as well.
An example of an array that would fail the if statement algo is:
[7, 3, 1, 4, 8, 5, 2, 6]
Enter for loop: 0 sees 7 swaps 7 and 2
[2, 3, 1, 4, 8, 5, 7, 6]
Inc loop: 1 sees 3 swaps 3 and 1
[2, 1, 3, 4, 8, 5, 7, 6]
Inc loop: 2 sees 3 good
Inc loop: 3 sees 4 good
Inc loop: 4 sees 8 swaps 8 and 6
[2, 1, 3, 4, 6, 5, 7, 8]
Inc loop: 5 sees 5 swaps 5 and 6
[2, 1, 3, 4, 5, 6, 7, 8]
Inc loop: 6 good
Inc loop: 7 good
Returns array not properly sorted which would result in the wrong number of swaps needed.
Does that make sense?
@@briandyck8828 Thanks.....It's clear to me now.
if after 3 years you still couldn't remember the website for maths papers it was latex haha
Rote explanation.