LeetCode Problem Workspace
Filter Elements from Array
Filter elements from an array based on a custom function using core interview patterns.
0
Topics
1
Code langs
0
Related
Practice Focus
Easy · Filter Elements from Array core interview pattern
Answer-first summary
Filter elements from an array based on a custom function using core interview patterns.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Filter Elements from Array core interview pattern
In this problem, you need to filter elements from an array based on a custom function. The solution leverages a common interview pattern of using a filtering function to remove unwanted elements. The key challenge is ensuring the filtering logic is correct, including handling edge cases like empty arrays or functions that depend on indices.
Problem Statement
Given an integer array arr and a filtering function fn, return a new array containing only the elements for which the function evaluates to a truthy value. The fn function can take one or two arguments, where the second argument is the index of the element. For each element in arr, apply fn and keep the element if the result is truthy.
The problem involves filtering elements based on dynamic criteria, such as element value or index. Edge cases include handling an empty array or different types of filtering logic, ensuring that only truthy results are kept. This challenge tests your ability to implement conditional filtering and manage diverse filtering criteria.
Examples
Example 1
Input: arr = [0,10,20,30], fn = function greaterThan10(n) { return n > 10; }
Output: [20,30]
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]
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]
Falsey values such as 0 should be filtered out
Constraints
- 0 <= arr.length <= 1000
- -109 <= arr[i] <= 109
Solution Approach
Use Array's filter method
A straightforward solution is to use the filter() method provided by JavaScript arrays. This method takes a callback function (fn) that determines whether each element should be included in the result. The function evaluates each element in arr, and the elements for which fn returns a truthy value are included in the filtered array.
Custom Filtering Logic
Depending on the problem constraints, the filtering function may need to account for element values, indices, or both. For example, you may want to remove elements below a certain threshold, like all numbers greater than 10, or elements at specific positions, like the first index.
Handle Edge Cases
Make sure to handle edge cases such as an empty array, or functions that may not always return a truthy value. Consider whether the filtering function might introduce additional logic, such as filtering out specific numbers like zero or negative values.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The time complexity depends on the filtering function and the length of the array. The filter() method itself operates in linear time, so the overall time complexity is O(n), where n is the length of the input array. Space complexity is also O(n), as a new array is created for the filtered result.
What Interviewers Usually Probe
- Tests knowledge of JavaScript's
filter()method and custom function behavior. - Checks understanding of handling edge cases like empty arrays or non-truthy values.
- Evaluates ability to apply filtering criteria efficiently based on different inputs.
Common Pitfalls or Variants
Common pitfalls
- Not handling edge cases like an empty array or invalid return values from the filtering function.
- Assuming the
fnfunction can only handle values without considering indices. - Returning incorrect results due to misunderstanding what constitutes a truthy value in JavaScript.
Follow-up variants
- Filter based on both value and index.
- Apply filtering logic to a multidimensional array.
- Use custom filtering functions instead of predefined ones.
FAQ
How does the filter() method work in JavaScript?
The filter() method creates a new array with all elements that pass the test implemented by the provided function. It evaluates each element in the array and includes it in the result if the function returns a truthy value.
What is a truthy value in JavaScript?
A truthy value is any value that, when converted to a Boolean, evaluates to true. Examples include non-zero numbers, non-empty strings, and objects.
How can I filter elements by their index?
You can access the index of each element in the filtering function by using the second argument in the callback function. This allows you to filter based on both the element value and its position.
What is the time complexity of the filter() method?
The time complexity of the filter() method is O(n), where n is the length of the array, as it processes each element once.
How do I handle an empty array in this problem?
If the array is empty, the filter() method will simply return an empty array, as no elements can pass the filtering condition.
Solution
Solution 1: Traversal
We traverse the array $arr$ and for each element $arr[i]$, if $fn(arr[i], i)$ is true, we add it to the answer array. Finally, we return the answer array.
function filter(arr: number[], fn: (n: number, i: number) => any): number[] {
const ans: number[] = [];
for (let i = 0; i < arr.length; ++i) {
if (fn(arr[i], i)) {
ans.push(arr[i]);
}
}
return ans;
}