Problem Description

This problem asks you to implement a custom forEach method for JavaScript/TypeScript arrays. The goal is to extend the Array prototype so that any array can call array.forEach(callback, context).

The method should iterate through each element of the array and execute a callback function for each element. The callback function receives three arguments:

• currentValue: The current element being processed
• index: The index of the current element in the array
• array: A reference to the entire array

Additionally, the method accepts an optional context parameter that determines what this refers to inside the callback function. When the context is provided, the callback should be executed with that context as its this value.

Key requirements:

• The forEach method should not return any value (void return type)
• You should implement this without using built-in array methods
• The callback should be invoked for each element in the array in order from index 0 to length-1

For example, if you have an array [1, 2, 3] and a callback that doubles each value, after calling forEach, the array would be modified to [2, 4, 6]. The context object allows you to control the execution context of the callback function.

The solution uses a simple for loop to iterate through the array and callback.call(context, ...) to invoke the callback with the specified context and arguments for each element.

Intuition

The key insight is understanding how JavaScript's built-in forEach works under the hood. At its core, forEach is simply a loop that visits each element in an array and executes a function for each one.

To implement this, we need to think about the basic mechanics:

1. We need to traverse the array from start to end
2. For each element, we need to invoke the callback function
3. The callback needs access to three pieces of information: the current element, its index, and the full array

The straightforward approach is to use a for loop with an index counter i that goes from 0 to this.length - 1. At each iteration, we have:

