Taro Logo

Filter Elements from Array

Easy
Apple logo
Apple
Topics:
Arrays

Given an integer array arr and a filtering function fn, return a filtered array filteredArr.

The fn function takes one or two arguments:

  • arr[i] - number from the arr
  • i - index of arr[i]

filteredArr should only contain the elements from the arr for which the expression fn(arr[i], i) evaluates to a truthy value. A truthy value is a value where Boolean(value) returns true.

Solve it without using the built-in Array.filter method.

Example 1:

Input: arr = [0,10,20,30], fn = function greaterThan10(n) { return n > 10; }
Output: [20,30]
Explanation:
const newArray = filter(arr, fn); // [20, 30]
The function filters out values that are not greater than 10

Example 2:

Input: arr = [1,2,3], fn = function firstIndex(n, i) { return i === 0; }
Output: [1]
Explanation:
fn can also accept the index of each element
In this case, the function removes elements not at index 0

Example 3:

Input: arr = [-2,-1,0,1,2], fn = function plusOne(n) { return n + 1 }
Output: [-2,0,1,2]
Explanation:
Falsey values such as 0 should be filtered out

What is the time and space complexity of your solution? Can you think of any edge cases?

Solution


Naive Approach

The most straightforward approach is to iterate through the input array arr and apply the filtering function fn to each element. If fn returns a truthy value for an element, we add that element to a new array. Finally, we return the new array.

Code:

function filterArray(arr, fn) {
  const filteredArr = [];
  for (let i = 0; i < arr.length; i++) {
    if (fn(arr[i], i)) {
      filteredArr.push(arr[i]);
    }
  }
  return filteredArr;
}

Big O Analysis:

  • Time Complexity: O(n), where n is the length of the input array arr. We iterate through each element of the array once.
  • Space Complexity: O(n) in the worst case, where n is the length of the input array arr. This occurs when the filtering function fn returns true for every element, and thus the filteredArr will contain all elements from the original arr.

Optimal Approach

The optimal approach is essentially the same as the naive approach since we must check every element in the original array at least once. However, small tweaks can be done to improve readability.

Edge Cases:

  • Empty Input Array: If the input array arr is empty, the function should return an empty array.
  • Filtering Function Always Returns False: If the filtering function fn always returns a falsy value, the function should return an empty array.
  • Filtering Function Always Returns True: If the filtering function fn always returns a truthy value, the function should return a copy of the original array.

Code:

function filterArray(arr, fn) {
    const filteredArr = [];
    for (let i = 0; i < arr.length; i++) {
        if (fn(arr[i], i)) {
            filteredArr.push(arr[i]);
        }
    }
    return filteredArr;
}

Big O Analysis:

  • Time Complexity: O(n), where n is the length of the input array arr. We iterate through each element of the array once.
  • Space Complexity: O(n) in the worst case, where n is the length of the input array arr. This occurs when the filtering function fn returns true for every element, and thus the filteredArr will contain all elements from the original arr.