Filter Elements from Array

Easy

Asked by:

23 views

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.

Please solve it without 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

Constraints:

0 <= arr.length <= 1000
-10⁹ <= arr[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected data type of the elements within the input array `arr`, and are there any constraints on the range of possible values?
Can the input array `arr` be empty or null? If so, what should the function return?
Is the filtering function `fn` guaranteed to be a pure function (i.e., without side effects), and what are the expected data types of its input parameters and return value?
Does the order of the elements in the returned array need to be the same as their order in the original input array `arr`?
Are there any specific error conditions I should handle, such as if the provided `fn` throws an exception?

Brute Force Solution

Approach

The brute force approach to filtering elements means we check each element individually. For each element, we decide if it should be kept or removed based on a specific rule. This ensures we consider every element in the original collection.

Here's how the algorithm would work step-by-step:

Start by looking at the very first element.
Check if this element meets the criteria for keeping it (the filter condition).
If it does, put this element into a new collection.
If it doesn't, simply skip it and don't add it to the new collection.
Move on to the next element in the original collection and repeat the check.
Continue this process, element by element, until you have examined all elements from the original collection.
The new collection now contains only the elements that satisfy the specified criteria.

Code Implementation

def filter_elements(original_list, condition):
    filtered_list = []

    # Iterate through each element in the original list.
    for element_index in range(len(original_list)):
        current_element = original_list[element_index]

        # Check if the current element satisfies the condition.
        if condition(current_element):

            # Add the element to the filtered list.
            filtered_list.append(current_element)

    return filtered_list

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n elements in the input array once. For each element, it applies a filter condition, which we assume takes constant time, O(1). Therefore, the time complexity is dominated by the single iteration through the array, resulting in O(n) time complexity, where n is the number of elements in the input array.

Space Complexity

O(N) – The plain English description indicates that we create a new collection (e.g., a new list) to store elements that satisfy the filter condition. In the worst-case scenario, all N elements of the original collection might meet the criteria and be added to this new collection. Therefore, the auxiliary space required would be proportional to the number of elements in the original array, resulting in O(N) space complexity. No other significant data structures or recursive calls contribute to auxiliary space.

Optimal Solution

Approach

The best way to solve this problem is to carefully select which array elements should be kept based on a specific rule. We go through the array once and decide what to keep, placing the kept items into a new collection.

Here's how the algorithm would work step-by-step:

Start with an empty new collection where we will keep the filtered elements.
Go through each element of the original array, one by one.
For each element, check if it matches the rule we have to filter by. The rule might be something like 'is the number greater than 5?' or 'is the string longer than 3 characters?'
If the element matches the rule, add it to the new collection.
If the element does not match the rule, skip it and continue to the next element in the original array.
Once you have checked every element in the original array, the new collection will contain only the elements that satisfy the filter rule.

Code Implementation

def filter_elements(original_array, filter_rule): 
    filtered_array = []

    # Iterate through each element in the original array.
    for element in original_array:

        # Apply the filter rule to determine if the element should be included.
        if filter_rule(element):

            filtered_array.append(element)

    return filtered_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array once, where n is the number of elements in the array. For each element, it performs a constant-time check against the filter rule. Adding an element to the new collection also takes constant time. Therefore, the time complexity is directly proportional to the number of elements in the input array, resulting in O(n).

Space Complexity

O(N) – The algorithm creates a new collection to store the filtered elements. In the worst-case scenario, where all elements in the original array satisfy the filter rule, the new collection will contain all N elements from the original array. Therefore, the auxiliary space used is proportional to the size of the input array, N. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or undefined input array	Return an empty array or throw an error depending on desired behavior.
Empty input array	Return an empty array as there are no elements to filter.
Null or undefined filtering function	Throw an error or return the original array, depending on the desired behavior.
Filtering function always returns true	Return a copy of the original array.
Filtering function always returns false	Return an empty array.
Large input array causing potential performance issues	Ensure the solution has O(n) time complexity and avoids unnecessary memory allocations.
Array contains non-integer values or mixed data types	Type-check elements within the filtering function or reject the input depending on the function's expected input types.
Filtering function throws an error	Catch the error and handle it appropriately, possibly by logging it and continuing with the next element or returning an error result.

Null or undefined input array

How to Handle:

Return an empty array or throw an error depending on desired behavior.

Empty input array

How to Handle:

Return an empty array as there are no elements to filter.

Null or undefined filtering function

How to Handle:

Throw an error or return the original array, depending on the desired behavior.

Filtering function always returns true

How to Handle:

Return a copy of the original array.

Filtering function always returns false

How to Handle:

Return an empty array.

Large input array causing potential performance issues

How to Handle:

Ensure the solution has O(n) time complexity and avoids unnecessary memory allocations.

Array contains non-integer values or mixed data types

How to Handle:

Type-check elements within the filtering function or reject the input depending on the function's expected input types.

Filtering function throws an error

How to Handle:

Catch the error and handle it appropriately, possibly by logging it and continuing with the next element or returning an error result.