• The current element: this[i]
• The current index: i
• The array itself: this (since we're extending the Array prototype)

The trickier part is handling the context parameter. In JavaScript, when you call a function normally like callback(), the this inside that function might not be what you expect. The context parameter allows users to explicitly set what this should be inside the callback.

This is where callback.call() comes in. The call() method lets us invoke a function while explicitly setting its this value. The first argument to call() becomes the this value inside the function, and subsequent arguments are passed as regular parameters.

So callback.call(context, this[i], i, this) means:

• Execute callback
• Set its this to context
• Pass this[i] as the first argument (currentValue)
• Pass i as the second argument (index)
• Pass this as the third argument (array)

This mirrors exactly how the native forEach behaves, allowing the callback to access all necessary information while respecting the provided execution context.

Solution Approach

The implementation follows a straightforward iterative approach using a traditional for loop to traverse the array elements.

Implementation Steps:

1. Method Extension: We extend Array.prototype to add our custom forEach method that accepts two parameters:

   • callback: The function to execute for each element
   • context: The optional object to use as this when executing the callback

2. Loop Structure: We use a standard for loop with index i starting from 0 and continuing while i < this.length:

   for (let i = 0; i < this.length; ++i)

   Here, this refers to the array instance on which forEach is called.

3. Callback Invocation: For each iteration, we invoke the callback using the call method:

   callback.call(context, this[i], i, this)

   This ensures:

   • The callback's this value is set to the provided context
   • The callback receives three arguments in order:
     • this[i]: The current element value
     • i: The current index
     • this: The entire array reference

4. No Return Value: The method completes without returning anything (void), as specified by the problem requirements.

Key Design Decisions:

• Using ++i (pre-increment) instead of i++ is a minor optimization that avoids creating a temporary variable, though the difference is negligible in modern JavaScript engines.

• The call method is essential here because it allows us to control the execution context. If we simply called callback(this[i], i, this), the this inside the callback would be undefined (in strict mode) or the global object (in non-strict mode), not the desired context.

• We iterate through all indices from 0 to length - 1, which handles both dense and sparse arrays correctly, executing the callback even for undefined elements (matching native forEach behavior).

The entire implementation is concise yet complete, requiring only a single loop and one function invocation per element, resulting in O(n) time complexity where n is the array length.

Example Walkthrough

Let's walk through a concrete example to see how our custom forEach implementation works.

Example Setup:

// Define our custom forEach
Array.prototype.forEach = function(callback, context) {
    for (let i = 0; i < this.length; ++i) {
        callback.call(context, this[i], i, this);
    }
};

// Create a sample array and context object
const numbers = [10, 20, 30];
const multiplier = {
    factor: 2,
    results: []
};

// Define a callback that uses the context
function multiplyAndStore(value, index, array) {
    // 'this' refers to the multiplier object
    const result = value * this.factor;
    this.results.push(`Index ${index}: ${value} * ${this.factor} = ${result}`);
}

// Execute forEach with context
numbers.forEach(multiplyAndStore, multiplier);

Step-by-step execution:

Iteration 1 (i = 0):

• Current element: this[0] = 10
• Execute: callback.call(multiplier, 10, 0, [10, 20, 30])
• Inside callback:
  • this = multiplier object
  • value = 10, index = 0, array = [10, 20, 30]
  • Calculates: 10 * 2 = 20
  • Pushes to results: "Index 0: 10 * 2 = 20"

Iteration 2 (i = 1):

• Current element: this[1] = 20
• Execute: callback.call(multiplier, 20, 1, [10, 20, 30])
• Inside callback:
  • this = multiplier object
  • value = 20, index = 1, array = [10, 20, 30]
  • Calculates: 20 * 2 = 40
  • Pushes to results: "Index 1: 20 * 2 = 40"

Iteration 3 (i = 2):

• Current element: this[2] = 30
• Execute: callback.call(multiplier, 30, 2, [10, 20, 30])
• Inside callback:
  • this = multiplier object
  • value = 30, index = 2, array = [10, 20, 30]
  • Calculates: 30 * 2 = 60
  • Pushes to results: "Index 2: 30 * 2 = 60"

Final Result:

console.log(multiplier.results);
// Output: [
//   "Index 0: 10 * 2 = 20",
//   "Index 1: 20 * 2 = 40", 
//   "Index 2: 30 * 2 = 60"
// ]

The key insight here is how callback.call(context, ...) allows the callback function to access properties and methods of the multiplier object through this. Without the context parameter, this.factor and this.results would be undefined, causing the callback to fail. This demonstrates why the call method is essential for properly implementing forEach with context support.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the array. The implementation uses a single for loop that iterates through each element of the array exactly once, calling the callback function for each element. Each callback invocation is assumed to be O(1) for basic operations, though the actual complexity depends on the callback implementation.

Space Complexity: O(1) for the forEach implementation itself. The method only uses a constant amount of extra space for the loop counter variable i. No additional data structures are created that scale with the input size. However, the total space complexity can vary depending on what the callback function does internally - if the callback creates new objects or data structures, that would add to the space complexity, but the forEach method itself maintains constant space usage.

Common Pitfalls

1. Modifying Array Length During Iteration

One of the most common pitfalls when implementing forEach is not handling cases where the callback function modifies the array's length during iteration. This can lead to skipped elements or accessing undefined indices.

Problem Example:

const arr = [1, 2, 3, 4, 5];
arr.forEach((val, i, array) => {
    if (val === 2) {
        array.push(6); // Adding elements during iteration
    }
    console.log(val);
});

In the basic implementation, the loop condition i < this.length is evaluated on each iteration, so adding elements will extend the loop, potentially causing infinite loops. Removing elements might skip some elements.

Solution: Cache the initial array length before starting the iteration:

Array.prototype.forEach = function(callback, context) {
    const len = this.length; // Cache initial length
    for (let i = 0; i < len; ++i) {
        if (i in this) { // Check if index still exists
            callback.call(context, this[i], i, this);
        }
    }
};

2. Not Handling Sparse Arrays Correctly

JavaScript arrays can be sparse (have "holes" where indices are missing). The native forEach skips these holes, but a naive implementation might not.

Problem Example:

const sparseArr = [1, , 3]; // Index 1 is a hole
sparseArr.forEach(val => console.log(val)); 
// Should only log: 1, 3 (not undefined for index 1)

Solution: Use the in operator to check if an index actually exists:

Array.prototype.forEach = function(callback, context) {
    for (let i = 0; i < this.length; ++i) {
        if (i in this) { // Only process existing indices
            callback.call(context, this[i], i, this);
        }
    }
};

3. Incorrect Context Binding in Arrow Functions

When the callback is an arrow function, attempting to bind a context won't work as arrow functions have lexically bound this that cannot be changed.

Problem Example:

const context = { multiplier: 2 };
[1, 2, 3].forEach((val) => {
    console.log(this.multiplier * val); // 'this' won't be 'context'
}, context);

Solution: Document this behavior and suggest using regular functions when context binding is needed:

// Use regular function for context binding
[1, 2, 3].forEach(function(val) {
    console.log(this.multiplier * val); // Works correctly
}, context);

4. Not Validating Callback Parameter

Failing to check if the callback is actually a function can cause runtime errors.

Problem Example:

[1, 2, 3].forEach("not a function"); // Should throw TypeError

Solution: Add type validation:

Array.prototype.forEach = function(callback, context) {
    if (typeof callback !== 'function') {
        throw new TypeError(callback + ' is not a function');
    }
  
    for (let i = 0; i < this.length; ++i) {
        if (i in this) {
            callback.call(context, this[i], i, this);
        }
    }
};

5. Performance Issues with Large Arrays

Using this.length directly in the loop condition causes property lookup on each iteration, which can impact performance for very large arrays.

Solution: Cache the length value:

Array.prototype.forEach = function(callback, context) {
    const len = this.length;
    for (let i = 0; i < len; ++i) {
        if (i in this) {
            callback.call(context, this[i], i, this);
        }
    }
};

These pitfalls highlight the importance of considering edge cases and following the native implementation's behavior closely when creating polyfills or custom implementations of built-in methods.