LeetCode 2634 - Filter Elements from Array

The problem asks us to implement a function that filters an array based on a custom condition defined by another function fn.

leetcodeeasy

LeetCode Problem 2634

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

The problem asks us to implement a function that filters an array based on a custom condition defined by another function fn. The input consists of an integer array arr and a filtering function fn that can accept either one argument, the array element itself, or two arguments, the element and its index. The goal is to return a new array filteredArr that contains only the elements from arr for which fn returns a truthy value. In JavaScript or Python terms, a truthy value is any value that evaluates to True when coerced to a boolean.

The array can have between 0 and 1000 elements, and the integers can range from -10^9 to 10^9. The input guarantees valid integers and a proper function fn, so we do not need to handle invalid input types. Important edge cases include an empty array, all elements being falsey, and fn relying on the index rather than the value itself.

The challenge explicitly prohibits using the built-in Array.filter method, so we must implement the filtering logic manually.

Approaches

The most straightforward approach is to iterate over each element of the array, apply the fn function to it, and conditionally include it in the output if the result is truthy. This brute-force method is correct because it directly implements the filtering logic. Since the array length is at most 1000, this approach is already efficient enough, but we can also discuss the general principle.

The key insight is that the filtering process does not require any extra complex data structures or sorting. Each element is considered independently, and the result only depends on fn. This makes the problem naturally suited for a simple iterative solution, which is optimal for the constraints provided.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Iterate over each element, apply fn, and collect truthy results
Optimal O(n) O(n) Same as brute force; optimal because each element must be checked

Algorithm Walkthrough

  1. Initialize an empty list (or slice in Go) called filteredArr to store the elements that pass the filter.
  2. Loop over the array arr using an index i from 0 to the length of arr minus one.
  3. For each element arr[i], call the function fn(arr[i], i).
  4. Check if the result of fn is truthy. In Python, this means using if fn(arr[i], i):; in Go, use a boolean expression.
  5. If the result is truthy, append the element to filteredArr.
  6. After the loop, return filteredArr.

Why it works: The algorithm works because it preserves the order of elements and includes only those for which the filtering function returns a truthy value. Each element is checked exactly once, ensuring correctness and efficiency.

Python Solution

from typing import List, Callable, Union

def filter(arr: List[int], fn: Callable[..., Union[bool, int]]) -> List[int]:
    filteredArr = []
    for i, value in enumerate(arr):
        if fn(value, i):
            filteredArr.append(value)
    return filteredArr

In this Python implementation, we use enumerate to obtain both the element and its index. We then call fn with both parameters, relying on Python's truthy evaluation in the if statement. Elements passing the filter are appended to the result list. This directly follows the algorithm described above.

Go Solution

func filter(arr []int, fn func(int, int) bool) []int {
    filteredArr := []int{}
    for i, val := range arr {
        if fn(val, i) {
            filteredArr = append(filteredArr, val)
        }
    }
    return filteredArr
}

In Go, we initialize an empty slice and iterate over arr using range to get both index and value. We then call fn and append the element to filteredArr if fn returns true. Go requires explicit boolean return types, unlike Python's general truthy evaluation.

Worked Examples

Example 1: arr = [0, 10, 20, 30], fn = greaterThan10

i arr[i] fn(arr[i], i) filteredArr
0 0 False []
1 10 False []
2 20 True [20]
3 30 True [20, 30]

Output: [20, 30]

Example 2: arr = [1, 2, 3], fn = firstIndex

i arr[i] fn(arr[i], i) filteredArr
0 1 True [1]
1 2 False [1]
2 3 False [1]

Output: [1]

Example 3: arr = [-2, -1, 0, 1, 2], fn = plusOne

i arr[i] fn(arr[i], i) filteredArr
0 -2 -1 → True [-2]
1 -1 0 → False [-2]
2 0 1 → True [-2, 0]
3 1 2 → True [-2, 0, 1]
4 2 3 → True [-2, 0, 1, 2]

Output: [-2, 0, 1, 2]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is visited exactly once to apply the filtering function
Space O(n) We store at most all elements in the filtered array

The reasoning is that no nested iterations are required, and the only additional space is for the output array, which in the worst case contains all n elements.

Test Cases

# Provided examples
assert filter([0,10,20,30], lambda n, i: n > 10) == [20, 30]  # filter values > 10
assert filter([1,2,3], lambda n, i: i == 0) == [1]  # only index 0 passes
assert filter([-2,-1,0,1,2], lambda n, i: n + 1) == [-2,0,1,2]  # truthy after +1

# Edge and boundary cases
assert filter([], lambda n, i: True) == []  # empty array
assert filter([0,0,0], lambda n, i: n) == []  # all falsey
assert filter([1,2,3], lambda n, i: False) == []  # all filtered out
assert filter([1,2,3], lambda n, i: True) == [1,2,3]  # all included
assert filter([1000,-1000,0], lambda n, i: n >= 0) == [1000,0]  # mixed positive and zero
Test Why
[0,10,20,30], n>10 standard filter
[1,2,3], i==0 uses index
[-2,-1,0,1,2], n+1 handles truthy/falsy
[] empty array edge case
[0,0,0], n all elements falsey
[1,2,3], False all elements filtered
[1,2,3], True all elements included
[1000,-1000,0], n>=0 mix of positive, negative, zero

Edge Cases

One important edge case is an empty array. Since there are no elements, the function should return an empty array without any errors. The implementation handles this naturally because the loop does not execute.

Another edge case is when all elements evaluate to a falsey value. For example, [0,0,0] filtered with a function returning the element itself. The implementation correctly returns an empty array because the conditional check if fn(value, i) fails for every element.

A third edge case is when the filtering function relies on the index rather than the value. This could be a source of bugs if the implementation ignores the index. Our implementation correctly passes both the value and index to fn, ensuring that filters like i==0 or i%2==0 work as expected.