What’s the time complexitiy of a self removing filter function?

The code below removes duplicate chars from an array and replaces the array with the return value of the filtered array.

while (!nonRepeatingFound && charArray.length > 0) {
    let currentLetter = charArray[0];
    if (
      charArray.filter(
        (elm) => elm == currentLetter
      ).length == 1 ||
      charArray.length == 1
    ) {
      nonRepeatingFound = true;
    } else {
      charArray = charArray.filter(
        (elm) => elm !== currentLetter
      );
      currentLetter = charArray[0];
    } 

Once a non-repeating instance is found (or every element of charArray is removed) the while loop terminates.

So my initial thinking was this is O(n^2) because of the filter functions located within the while loop. However, considering that the filter function is removing duplicates while it iterates I no longer believe it is that simple.

An example with nothing but duplicates would take the longest but (as far as I can tell) the while loop will never iterate on every element in the original array but for only one instance of each char. Likewise, the filter methods iterate over less and less values as this code executes.

What is the big o notation of a problem like this?



Read more here: https://stackoverflow.com/questions/66327325/whats-the-time-complexitiy-of-a-self-removing-filter-function

Content Attribution

This content was originally published by securethebags at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.

%d bloggers like this: