Last week, I tried to solve the second Codility Challenge for this year called Cobaltum 2018. Same as the previous one, Ferrum 2018, my solution was awarded with the Codility Golden Award. From every other that I did before, this seemed to be the easiest one (or maybe that is just relative perception) although I lost some time to figure out the proper solution that will be elegant and handles the edge cases at the same time.
This time I will not give details about the Codility Challenges, but if you like to have brief intro about how that works you can find out more in my previous article about the Ferrum 2018 challenge or check my Lazy Propagation Segment Tree implementation. I’ll introduce you to the current challenge and what are the requirements that your solution must satisfy.
Cobaltum 2018 Codility Challenge
For this challenge you’ll need to find a solution that will find the minimum number of swaps that we need to do in order to make arrays A and B consisting of integers, both of length N, and you would like them to be (strictly) increasing, i.e. for each K (0 ≤ K < N − 1), A[K] < A[K + 1] and B[K] < B[K + 1]. Thus, you need to modify the sequences, but the only manipulation you can perform is to swap an arbitrary element in sequence A with the corresponding element in sequence B. That is, both elements to be exchanged must occupy the same index position within each sequence.
For example, given:
A = 5 B = 1
A = 3 B = 6
A = 7 B = 6
A = 7 B = 9
A = 10 B = 9
your function should return 2, as explained above.
A = 5 B = 2
A = -3 B = 6
A = 6 B = -5
A = 4 B = 1
A = 8 B = 0
your function should return −1, since you cannot perform operations that would make the sequences become increasing.
A = 1 B = -2
A = 5 B = 0
A = 6 B = 2
your function should return 0, since the sequences are already increasing.
The imitations for the time complexity and the space complexity are:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Try this Cobaltum 2018 Challenge by yourself and try to get to this screen and pick up your reward