Filter Elements from Array

Problem

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.

Examples

Example 1:

1
2
3
4
5
6


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:

1
2
3
4
5
6


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:

1
2
3
4


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

Solution

Method 1 - Filtering the array

Here is the approach:

Iteration Through the Array:
- Both implementations iterate through the elements of the array.
- For each element, the function fn is applied.
Condition Check:
- If fn(arr[i], i) evaluates to true, the element arr[i] is added to filteredArr.
Functional Interface in Java:
- Java uses a BiPredicate<Integer, Integer> interface to define functions that take two arguments (the element and its index) and return a boolean.
Lambda Functions in Python:
- Python uses lambda functions (or any callable) that take the element and its index as arguments and return a boolean.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


import java.util.ArrayList;
import java.util.List;
import java.util.function.BiPredicate;

class Solution {
    public static List<Integer> filter(
        int[] arr, BiPredicate<Integer, Integer> fn) {
        List<Integer> filteredArr = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (fn.test(arr[i], i)) {
                filteredArr.add(arr[i]);
            }
        }
        return filteredArr;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};

        BiPredicate<Integer, Integer> isEven = (num, index) -> num % 2 == 0;
        BiPredicate<Integer, Integer> isGreaterThanIndex =
            (num, index) -> num > index;

        // Example filtering: keep only even numbers
        System.out.println(filter(arr, isEven)); // Output: [2, 4]

        // Example filtering: keep numbers greater than their index
        System.out.println(
            filter(arr, isGreaterThanIndex)); // Output: [1, 2, 3, 4, 5]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


 class Solution:
     def filter(self, arr: List[int], fn: Callable[[int, int], bool]) -> List[int]:
         filteredArr = []
         for i in range(len(arr)):
             if fn(arr[i], i):
                 filteredArr.append(arr[i])
         return filteredArr
 
 # Example usage
 if __name__ == "__main__":
     sol = Solution()
     arr = [1, 2, 3, 4, 5]
 
     # Example filtering: keep only even numbers
     is_even = lambda num, index: num % 2 == 0
     print(sol.filter(arr, is_even))  # Output: [2, 4]
 
     # Example filtering: keep numbers greater than their index
     is_greater_than_index = lambda num, index: num > index
     print(sol.filter(arr, is_greater_than_index))  # Output: [1, 2, 3, 4, 5]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    filter(arr, fn) {
        const filteredArr = [];
        for (let i = 0; i < arr.length; i++) {
            if (fn(arr[i], i)) {
                filteredArr.push(arr[i]);
            }
        }
        return filteredArr;
    }
}

// Example usage
const sol = new Solution();
const arr = [1, 2, 3, 4, 5];

// Example filtering: keep only even numbers
const isEven = (num, index) => num % 2 === 0;
console.log(sol.filter(arr, isEven)); // Output: [2, 4]

// Example filtering: keep numbers greater than their index
const isGreaterThanIndex = (num, index) => num > index;
console.log(sol.filter(arr, isGreaterThanIndex)); // Output: [1, 2, 3, 4, 5]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


type FilterFunction = (element: number, index: number) => boolean;

class Solution {
  filter(arr: number[], fn: FilterFunction): number[] {
    const filteredArr: number[] = [];
    for (let i = 0; i < arr.length; i++) {
      if (fn(arr[i], i)) {
        filteredArr.push(arr[i]);
      }
    }
    return filteredArr;
  }
}

// Example usage
const sol = new Solution();
const arr = [1, 2, 3, 4, 5];

// Example filtering: keep only even numbers
const isEven: FilterFunction = (num, index) => num % 2 === 0;
console.log(sol.filter(arr, isEven)); // Output: [2, 4]

// Example filtering: keep numbers greater than their index
const isGreaterThanIndex: FilterFunction = (num, index) => num > index;
console.log(sol.filter(arr, isGreaterThanIndex)); // Output: [1, 2, 3, 4, 5]

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 1 - Filtering the array#

Code#

Complexity#