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?
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.
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;
}
arr
. We iterate through each element of the array once.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
.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.
arr
is empty, the function should return an empty array.fn
always returns a falsy value, the function should return an empty array.fn
always returns a truthy value, the function should return a copy of the original array.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;
}
arr
. We iterate through each element of the array once.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
.