💬 Discord
Sign In
NeetCode #948LC-2634EasyJavaScript
← Back to All Problems

#948 · #2634 · Filter Elements from Array(过滤数组中的元素)

📌 Problem Statement & Constraints

Given an integer array arr and a function fn, return a new array containing only the elements for which fn(arr[i], i) is truthy. The built-in Array.filter must not be used.

💡 Core Algorithmic Approaches

  1. Iterate the array, evaluate fn(arr[i], i) for each element, and push the element when the predicate is truthy.
  2. The result length is unknown in advance, so push into a growing array.
  3. Preserve the original relative order of the kept elements.
  4. The exercise targets the semantics of filter: the predicate receives the element and its index.

💻 Benchmark Python3 Implementation

var filter = function(arr, fn) {
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        if (fn(arr[i], i)) {                  // keep when the predicate is truthy
            res.push(arr[i]);
        }
    }
    return res;
};

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the array.
💾 Space Complexity
O(n): the result can be as long as the input.

⚠️ Interview Pitfalls & Follow-ups

  • Passing only the element: the predicate may depend on the index.
  • Writing if (fn) instead of if (fn(...)): the former tests whether the function object is truthy, which is always true.
  • Deleting elements from arr in place: a new array should be built instead of modifying the input.