Filter Elements from Array
Easy
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 thearri- index ofarr[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 functionfnreturnstruefor every element, and thus thefilteredArrwill contain all elements from the originalarr.
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
arris empty, the function should return an empty array. - Filtering Function Always Returns False: If the filtering function
fnalways returns a falsy value, the function should return an empty array. - Filtering Function Always Returns True: If the filtering function
fnalways 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 functionfnreturnstruefor every element, and thus thefilteredArrwill contain all elements from the originalarr.
