Given an array, arr[] of integers. The task is to sort the elements of the given array in the increasing order of their modulo with 3 maintaining the order of their appearance.
Expect time complexity O(N) and the interviewer said that it can be done in only one/two traversal(s)(sorry I don't remember it clearly, it was quite sometime ago).
Expected space complexity O(1).
https://en.wikipedia.org/wiki/Dutch_national_flag_problem
However, stability requirement is not achievable in the given constraints.
We can use dutch national flag as modulo with 3 will leave us with an array of 0, 1, 2. So the problem will boil down to something like this.
The task is to sort the elements of the given array in the increasing order of their modulo with 3 maintaining the order of their appearance.
How to maintain the order of their appearance in one traversal?
If you push the elements in a vector, the order will be maintained.
nvm
Space Complexity is O(1) mate. You can't use another vector. Somehow you have to think of a way while using only swapping.
In that way the original order will not be maintained.
Can do it in 2 traversals with no extra space. In one traversal you can get number of 0s,1s and 2s. So in the second traversal, if you encounter a number, you know its exact position (from the previous traversal). Just swap with its exact position and continue the process.
can you please elaborate I had though of the same thing but wasn't sure if it will maintain the order of the elements
okay, I just gave a thought and found out that the order will not be maintained. If you allow one more traversal then it is possible definitely. In the second traversal replace each value with its original position in the sorted array, this can be done using the number of 0,1,2. Finally, in the 3rd traversal, swap it i.e place everything in the positions stored. Maybe this swapping can be done in the 2nd traversal only efficiently but I guess it's tricky.
Can you write the code for this ??
.
Order is not maintained here
I think below code will work assuming input can be modified It uses two passes one to count the number of 0,1,2's and second for modifying the input to make it sorted by starting three pointers from 0,cnt[0],cnt[0]+cnt[1].
I have a doubt.... for example you are changing value of a[oneindx], but you are not storing its previous value i mean it's previous value would be diminshed?