CodeSignal Arcade – Sort by Height

Problem

Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees. People can be very tall!

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be
solution(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Solution

Idea

I don’t remember any algorithm for sorting so I have to study one first. I choose QuickSort because it’s one of the most efficient sorting algorithm. The key idea of Quick Sort is:

• Choose a pivot. We can choose any number in the array. For example, the last number in the array.
• Partition the array based on the pivot.
  • Left partition contains number less than the pivot.
  • Right partition contains number greater than the pivot.
• Move the pivot to the correct position.
• Repeat the algorithm with the left and right partition.

When implementing this sorting algorithm, I find out that we don’t need to store the partition in another variable, we just need to push the number which is smaller than the pivot to the start of the array.

With the first version of the code, I passed 9/12 test cases from CodeSignal. The 3 left one are for performance testing. In the first version, I just ignored the tree (number -1) when processing the algorithm. It means that my strategy was wrong. I think that if the number of trees are large enough, it will slow down the algorithm.

In the second version, I do the following:

• Scan the array for the trees.
  • Save the trees’ index into treeArray
  • Get rid of the trees and have peopleArray
• Process the sorting with the peopleArray.
• Insert the trees back to peopleArray based on the index from treeArray.

And voila, it works!

Code

function solution(a) {
    let [treeArray, peopleArray] = filterTree(a);
    
    quickSort(peopleArray, 0, peopleArray.length - 1);
    
    for (let i = 0; i < treeArray.length; i++) {
        peopleArray.splice(treeArray[i], 0, -1);
    }
    
    return peopleArray;
}

function filterTree(a) {
    let treeArray = [];
    let peopleArray = [];
    for (let i = 0; i < a.length; i++) {
        if (a[i] == -1) {
            treeArray.push(i);
        } else {
            peopleArray.push(a[i]);
        }
    }
    return [treeArray, peopleArray];
}

function partition(a, low, high) {
    let pivot = a[high];
    
    if (pivot == -1) { // found a tree, start with a new pivot
        return high - 1;
    }
    
    let i = low - 1;
    
    for (let j = low; j < high; j++) {
        if (a[j] == -1) { // found a tree, ignore it
            continue;
        }
        
        if (a[j] < pivot) {
            i = getPersonIndex(a, i + 1);
            
            [a[i], a[j]] = [a[j], a[i]]; // swap element by destructuring method
        }
    }
    
    i = getPersonIndex(a, i + 1);
    [a[i], a[high]] = [a[high], a[i]]; // swap pivot element
    return i;
}

function getPersonIndex(a, index, order = 1) {
    if (a[index] == -1) {
        return getPersonIndex(a, index + order);
    }
    return index;
}

function quickSort(a, low, high) {
    if (low >= high) {
        return a;
    }
    
    let pivotIndex = partition(a, low, high);
    quickSort(a, low, pivotIndex - 1);
    quickSort(a, pivotIndex + 1, high);
    
    return a;
}