Remove elements having length less than `n`, in a LARGE sorted array

Question

At first let me explain what I want. Well, I have a sorted array like this

var arr = ["ab", "abcd", "abdf", "abcdd", "abcdd", "abcdfd", "abcdsss", "abcdefgh", "abcdsdsdsds"];

Now I need to remove all elements which string length is less than 5. Ok, Now my point is, is there any easiest way to find the index of the element that string length is 4. Likes here two elements contain string length 4. But I need the last one. If it is possible to get that index I can apply

arr.splice(0, (index+1));

And one thing, my original array contain 1 million data. Now how can I solve this?

Answer 1

You can use array filter to remove elements.

var arr = ["ab", "abcd", "abdf", "abcdd", "abcdd", "abcdfd", "abcdsss", "abcdefgh", "abcdsdsdsds"];
arr = arr.filter(function(item) { 
  return item.length > 4;
});
//["abcdd", "abcdd", "abcdfd", "abcdsss", "abcdefgh", "abcdsdsdsds"]

I don't know how you have one million items in the array, but maybe you could try to reduce that array in the server before sending it to the client. (I don't know exactly where your data comes from, but that is a lot of data for a javascript array);

Answer 2

While filter() is the simplest way, it'll be more efficient to use a simple for loop to find the index of the last element with length 4 (or whatever) and do a single slice() to get the result. Especially if the number of elements > length 4 is large.

var arr = ["ab", "abcd", "abdf", "abcdd", "abcdd", "abcdfd", "abcdsss", "abcdefgh", "abcdsdsdsds"],
    lastIndex = false;

// find the number of elements to be removed
for ( var i = 0; i < arr.length; i++ ) {
    if ( arr[i].length >= 5 ) {
        lastIndex = i;
        break; // break out of the loop
    }
}

// one single splice to get the result
arr.splice(0, lastIndex); 

// arr is now ["abcdd", "abcdd", "abcdfd", "abcdsss", "abcdefgh", "abcdsdsdsds"]

And here is a performance comparison of filter and loop & splice (above) strategies. As you can see the above method is leaps and bounds ahead of filter.