Filtering an array in JavaScript with out using any built in functions or a new array

Question

I have a min and a max. Iterating through an array I need to remove all elements that are in between min and max. I cannot use any built in array functions like splice and the array needs to stay in the original order. For Example the array [1,5,13,27,58] min = 10 max = 30 would return an array of [1,5,58]. I am looking for more of strategy of how to do this in N time complexity. This question is for interview prep.

Here is the code I have tried,

function filter_range(array, min, max) {
  for (var i = 0; i < array.length; i++) {
    if (min < array[i] && array[i] < max) {
      for (var j = i; j < array.length - 1; j++) {
        var temp = array[j]
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

var array = [1, 5, 23, 13, 59];
filter_range(array, 10, 30);
for (var i = 0; i < array.length; i++) {
  console.log(array[i])
}

@kevinternet, I just added the code I tried. I did not get it to work — Aaron
– Aaron, Commented Oct 18, 2016 at 16:28
The code in you inner loop is swapping elements, not removing anything. — Barmar
– Barmar, Commented Oct 18, 2016 at 16:30
Possible approach: do a first pass where you replace removed values with undefined (or null or whatever), and then do a second pass where you defragement the array by shifting elements down to the left. This is still O(n) time, because there are a fixed number of passes, and each pass only handles each element once. (So it's O(2n), which is O(n).) — apsillers
– apsillers, Commented Oct 18, 2016 at 16:31

Mike Cluck · Accepted Answer · 2016-10-18 16:44:11Z

4

You can pull this off by merely overwriting the Nth element in the array with the next value that fits within that range, where N is the number of values discovered so far. Then set the length of the array to the number of values you found.

function filter_range(array, min, max) {
  var nextIndex = 0;
  for (var i = 0, len = array.length; i < len; i++) {
    var value = array[i];
    if (value >= min && value <= max) {
      array[nextIndex++] = value;
    }
  }
  array.length = nextIndex;
}

function test(arr, min, max) {
  console.log('Input: ' + arr.join(', '));
  console.log('Range: [' + min + ', ' + max + ']');
  filter_range(arr, min, max);
  console.log('Output: ' + arr.join(', '));
  console.log('');
}

test([1, 2, 3], 1, 2);
test([1, 2, 3], 2, 3);
test([1, 2, 3, 4, 5], 2, 4);
test([1, 2, 3], 0, 100);
test([1, 5, 13, 27, 58], 10, 30);
test([1, 13, 5, 58, 27], 10, 30);

edited Oct 18, 2016 at 16:44

answered Oct 18, 2016 at 16:39

Mike Cluck

32.6k13 gold badges84 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Razvan Marian Brinzila · Accepted Answer · 2016-10-18 16:34:10Z

-2

easiest way I can think of is moving the good values to a new array

  function run(){
  var a = [1,5,13,27,58];
  var b = [];
  var min = 10;
  var max = 30;

  alert (a);

  for (i=0;i<a.length;i++){
    if (a[i]>max || a[i]<min) {
      b.push(a[i]);
    }
  }

  alert (b);
}

answered Oct 18, 2016 at 16:34

Razvan Marian Brinzila

324 bronze badges

1 Comment

Barmar Over a year ago

The title says you can't use a new array.

Collectives™ on Stack Overflow

Filtering an array in JavaScript with out using any built in functions or a new array

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related