CODEWITHSUNDEEP
javascriptalgorithmperformance
StevenTsooo
StevenTsooo

Reputation: 508

Removing null at beginning and end of array

Looking for an algorithm that will remove null that occurs at the beginning and end of the array and nothing in between that is O(n)

For example:

[null, null, 1, 2, 3, null, null, null] -> [1, 2, 3]

[null, null, 1, 2, null, 3, null, null, null] -> [1, 2, null, 3]

[1, null, 2, 3, null, 4, null, null, null] -> [1, null, 2, 3, null, 4]

[null, null, 2, 3, null, 4, null, null, 5] -> [2, 3, null, 4, null, null, 5]

Upvotes: 0

Views: 214

Answers (3)

Stepan Shatkovski
Stepan Shatkovski

Reputation: 615

that would be the most efficient solution

function removeNullsFromEdges(array) {
  let indexOfFirstNumber = array.length;
  for (let i = 0; i < array.length; i++) {
    if (array[i] !== null) {
      indexOfFirstNumber = i;
      break;
    }
  }
  let indexOfLastNumber = array.length;
  for (let i = array.length - 1; i >= 0; i--) {
    if (array[i] !== null) {
      indexOfLastNumber = i;
      break;
    }
  }
  return array.slice(indexOfFirstNumber, indexOfLastNumber + 1);
}

Upvotes: 0

Nick
Nick

Reputation: 16576

Here's a relatively small solution that should be O(n). You do one pass to get the start and end positions of your array and then another pass when you do a .slice.

const trimmer = arr => {
  const positions = arr.reduce((acc, el, i) => {
    if(el !== null) {
      acc[1] = i + 1;
      if (acc[0] === undefined) acc[0] = i;
    }
    return acc;
  }, [undefined, undefined]);
  return arr.slice(...positions);
}

console.log(trimmer([null, null, 1, 2, 3, null, null, null]));
console.log(trimmer([null, null, 1, 2, null, 3, null, null, null]));
console.log(trimmer([1, null, 2, 3, null, 4, null, null, null]));
console.log(trimmer([null, null, 2, 3, null, 4, null, null, 5]));

Upvotes: 1

Bibberty
Bibberty

Reputation: 4768

Bit chunky but works.

const tests = [[null, null, 1, 2, 3, null, null, null],
[null, null, 1, 2, null, 3, null, null, null],
[1, null, 2, 3, null, 4, null, null, null],
[null, null, 2, 3, null, 4, null, null, 5]];

const strip = (arr) => {
  const end = arr.length-(arr.reverse().findIndex(a => a != null));
  const start = arr.reverse().findIndex(a => a != null);
  return arr.slice(start, end);
};

tests.forEach(a => console.log(strip(a)));

One single loop, checking start and end.

const tests = [[null, null, 1, 2, 3, null, null, null],
[null, null, 1, 2, null, 3, null, null, null],
[1, null, 2, 3, null, 4, null, null, null],
[null, null, 2, 3, null, 4, null, null, 5],
[null, null, null, null, null],
[null, 1, null, null, null, null]
];

const strip = (arr) => {
  let start = -1, end = -1, i = 0, x = arr.length - 1;
  while(start === -1 || end === -1) {
    if(start === -1 && arr[i] !== null) {
        start = i;
    }
    if(end === -1 && arr[x] !== null) {      
        end = x+1;
    }
    if(i === x) return [];
    x--;
    i++;
  }
  return arr.slice(start, end);
};




tests.forEach(a => console.log(strip(a)));

Ok, here is a super super simple solution.

const tests = [[null, null, 1, 2, 3, null, null, null],
[null, null, 1, 2, null, 3, null, null, null],
[1, null, 2, 3, null, 4, null, null, null],
[null, null, 2, 3, null, 4, null, null, 5],
[null, null, null, null, null]
];

const strip = (arr) => {
  while(arr[0] === null && arr.length > 0) {
    arr.shift();
  }
  while(arr[arr.length-1] === null && arr.length > 0) {
    arr.pop();
  }
  return arr;
};

tests.forEach(a => console.log(strip(a)));

Upvotes: 3

Related Questions