2634. Filter Elements from Array
Problem Description
In this problem, you are provided with two main elements: an integer array arr
and a function fn
which acts as a filter. The goal is to construct a new array, filteredArr
, that contains only certain elements from the original array arr
. To decide which elements make it into filteredArr
, you use the filter function fn
.
The function fn
can accept one or two parameters. The first parameter is an element from the array (arr[i]
), and the second parameter is the index of that element within the array (i
). The role of fn
is to evaluate each element (and its index) and return a truthy value if the element should be included in the filtered array or a falsy value if it should not. In JavaScript, a truthy value is any value that, when converted to a boolean, becomes true
.
The requirement of the problem is to write your own filter logic without using the built-in Array.filter
method provided by JavaScript. This is a fundamental programming task that reinforces your understanding of array iteration and conditional statements.
Intuition
The intuition behind the solution involves iterating through the given array, analyzing each element using the provided function fn
, and selectively gathering items into a new array based on the result of that function. The steps to arrive at the solution are quite straightforward:
- Initialize a new array, let's call it
ans
, to store the elements that satisfy the filtering condition. - Loop through each element of the original array
arr
using afor
loop. As we loop through, we have access to both the current elementarr[i]
and its indexi
. - On each iteration, apply the filter function
fn
to the current element and its index. If the function returns a truthy value, include this element in theans
array by adding (pushing) it. - After going through all the elements in
arr
, end the loop and return theans
array as the filtered array.
By following these steps, you effectively replicate the behavior of the Array.filter
method using basic iteration and conditional logic. This method ensures that the original array remains unchanged while producing a new array that meets the specified filtering criteria.
Solution Approach
The implementation of the solution uses a simple and effective algorithm that involves array traversal and conditional logic:
-
Array traversal: We start by iterating through each element of the input array
arr
using afor
loop. The loop runs from the beginning to the end of the array, granting us access to every element and its corresponding index. -
Apply the filter function: During each iteration of the loop, we invoke the function
fn
with two arguments: the current elementarr[i]
and its indexi
. The purpose offn
is to determine whether the element meets the filtering criteria specified. -
Conditional logic: If the function
fn
returns a truthy value, it signifies that the current element passes the filter condition and should be included in the resulting array. We check the result offn(arr[i], i)
with a simpleif
condition. -
Building the answer array: When the
if
condition is satisfied, we use theArray.prototype.push
method to add the current elementarr[i]
to a new array calledans
. This array is initialized beforehand to store all elements that meet the condition. -
Return the result: After the loop has finished processing all the elements in the input array, the
ans
array now contains all the elements for whichfn(arr[i], i)
returned a truthy value. We returnans
as the filtered array.
By following these steps, the code effectively filters the input array based on the logic defined in the filter function fn
without utilizing the built-in Array.filter
method. This approach demonstrates fundamental programming concepts like loops, conditionals, and array manipulation in TypeScript, which is the language of the provided solution.
Here is the code snippet provided using the steps mentioned above:
1function filter(arr: number[], fn: (n: number, i: number) => any): number[] {
2 const ans: number[] = [];
3 for (let i = 0; i < arr.length; ++i) { // Loop through array
4 if (fn(arr[i], i)) { // Apply filter function and check for truthy
5 ans.push(arr[i]); // Add element to answer array if condition is met
6 }
7 }
8 return ans; // Return filtered array
9}
Notice that no special data structures are needed for this task. An additional array ans
is the only requirement to gather filtered results. The given solution is straightforward, adhering to basic algorithmic patterns—an essential practice for any programmer to master.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a simple example to illustrate the solution approach:
Assume we have an integer array arr
and a filter function fn
defined as follows:
1const arr = [1, 2, 3, 4, 5];
2const fn = (element: number, index: number) => (element % 2 === 0);
In this example, our function fn
is designed to return true
for even numbers and false
for odd numbers.
Now, let's use these to walk through the filter function's steps:
-
Array traversal: We start by looking at each element of the array
arr
. The array elements are[1, 2, 3, 4, 5]
. -
Apply the filter function: For each element, we call the function
fn
:fn(1, 0)
returnsfalse
because 1 is odd.fn(2, 1)
returnstrue
because 2 is even.fn(3, 2)
returnsfalse
because 3 is odd.fn(4, 3)
returnstrue
because 4 is even.fn(5, 4)
returnsfalse
because 5 is odd.
-
Conditional logic: We check the result of the function for each occurrence:
- Because the call for
arr[0]
returnedfalse
, we do not include1
in theans
array. - The call for
arr[1]
returnedtrue
, so2
is included in theans
array. - The call for
arr[2]
returnedfalse
, so3
is not included. - Because
arr[3]
returnedtrue
,4
is added to theans
array. - Finally,
arr[4]
returnedfalse
, so5
is left out.
- Because the call for
-
Building the answer array: As we apply the filter function and evaluate the result, our
ans
array begins to build up with the even numbers[2, 4]
. -
Return the result: Once we've finished iterating through the entire
arr
array, the function ends, and the finalans
array[2, 4]
is returned, which contains only the elements from the arrayarr
that are even.
In conclusion, following the above steps and example, the filter function replicates Array.filter
behavior by creating a new array that only includes elements passing the filtering condition defined by fn
. The final result is an array of even numbers from the original array, demonstrating how the algorithm effectively selects elements based on specified criteria.
Solution Implementation
1def filter_by_function(array, filter_function):
2 """
3 Filters elements of an array based on a provided filter function.
4
5 :param array: The array to filter.
6 :param filter_function: The filter function used to determine if an element
7 should be included in the result array.
8 It takes the element value and index as its arguments.
9 :return: A new list with elements that pass the filter function condition.
10 """
11 result = [] # Initialize an empty list to hold the filtered results
12 for index, value in enumerate(array): # Loop over each item and its index in the array
13 if filter_function(value, index): # If the filter function returns 'true', include the element in the result list
14 result.append(value) # Append the current element to the result list
15 return result # Return the filtered list
16
1import java.util.ArrayList;
2import java.util.List;
3import java.util.function.BiPredicate;
4
5/**
6 * Filters elements of an array based on a provided filter function.
7 * @param array The array to filter.
8 * @param filterFunction The filter function used to determine if an element should be included in the result array.
9 * It takes the element value and its index in the array as its arguments.
10 * @return A new list with elements that pass the filter function condition.
11 */
12public List<Integer> filter(int[] array, BiPredicate<Integer, Integer> filterFunction) {
13 List<Integer> result = new ArrayList<>(); // Initialize an empty list to hold the filtered results
14 for (int index = 0; index < array.length; index++) {
15 if (filterFunction.test(array[index], index)) {
16 // If the filter function returns 'true', include the element in the result list
17 result.add(array[index]);
18 }
19 }
20 return result; // Return the filtered list
21}
22
1#include <vector>
2#include <functional> // For std::function
3
4/**
5 * Filters elements of a vector based on a provided filter function.
6 * @param inputArray - The vector to filter.
7 * @param filterFunction - The filter function used to determine if an element should be included in the result vector.
8 * It takes the element value and index as its arguments.
9 * @returns A new vector with elements that pass the filter function condition.
10 */
11std::vector<int> filter(const std::vector<int> &inputArray, const std::function<bool(int, int)> &filterFunction) {
12 std::vector<int> result; // Initialize an empty vector to hold the filtered results
13 for (int index = 0; index < inputArray.size(); ++index) {
14 if (filterFunction(inputArray[index], index)) {
15 // If the filter function returns 'true', include the element in the result vector
16 result.push_back(inputArray[index]);
17 }
18 }
19 return result; // Return the filtered vector
20}
21
1/**
2 * Filters elements of an array based on a provided filter function.
3 * @param {number[]} array - The array to filter.
4 * @param {Function} filterFunction - The filter function used to determine if an element should be included in the result array.
5 * It takes the element value and index as its arguments.
6 * @returns {number[]} A new array with elements that pass the filter function condition.
7 */
8function filter(array: number[], filterFunction: (value: number, index: number) => boolean): number[] {
9 const result: number[] = []; // Initialize an empty array to hold the filtered results
10 for (let index = 0; index < array.length; ++index) {
11 if (filterFunction(array[index], index)) {
12 // If the filter function returns 'true', include the element in the result array
13 result.push(array[index]);
14 }
15 }
16 return result; // Return the filtered array
17}
18
Time and Space Complexity
The time complexity of the provided code is O(n)
, where n
is the length of the array arr
. This is because the function iterates through each element of the array exactly once.
The space complexity of the function is O(1)
, ignoring the space consumption of the ans
array, since there are no additional data structures that grow with the size of the input. The variables ans
and i
use a fixed amount of space regardless of the input size.
In a binary min heap, the minimum element can be found in:
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.