CODEWITHSUNDEEP
arraysalgorithm
alwayscurious
alwayscurious

Reputation: 1165

Is there a more efficient way to distribute non-zero elements in an array?

Inputs: array = [0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0] and mid_space = 5

Expected Output: array = [0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0]

Essentially I want to "respace" the ones such that there are mid_space number of zeroes between them and the remaining zeroes are equally spaced at the front and back.

My existing approach is:

  1. to calculate the current spacing eg [3,4,3,9,4] and the expected_spacing [4,5,5,5,4]
  2. then the difference between these two: [1,1,2,-4,0]
  3. then insert a zero at the front, insert a zero after the next set of ones, insert 2 zeroes after the next set and so on.

I'm looking for a simpler and more efficient approach without using so much code as I would need to do here.

Any advice?

edit: To calculate the expected_spacing I first calculate the total number of spaces (23 here), then the remaining spaces after allocating a group of 5 to each set of ones 23 - (5 * 3[which is the number of sets of "11"]) = 8. Then This means that 8/2 = 4 on each of the start and end of the array.

Upvotes: 1

Views: 89

Answers (2)

trincot
trincot

Reputation: 350760

I would go with a solution that does not perform conversion to string, which comes with a performance impact:

function spread(array, midSpace) {
    let splitCount = 0, i = -2;
    while ((i = array.indexOf(1, i+2)) != -1) splitCount++;
    // Fill the result array with only zeroes
    let result = Array(array.length).fill(0);
    // Then populate the 1-values at the right spots
    for (let i = (array.length - splitCount * (midSpace + 2) + midSpace) >> 1; splitCount; splitCount--, i += midSpace) {
        result[i++] = 1;
        result[i++] = 1;
    }
    return result;
}

let input = [0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0];
console.log(String(spread(input, 5)));

In my tests this performed a couple of times faster than the solution that manipulates strings. The script I used for benchmarking is attached.

function spreadTrincot(array, midSpace) {
    let splitCount = 0, i = -2;
    while ((i = array.indexOf(1, i+2)) != -1) splitCount++;
    // Fill the result array with only zeroes
    let result = Array(array.length).fill(0);
    // Then populate the 1-values at the right spots
    for (let i = (array.length - splitCount * (midSpace + 2) + midSpace) >> 1; splitCount; splitCount--, i += midSpace) {
        result[i++] = 1;
        result[i++] = 1;
    }
    return result;
}

function spreadGrodzi(v, midSpace) {
    const s = 
      v.join('')
      .replace(/0/g,' ').trim() // skip leading/trailing zeros
      .replace(/ +/g, '0'.repeat(midSpace));   // replace any groups of zeros
    const n = Math.floor((v.length - s.length) / 2); // we assume there is at least one zero to be added, otherwise check for negativeness
    const v2 = ('0'.repeat(n) + s + '0'.repeat(v.length - s.length - n)
      ).split('').map(x => parseInt(x));
    return v2;
}

const delay = (ms=10) => new Promise(resolve => setTimeout(resolve, ms));
const asyncLog = msg => Promise.resolve(console.log(msg)).then(delay);

(async () => {
  let times = 50000;
  let input = [0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0];
  input = input.concat(input);
  input = input.concat(input);
  input = input.concat(input);
  input = input.concat(input);
  input = input.concat(input); // make input longer.
  let result, result2, start, delay;

  await asyncLog("input size is " + input.length);

  await asyncLog("calling trincot's function...");
  start = performance.now();
  for (let i = 0; i < times; i++) result = spreadTrincot(input, 5);
  delay = performance.now() - start;
  await asyncLog("trincot's function finishes in " + delay + "ms");

  await asyncLog("calling grodzi's function...");
  start = performance.now();
  for (let i = 0; i < times; i++) result2 = spreadGrodzi(input, 5);
  delay = performance.now() - start;
  await asyncLog("grodzi's function finishes in " + delay + "ms");

  await asyncLog("Check that outputs are same: " + (result+"" == result2+""));
})();

Upvotes: 2

grodzi
grodzi

Reputation: 5703

If it is not about efficiency in terms of perf but in terms of sweating

You can simply manipulate strings

  • truncate the leading/trailing zeros
  • replace any group of 0 by 5 zeros
  • complete the string on both start and end with appropriate zeros

const v = [0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0]
const s = 
  v.join('')
  .replace(/0/g,' ').trim() // skip leading/trailing zeros
  .replace(/ +/g, '00000')   // replace any groups of zeros
const n = Math.floor((v.length - s.length) / 2) // we assume there is at least one zero to be added, otherwise check for negativeness
const v2 = ('0'.repeat(n) + s + '0'.repeat(v.length - s.length - n)
  ).split('').map(x => parseInt(x))
console.log('bef', v.join(''))
console.log('aft', v2.join(''))

edit: floored n as spotted by @trincot, thx

Upvotes: 1

Related Questions