LeetCode 2804 - Array Prototype ForEach

This problem asks us to implement a custom version of the forEach method for arrays in JavaScript. The goal is to extend the Array.prototype so that any array can call forEach(callback, context) and execute the callback on each element.

leetcodeeasy

LeetCode Problem 2804

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

This problem asks us to implement a custom version of the forEach method for arrays in JavaScript. The goal is to extend the Array.prototype so that any array can call forEach(callback, context) and execute the callback on each element. The callback function receives three parameters: the current element value, its index, and the array itself. Additionally, the optional context argument should be used to bind the this keyword inside the callback.

The input consists of a valid array and a function, along with a context object. The expected output is that the array is mutated (or the callback is executed) for each element; the forEach method itself does not return a value. Constraints indicate that the array length can be large (up to 100,000 elements), so performance should be linear. Edge cases include empty arrays, arrays with mixed types, and using a null or empty context.

Key points to note are that we cannot use built-in array methods like forEach to implement this, and we must ensure the this binding works correctly.

Approaches

The brute-force approach is straightforward: manually loop over each element in the array and call the callback with the element, index, and array, while using Function.prototype.call to bind the context. This approach is both simple and sufficient because iterating linearly over the array is efficient for the constraints. There is no faster asymptotic solution because each element must be visited once.

The key insight is that the problem is essentially a linear iteration with context binding. By using a standard for loop and callback.call(context, ...), we achieve the correct behavior without relying on built-in array iteration methods.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Iterate manually, call callback on each element with context
Optimal O(n) O(1) Same as brute force; optimal given requirement to process each element

Algorithm Walkthrough

  1. Extend Array.prototype with a new method named forEach.
  2. The method accepts a callback function and an optional context object.
  3. Start a for loop from index 0 to this.length - 1 to iterate over the array.
  4. On each iteration, invoke callback.call(context, currentValue, index, this). This ensures the callback executes with the correct this value.
  5. The method does not return anything.
  6. After the loop completes, the array has been processed according to the callback logic.

Why it works: The loop guarantees that each element is visited exactly once in order. Using call ensures the correct binding of this to the provided context. The invariant is that after each iteration, the callback has been executed for the corresponding index.

Python Solution

# Python equivalent for testing, though Python does not modify Array.prototype
from typing import Any, Callable, List

def forEach(arr: List[Any], callback: Callable[[Any, int, List[Any]], None], context: Any) -> None:
    for i in range(len(arr)):
        callback(arr[i], i, arr)

Explanation: In Python, we define a standalone forEach function since Python lists do not have a prototype. The function loops over the array and calls the callback with the element, index, and array. Python does not have a direct equivalent of this, so context is ignored, but in JavaScript it would be applied using call.

Go Solution

package main

type Any interface{}

func ForEach(arr []Any, callback func(val Any, index int, arr []Any), context Any) {
    for i := 0; i < len(arr); i++ {
        callback(arr[i], i, arr)
    }
}

Explanation: Go does not have prototypes or this binding, so the context is unused. We simply loop over the slice and execute the callback with each element and index. This mirrors the linear iteration of JavaScript.

Worked Examples

Example 1

Input: [1,2,3], callback multiplies by 2, context {"context": true}

Iteration table:

Index Value Callback result Array state
0 1 2 [2,2,3]
1 2 4 [2,4,3]
2 3 6 [2,4,6]

Example 2

Input: [true,true,false,false], callback sets value to this, context {"context": false}

Index Value Callback result Array state
0 true {"context": false} [{"context": false},true,false,false]
1 true {"context": false} [{"context": false},{"context": false},false,false]
2 false {"context": false} [{"context": false},{"context": false},{"context": false},false]
3 false {"context": false} [{"context": false},{"context": false},{"context": false},{"context": false}]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is visited exactly once
Space O(1) No additional space besides loop variables

The complexity is optimal because every element must be processed. Only constant extra space is required.

Test Cases

# test cases
def test_forEach():
    arr1 = [1,2,3]
    forEach(arr1, lambda val, i, arr: arr.__setitem__(i, val*2), {"context": True})
    assert arr1 == [2,4,6]  # multiply by 2

    arr2 = [True, True, False, False]
    ctx = {"context": False}
    forEach(arr2, lambda val, i, arr: arr.__setitem__(i, ctx), ctx)
    assert arr2 == [ctx, ctx, ctx, ctx]  # set context

    arr3 = [True, True, False, False]
    forEach(arr3, lambda val, i, arr: arr.__setitem__(i, not val), {"context": 5})
    assert arr3 == [False, False, True, True]  # logical negation

    arr4 = []
    forEach(arr4, lambda val, i, arr: arr.__setitem__(i, val*2), {})
    assert arr4 == []  # empty array

test_forEach()
Test Why
[1,2,3] tests numerical transformation
[True, True, False, False] with context tests correct this binding
empty array tests edge case of no iteration
logical negation tests boolean transformation

Edge Cases

Empty Array: When arr is empty, the loop does not execute, and the array remains empty. This ensures no errors occur when the input is size 0.

Null or Undefined Context: If context is None or not provided, callback.call in JavaScript defaults this to undefined. Our implementation handles this by passing whatever is provided.

Mixed Data Types: Arrays may contain numbers, booleans, or objects. The callback receives the value as-is, and the implementation does not assume a type. This prevents type errors during iteration.

Very Large Arrays: With arr.length up to 100,000, the linear iteration ensures the implementation remains efficient and avoids stack overflows, as recursion is not used.