Problem Description

You are given an integer array arr and a filtering function fn. Your task is to create and return a new filtered array filteredArr.

The filtering function fn accepts two parameters:

• arr[i] - the current number from the array
• i - the index of the current element

To build filteredArr, you need to iterate through the original array and include only those elements where fn(arr[i], i) returns a truthy value. A truthy value is any value that evaluates to true when converted to a boolean using Boolean(value).

The implementation must be done manually without using the built-in Array.filter method.

For example, if you have an array [1, 2, 3] and a function that returns true for even numbers, the filtered array would be [2]. Or if the function returns true for elements at odd indices, the filtered array would be [2] (since 2 is at index 1).

The solution iterates through the array using a for loop, checks each element with the provided function, and pushes elements that pass the test into a new array. This approach has a time complexity of O(n) where n is the length of the input array, as it visits each element exactly once.

Intuition

The problem asks us to recreate the filtering functionality without using the built-in filter method. When we think about what filtering actually does, it's essentially examining each element in a collection and deciding whether to keep it or discard it based on some condition.

The natural approach is to mimic this process manually. We need to:

1. Look at each element one by one
2. Apply the given test function to determine if we should keep it
3. Collect the "keeper" elements somewhere

This leads us directly to the idea of creating an empty result array and iterating through the original array. For each element, we call the provided function fn with the element value and its index. If the function returns a truthy value, we know this element should be included in our filtered result.

The key insight is that filtering is fundamentally a selective copying operation - we're creating a new array that contains a subset of the original elements. We can't modify the original array in place because we need to return a new filtered array. Therefore, we need a temporary storage (the ans array) to collect our filtered elements as we go through the original array.

Using a simple for loop gives us access to both the element value arr[i] and its index i, which are exactly what the filtering function needs as arguments. When fn(arr[i], i) returns a truthy value, we add that element to our result using push(). This preserves the relative order of elements from the original array, which is an important characteristic of filtering operations.

Solution Approach

The solution uses a straightforward traversal approach to implement the filtering logic manually.

We start by initializing an empty array ans that will store our filtered results:

const ans: number[] = [];

Next, we iterate through the input array using a standard for loop from index 0 to arr.length - 1:

for (let i = 0; i < arr.length; ++i) {
    // processing logic here
}

For each element at position i, we evaluate the filtering condition by calling the provided function fn with two arguments:

• arr[i]: the current element value
• i: the current index

The critical part is the conditional check:

if (fn(arr[i], i)) {
    ans.push(arr[i]);
}

If fn(arr[i], i) returns a truthy value, we add the current element to our result array using the push() method. This ensures that only elements satisfying the filter condition are included in the final array.

Finally, we return the ans array containing all filtered elements:

return ans;

The algorithm maintains the original order of elements - if element A appears before element B in the original array, and both pass the filter, then A will appear before B in the filtered array as well. This property is preserved because we traverse the array sequentially and append elements in the order they're encountered.

The time complexity is O(n) where n is the length of the input array, as we visit each element exactly once. The space complexity is O(k) where k is the number of elements that pass the filter condition, which in the worst case could be O(n) if all elements pass the filter.

Example Walkthrough

Let's walk through a concrete example to see how the solution works step by step.

Given:

• Array: arr = [5, 12, 8, 3, 10]
• Filter function: fn = (val, index) => val > 7 (keeps elements greater than 7)

Step-by-step execution:

1. Initialize result array:

   • ans = []

2. Iteration 1 (i = 0):

   • Current element: arr[0] = 5
   • Evaluate: fn(5, 0) → 5 > 7 → false
   • Action: Don't add to ans
   • Result: ans = []

3. Iteration 2 (i = 1):

   • Current element: arr[1] = 12
   • Evaluate: fn(12, 1) → 12 > 7 → true
   • Action: Push 12 to ans
   • Result: ans = [12]

4. Iteration 3 (i = 2):

   • Current element: arr[2] = 8
   • Evaluate: fn(8, 2) → 8 > 7 → true
   • Action: Push 8 to ans
   • Result: ans = [12, 8]

5. Iteration 4 (i = 3):

   • Current element: arr[3] = 3
   • Evaluate: fn(3, 3) → 3 > 7 → false
   • Action: Don't add to ans
   • Result: ans = [12, 8]

6. Iteration 5 (i = 4):

   • Current element: arr[4] = 10
   • Evaluate: fn(10, 4) → 10 > 7 → true
   • Action: Push 10 to ans
   • Result: ans = [12, 8, 10]

Final Output: [12, 8, 10]

The filtered array contains only the elements greater than 7, maintaining their original relative order from the input array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array arr. The algorithm iterates through each element of the input array exactly once using a single for loop. Even though the callback function fn is called for each element, assuming the callback function has O(1) complexity, the overall time complexity remains linear.

Space Complexity: O(1) (excluding the output array). The algorithm only uses a constant amount of extra space for the loop variable i. If we include the output array ans in the space complexity analysis, it would be O(k) where k is the number of elements that satisfy the filter condition, which in the worst case could be O(n) when all elements pass the filter.

Common Pitfalls

1. Misunderstanding Truthy vs. True Values

A frequent mistake is assuming the filtering function must return exactly True or False. In reality, the function can return any value, and Python will evaluate its truthiness.

Problematic assumption:

def filter(arr, fn):
    filtered_result = []
    for index in range(len(arr)):
        # Wrong: checking for exact True value
        if fn(arr[index], index) == True:
            filtered_result.append(arr[index])
    return filtered_result

Why it's wrong: If fn returns truthy values like 1, "yes", or [1], the condition == True will fail even though these should pass the filter.

Correct approach:

def filter(arr, fn):
    filtered_result = []
    for index in range(len(arr)):
        # Correct: relies on Python's truthiness evaluation
        if fn(arr[index], index):
            filtered_result.append(arr[index])
    return filtered_result

2. Modifying the Original Array

Some developers might accidentally modify the input array instead of creating a new one.

Problematic approach:

def filter(arr, fn):
    # Wrong: modifying arr in-place
    i = 0
    while i < len(arr):
        if not fn(arr[i], i):
            arr.pop(i)
        else:
            i += 1
    return arr

Why it's wrong: This modifies the original array, which violates the requirement to return a new filtered array. Additionally, removing elements while iterating causes index shifting issues.

Correct approach: Always create and return a new list without modifying the original.

3. Index Confusion When Function Depends on Original Indices

When the filtering function depends on the index parameter, developers might mistakenly use the filtered array's index instead of the original array's index.

Example scenario:

# Filter function that keeps elements at even indices
fn = lambda val, idx: idx % 2 == 0

arr = [10, 20, 30, 40, 50]
# Expected: [10, 30, 50] (indices 0, 2, 4 from original)

Wrong mental model: Thinking the index parameter should reflect the position in the filtered result rather than the original array position.

4. Not Handling Edge Cases

Failing to consider edge cases like empty arrays or None values.

Incomplete implementation:

def filter(arr, fn):
    # Might fail if arr is None or has unexpected types
    filtered_result = []
    for index in range(len(arr)):
        if fn(arr[index], index):
            filtered_result.append(arr[index])
    return filtered_result

More robust approach:

def filter(arr, fn):
    # Handle None or empty input
    if not arr:
        return []
  
    filtered_result = []
    for index in range(len(arr)):
        try:
            if fn(arr[index], index):
                filtered_result.append(arr[index])
        except Exception:
            # Skip elements that cause errors in the filter function
            continue
  
    return filtered_result