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

Good thing is that you have the array sorted on the length, bad new is that you have array of 100,000+ elements.

Regex on string is faster than the looping over array(specially in case of 100k+ elements)

You can use regex to get the last elements with a specified length and then you can use splice on the array using the index.

1. Convert the array to string using join
2. Use regex to extract all the strings whose length is n
3. Get the last element from the matched set
4. Get the last index of this element from the original array
5. splice original array using this index

Demo

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

var matches = arr.join(",").match(/\b[a-z]{5}\b/ig) || [];

arr.splice(0, arr.lastIndexOf(matches[matches.length - 1]) + 1);

console.log(arr);
document.write(arr);

Regex Explanation

1. \b: Word Boundary
2. [a-z]: Matches all alphabets
3. {n}: Matches previous class exactly n times
4. i: Incase-sensitive match
5. g: Global, get all matches

---

Binary Search

You can also use Binary search to split your array in two equal sub-arrays and search in individual sub-array for the last element having the length specified. And then use this element to get the index of it and then splice the original array.

Search algorithm courtesy of Binary Search in Javascript

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

var copy = arr.slice();

function binarySearch(arr, len) {
  var mid = Math.floor(arr.length / 2);
  console.log(arr[mid], len);

  if (arr[mid].length === len && arr[mid + 1].length === len) {
    console.log('match', arr[mid], len);
    return binarySearch(arr.splice(mid));
  } else if (arr[mid].length === len) {
    return arr[mid];
  } else if (arr[mid].length < len && arr.length > 1) {
    console.log('mid lower', arr[mid], len);
    binarySearch(arr.splice(mid, Number.MAX_VALUE), len);
  } else if (arr[mid].length > len && arr.length > 1) {
    console.log('mid higher', arr[mid], len);
    binarySearch(arr.splice(0, mid), len);
  } else {
    console.log('not here', len);
    return -1;
  }
}

var result = binarySearch(copy, 5);

arr.splice(0, arr.lastIndexOf(result) + 1);

console.log(arr);
document.write(arr);

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.

Answer 3

following Tushar's comment, if the array is sorted, there is a more efficient lodash approach:

arr = _.takeWhile(arr, function(element){ return element.length < 5; });

--- old appaorch ---

You can use lodash to do this nice, clean and simple:

arr = _.filter(arr, function(element){return element.length < 5; };

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

// arr = _.filter(arr, function(element){return element.length < 5; });
arr = _.takeWhile(arr, function(element){ return element.length < 5; });

alert('filtered array: ' + arr);

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.1/lodash.min.js"></script>

Answer 4

We can also use .grep function of jquery like bellow

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

            arr=$.grep(arr,function (obj,i){
                return obj.length > 4
            })
            console.log('value is'+arr);

It also generally used to filter from a array

Answer 5

Try using do.. while loop

do {
  arr.splice(0,1)
} while (arr[0].length < 5)

Answer 6

Try something like this

1. Remove all elements that length less then 5

      var arrFiltered = arr.filter(function(element){ return element.length>=5});
   

2. Get index of last element with length 4

      var lastId = 0;
      var filteredElements = arr.filter(function(e){ 
                 return e.length === 4;
      };
   
      lastId = filteredElement[filteredElement.length-1]?arr.indexOf(filteredElement.pop());
   

Answer 7

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);