Jumble numbers in an array such that no two adjacent numbers are same using JavaScript

Question

The idea it to basically not have repeated values in the array with similar values.

An example input array:

input = [1,2,2,2,2,3,4,5,6,7,8,9]

Expected output to be something like this:

desiredOutput = [1,2,3,2,4,2,5,2,6,2,7,8,9]

I have tried putting this in a for loop where it checks with the next item and if it is same, swaps the values. The problem is when I have continuous similar values.

Answer 1

maybe that could help you:

for(var i = 1; i < input.length; i++) {
    if(input[i-1] == input[i]) {
        var j = i;
        while(j < input.length && input[j] == input[i]) {
            j++;
        }
        var el = input[j];
        input[j] = input[i];
        input[i] = el;  
    }
}

Answer 2

Greedy Approach Using Max Heap

The idea is to greedily put the highest frequency numbers first.

1. Construct a max heap where every node is a tuple that stores the number & it's frequency.

2. Then extract the head of the max heap (the highest frequency node) and add it's value to the resultant array.

3. If there's a previous element then add it back to the heap.

4. Decrement the frequency of the extracted node and store it in prev, so that it can be added back after one iteration.

5. Finally return the solution if it exists otherwise return the string "Not Possible".

function solution(arr) {
  const maxHeap = Array.from(
    arr.reduce((m, i) => m.set(i, (m.get(i) ?? 0) + 1), new Map())
  ).sort(([, a], [, b]) => b - a);
  
  const res = [];
  let prev = null;
  
  while (maxHeap.length) {
    const maxNode = maxHeap.shift();
    res.push(maxNode[0]);
    maxNode[1] -= 1;
    if (prev) {
      maxHeap.push(prev);
      maxHeap.sort(([, a], [, b]) => b - a);
      prev = null;
    }
    if (maxNode[1] > 0) {
      prev = maxNode;
    }
  }
  return res.length < arr.length ? "Not Possible" : res;
}

console.log(JSON.stringify(solution([1, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9])));
console.log(JSON.stringify(solution([1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2])));
console.log(JSON.stringify(solution([1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3])));
console.log(JSON.stringify(solution([1, 1, 1, 1, 3, 3])));
console.log(JSON.stringify(solution([1, 1, 3])));

Note: I've not implemented a Max Heap (because it's tedious), I've simulated it with Array.prototype.sort.