Sorting an array according to the order defined by another three numeric items in array

You’re given a pair of arrays: one of the integers and the other of three particular integers. The first array is assured to contain only integers that are in the second; and the second array represents the desired order for the integers in the first.

Create a function that sorts the first array in the desired order.

The complexity of Space and Time

O(n) time | O(1) space

n is the length of the input array.

Input

array = [1, 0, 1, -1, -1, 0, 1, 0]

order = [0, 1, -1]

Output

[0, 0, 0, 1, 1, 1, -1, -1]

Hint

1st Approach (Counting Number): Count the number of times each of the three values appears in the input array. You can repopulate the input array after you’ve acquired these counts.

Pseudo Code

DEFINE FUNCTION threeNumberSort(array, order):
    SET valueCounts TO [0, 0, 0]
    FOR element IN array:
        SET orderIdx TO order.index(element)
        valueCounts[orderIdx] += 1
    FOR i IN range(3):
        SET value TO order[i]
        SET count TO valueCounts[i]
        SET numElementsBefore TO sum(valueCounts[:i])
        FOR n IN range(count):
            SET currentIdx TO numElementsBefore + n
            SET array[currentIdx] TO value
    RETURN array

2nd Approach (Splitting into subarrays): Splitting the main array into three subsets and transferring values from each distinct value to the proper subset. Keep track of the starting indices for each subset or subarrays.

Pseudo Code

DEFINE FUNCTION threeNumberSort(array, order):
    SET firstValue TO order[0]
    SET thirdValue TO order[2]
    SET firstIdx TO 0
    FOR idx IN range(len(array)):
        IF array[idx] EQUALS firstValue:
            SET array[firstIdx], array[idx] TO array[idx], array[firstIdx]
            firstIdx += 1
    SET thirdIdx TO len(array) - 1
    FOR idx IN range(len(array) - 1, -1, -1):
        IF array[idx] EQUALS thirdValue:
            SET array[thirdIdx], array[idx] TO array[idx], array[thirdIdx]
            thirdIdx -= 1
    RETURN array

3rd Approach (Two Passes): If you do two passes through the array, you’ll be placing the first ordered element during the first pass and the third ordered element during the second.

Pseudo Code

DEFINE FUNCTION threeNumberSort(array, order):
    SET firstValue TO order[0]
    SET secondValue TO order[1]
    # Keep track of the indices where the values are stored
    SET firstIdx, secondIdx, thirdIdx TO 0, 0, len(array) - 1
    WHILE secondIdx <= thirdIdx:
        SET value TO array[secondIdx]
        IF value EQUALS firstValue:
            SET array[secondIdx], array[firstIdx] TO array[firstIdx], array[secondIdx]
            firstIdx += 1
            secondIdx += 1
        ELSEIF value EQUALS secondValue:
            secondIdx += 1
        ELSE:
            SET array[secondIdx], array[thirdIdx] TO array[thirdIdx], array[secondIdx]
            thirdIdx -= 1
    RETURN array

Solution in Typescript

function threeNumberSort1(array, order) {
  const valueCounts = [0, 0, 0];
  for (const element of array) {
    const orderIdx = order.indexOf(element);
    valueCounts[orderIdx]++;
  }

  for (let idx = 0; idx < 3; idx++) {
    const value = order[idx];
    const count = valueCounts[idx];
    const numElementsBefore = valueCounts
      .slice(0, idx)
      .reduce((a, b) => a + b, 0);
    for (let n = 0; n < count; n++) {
      const currentIdx = numElementsBefore + n;
      array[currentIdx] = value;
    }
  }
  return array;
}

function threeNumberSort2(array, order) {
  const firstValue = order[0];
  const thirdValue = order[2];
  let firstIdx = 0;
  for (let idx = 0; idx < array.length; idx++) {
    if (array[idx] === firstValue) {
      swap(firstIdx, idx, array);
      firstIdx++;
    }
  }
  let thirdIdx = array.length - 1;
  for (let idx = array.length - 1; idx > -1; idx--) {
    if (array[idx] === thirdValue) {
      swap(thirdIdx, idx, array);
      thirdIdx--;
    }
  }
  return array;
}

function threeNumberSort3(array, order) {
  const firstValue = order[0];
  const secondValue = order[1];
  // Keep track of the indices where the values are stored
  let firstIdx = 0;
  let secondIdx = 0;
  let thirdIdx = array.length - 1;
  while (secondIdx <= thirdIdx) {
    const value = array[secondIdx];
    if (value === firstValue) {
      swap(firstIdx, secondIdx, array);
      firstIdx++;
      secondIdx++;
    } else if (value === secondValue) {
      secondIdx++;
    } else {
      swap(secondIdx, thirdIdx, array);
      thirdIdx -= 1;
    }
  }
  return array;
}

function swap(i, j, array) {
  const temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

mocha.setup("bdd");
describe("Sorting an array according to the order defined by another three numeric items in array", () => {
  it("#1 1st Approach (Counting Number)", function () {
    const array = [1, 0, 0, -1, -1, 0, 1, 1];
    const order = [0, 1, -1];
    const expected = [0, 0, 0, 1, 1, 1, -1, -1];
    const actual = threeNumberSort1(array, order);
    chai.expect(actual).to.deep.equal(expected);
  });

  it("#2 2nd Approach (Splitting into subarrays)", function () {
    const array = [1, 0, 0, -1, -1, 0, 1, 1];
    const order = [0, 1, -1];
    const expected = [0, 0, 0, 1, 1, 1, -1, -1];
    const actual = threeNumberSort2(array, order);
    chai.expect(actual).to.deep.equal(expected);
  });

  it("#3 3rd Approach (Two Passes)", function () {
    const array = [1, 0, 0, -1, -1, 0, 1, 1];
    const order = [0, 1, -1];
    const expected = [0, 0, 0, 1, 1, 1, -1, -1];
    const actual = threeNumberSort3(array, order);
    chai.expect(actual).to.deep.equal(expected);
  });
});

mocha.run();

Demo

https://codepen.io/evalteam/pen/xxPxorj