LeetCode 2635 - Apply Transform Over Each Element in Array

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

This problem asks us to implement a custom version of the array transformation operation, similar to JavaScript’s Array.map, but without using the built in Array.map method.

We are given two inputs:

An integer array arr
A mapping function fn

The goal is to return a new array where each element is the result of applying the function fn to the corresponding element in arr.

More formally, for every index i, we must compute:

returnedArray[i] = fn(arr[i], i)

This means the transformation function receives two pieces of information:

The current array element, arr[i]
The index of that element, i

The function can use either or both of these inputs to determine the transformed value.

For example, if arr = [1,2,3] and the function adds one to every element, the transformed array becomes [2,3,4].

If the function depends on the index, such as adding i to each value, then:

arr[0] + 0 = 1
arr[1] + 1 = 3
arr[2] + 2 = 5

resulting in [1,3,5].

The constraints tell us several important things about the scale of the problem:

The array length is at most 1000, which is relatively small.
Array values can range from -10^9 to 10^9, meaning values may be very large or negative.
The transformation function always returns an integer.

Since the array size is small, performance is not a major bottleneck. However, we still want an efficient and clean implementation.

An important detail is that we must create a new array rather than modifying the input array in place. This guarantees that the original array remains unchanged.

Several edge cases are worth identifying early:

The input array may be empty ([]), in which case the result should also be an empty array.
The function may ignore the value entirely and always return a constant.
The function may rely on the index, so we must pass both arr[i] and i correctly.
Negative numbers and very large integers may appear, so the implementation must avoid assumptions about positivity.

Because the problem guarantees valid input and a valid transformation function, we do not need to handle invalid cases.

Approaches

Brute Force Approach

The brute force solution is to iterate through the input array one element at a time, call the transformation function on every element, and append the result into a newly created array.

For each index i, we compute:

fn(arr[i], i)

and store the result in a separate output array.

This approach is correct because the problem explicitly defines the output as independently applying the transformation function to every element. Since every element must be processed exactly once, iterating through the entire array guarantees correctness.

Although this is called a brute force approach, it is already efficient enough for the given constraints. There is no unnecessary repeated work because each element only needs one transformation.

Optimal Approach

The key observation is that every element transformation is independent of every other element. There is no relationship between indices that requires extra computation or advanced data structures.

Since each array element only needs to be visited once, the optimal solution is simply a single pass through the array while constructing a new result array.

This works because:

Every output element depends only on one input element and its index.
No sorting, searching, or memoization is needed.
We can compute results immediately as we traverse the array.

Thus, the best possible solution is a straightforward linear scan.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Iterates through the array and stores transformed values in a new array
Optimal	O(n)	O(n)	Single pass transformation, this is effectively the same as brute force because every element must be visited

Algorithm Walkthrough

Create an empty result array that will store transformed values.
Iterate through the input array using an index from 0 to len(arr) - 1.
For each position i, retrieve the current value arr[i].
Call the transformation function as fn(arr[i], i).
Append the returned transformed value into the result array.
Continue until every element in the input array has been processed.
Return the completed result array.

Why it works

The algorithm works because it directly follows the problem definition. For every index i, we compute exactly:

returnedArray[i] = fn(arr[i], i)

Since we process every valid index exactly once and store the corresponding transformed result in the same order, the final array precisely matches the required output. The invariant maintained during execution is that after processing index i, the result array correctly contains transformed values for all positions from 0 through i.

Python Solution

from typing import List, Callable

class Solution:
    def map(self, arr: List[int], fn: Callable[[int, int], int]) -> List[int]:
        transformed_array = []

        for index in range(len(arr)):
            transformed_value = fn(arr[index], index)
            transformed_array.append(transformed_value)

        return transformed_array

The implementation begins by creating an empty list called transformed_array, which will hold the transformed values.

We then iterate through the input array using indices rather than directly iterating over values. This is important because the transformation function requires both the current element and its index.

Inside the loop, we call:

fn(arr[index], index)

The returned value is stored in transformed_value and appended to the result list.

Once all elements have been processed, the function returns the newly built array.

This implementation exactly mirrors the algorithm described earlier and avoids using the built in Array.map method, satisfying the problem requirements.

Go Solution

func map(arr []int, fn func(int, int) int) []int {
	result := make([]int, 0, len(arr))

	for index, value := range arr {
		transformedValue := fn(value, index)
		result = append(result, transformedValue)
	}

	return result
}

