The question
Given an array [a1, a2, …, aN, b1, b2, …, bN, c1, c2, …, cN] convert it to [a1, b1, c1, a2, b2, c2, …, aN, bN, cN] in-place using constant extra space
My solution
At first this question felt a little confusing so lets clear a few things.
– There will only be a, b and c
– The size of the array is going to be N*3
– The problem needs to be solved without creating an extra array so the modifications need to be made in the same array
The algorithm:
1 – Start at the element at index 1 (We know the element at index 0 is in the right place already)
2 – Check if the element is already in the place it should be. If it is, continue to next element.
3 – If the element is not in the right place grab the element that should be in that place and move this element to the other element location.
4 – Repeat for all elements
This is the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var arr = ['a1', 'a2', 'a3', 'a4', 'b1', 'b2', 'b3', 'b4', 'c1', 'c2', 'c3', 'c4'];
function convertArray(arr) {
var letters = ['a', 'b', 'c'];
var maxNumber = arr.length / 3;
function moveToExpected(index) {
var expectedNumber = (Math.floor(index / 3)) + 1;
var expectedLetter = letters[(index % 3)];
if (arr[index] !== expectedLetter + expectedNumber) {
var expectedElementPosition = (index % 3) * maxNumber +
(Math.floor(index / 3));
var tmp = arr[index];
arr[index] = arr[expectedElementPosition];
arr[expectedElementPosition] = tmp;
moveToExpected(expectedElementPosition);
}
}
var secondLast = arr.length - 1;
for (var i = 1; i < secondLast; i++) {
moveToExpected(i);
}
}
function test() {
convertArray(arr);
var expected = ['a1', 'b1', 'c1', 'a2', 'b2', 'c2', 'a3', 'b3', 'c3', 'a4', 'b4', 'c4'];
if (JSON.stringify(expected) === JSON.stringify(arr)) {
console.log('success');
}
}
test(); // Prints success
This gets the job done in a kind of efficient way but I am not sure about the O notation for this. It will go through all elements in the array and for some of them it will do some swaps. It is more than O(n) but less than O(n^2).
The best solution
The solution they propose is a little similar:
1 – Start at the element at index 1 (We know the element at index 0 is in the right place already)
2 – Get the index of the element that should be in this location.
3 – If the index is higher than the current index then we can just swap those two elements
4 – If the index is lower that means that the element has been already swapped so we have to follow the swaps until current index is lower than the swap index and then do the swap
5 – Repeat for all elements
This is the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function convertArray(arr) {
var n = arr.length / 3;
function getIndex(current) {
return (current % 3) * n + (current / 3);
}
var swap;
var tmp;
for (var i = 0; i < arr.length; i++) {
swap = Math.floor(getIndex(i));
while (swap < i) {
swap = Math.floor(getIndex(swap));
}
tmp = arr[i];
arr[i] = arr[swap];
arr[swap] = tmp;
}
}
function test() {
convertArray(arr);
var expected = ['a1', 'b1', 'c1', 'a2', 'b2', 'c2', 'a3', 'b3', 'c3', 'a4', 'b4', 'c4'];
if (JSON.stringify(expected) === JSON.stringify(arr)) {
console.log('success');
}
}
test(); // Prints success
They explain the complexity as O(N^1.3) which is some times called super linear.
computer_science algorithms javascript programming