The Go implementation follows the same logic as the Python solution but uses Go idioms.

Instead of creating an empty slice without capacity, we initialize the result slice with a capacity equal to len(arr):

make([]int, 0, len(arr))

This optimization reduces memory reallocations while appending.

Go slices naturally handle empty arrays, so if arr is empty, the loop executes zero times and an empty slice is returned.

Integer overflow is not a concern under normal LeetCode execution because Go int values are sufficiently large for the problem constraints.

Worked Examples

Example 1

Input

arr = [1,2,3]
fn(n) = n + 1

Index	Current Value	Function Call	Result
0	1	fn(1, 0)	2
1	2	fn(2, 1)	3
2	3	fn(3, 2)	4

Final output:

[2,3,4]

The function ignores the index and simply increases every number by one.

Example 2

Input

arr = [1,2,3]
fn(n, i) = n + i

Index	Current Value	Function Call	Result
0	1	fn(1, 0)	1
1	2	fn(2, 1)	3
2	3	fn(3, 2)	5

Final output:

[1,3,5]

In this example, the index affects the transformation. Each value increases by its position in the array.

Example 3

Input

arr = [10,20,30]
fn() = 42

Index	Current Value	Function Call	Result
0	10	fn(10, 0)	42
1	20	fn(20, 1)	42
2	30	fn(30, 2)	42

Final output:

[42,42,42]

Since the function always returns 42, every element in the result array becomes 42.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is visited exactly once
Space	O(n)	A new array of size `n` is created

The time complexity is linear because we iterate through the array one time, performing a constant amount of work per element.

The space complexity is also linear because the problem requires returning a newly created transformed array. In the worst case, the result array contains the same number of elements as the input.

Test Cases

class Solution:
    def map(self, arr, fn):
        result = []

        for i in range(len(arr)):
            result.append(fn(arr[i], i))

        return result

solution = Solution()

# Provided examples
assert solution.map([1, 2, 3], lambda n, i: n + 1) == [2, 3, 4]  # plus one
assert solution.map([1, 2, 3], lambda n, i: n + i) == [1, 3, 5]  # add index
assert solution.map([10, 20, 30], lambda n, i: 42) == [42, 42, 42]  # constant function

# Boundary cases
assert solution.map([], lambda n, i: n) == []  # empty array
assert solution.map([5], lambda n, i: n * 2) == [10]  # single element

# Negative numbers
assert solution.map([-1, -2, -3], lambda n, i: n * 2) == [-2, -4, -6]  # negatives

# Large numbers
assert solution.map([10**9, -10**9], lambda n, i: n + 1) == [1000000001, -999999999]  # large values

# Index dependent transformation
assert solution.map([0, 0, 0], lambda n, i: i) == [0, 1, 2]  # uses index only

# Identity transformation
assert solution.map([4, 5, 6], lambda n, i: n) == [4, 5, 6]  # unchanged values

Test	Why
`[1,2,3] → plus one`	Verifies basic transformation
`[1,2,3] → n+i`	Ensures index is passed correctly
`[10,20,30] → 42`	Validates constant return functions
`[]`	Tests empty input handling
`[5]`	Verifies single element processing
Negative numbers	Ensures negative values work correctly
Large integers	Confirms handling of constraint limits
Index only transformation	Checks index dependent logic
Identity mapping	Ensures original values can be preserved

Edge Cases

Empty Array

An empty input array can easily cause bugs if the implementation assumes at least one element exists. For example, accessing arr[0] without checking length would fail.

This implementation handles the case naturally because the loop executes zero times. The result array remains empty and is returned immediately.

Functions That Ignore Input Values

Some transformation functions may ignore the array value or index entirely and always return the same constant.

For example:

fn() = 42

A naive implementation might accidentally depend on the input values. Our implementation always calls the function independently for each index, so constant transformations work correctly.

Index Dependent Transformations

A common source of bugs is forgetting to pass the index into the function or passing the wrong index.

For example:

fn(n, i) = n + i

If the implementation only passed the value and omitted the index, the output would be incorrect. Since our solution explicitly calls:

fn(arr[i], i)

the correct index is always provided.

Negative and Large Integers

Since array values may range from -10^9 to 10^9, implementations that make assumptions about positivity could fail.

Our solution performs no arithmetic itself and simply forwards values to the transformation function, so negative and large integers are handled safely and correctly.