Watch 10 video solutions for Apply Transform Over Each Element in Array, a easy level problem. This walkthrough by NeetCodeIO has 23,802 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array arr and a mapping function fn, return a new array with a transformation applied to each element.
The returned array should be created such that returnedArray[i] = fn(arr[i], i).
Please solve it without the built-in Array.map method.
Example 1:
Input: arr = [1,2,3], fn = function plusone(n) { return n + 1; }
Output: [2,3,4]
Explanation:
const newArray = map(arr, plusone); // [2,3,4]
The function increases each value in the array by one.
Example 2:
Input: arr = [1,2,3], fn = function plusI(n, i) { return n + i; }
Output: [1,3,5]
Explanation: The function increases each value by the index it resides in.
Example 3:
Input: arr = [10,20,30], fn = function constant() { return 42; }
Output: [42,42,42]
Explanation: The function always returns 42.
Constraints:
0 <= arr.length <= 1000-109 <= arr[i] <= 109fn returns an integer.Problem Overview: You receive an array arr and a transformation function fn. The task is to apply fn to every element in the array and return a new array containing the transformed results. The function typically receives the element and its index, similar to the behavior of map() in many programming languages.
Approach 1: Using a For Loop (Time: O(n), Space: O(n))
The most direct solution iterates through the array once and applies the transformation function to each element. For each index i, compute fn(arr[i], i) and append the result to a new output array. This approach uses simple iteration and avoids additional overhead from function calls or recursion. Since each element is processed exactly once, the time complexity is O(n). The output array stores n transformed elements, giving a space complexity of O(n). This approach works well in any language and mirrors how a built‑in map implementation works internally.
From a data structures perspective, the problem operates purely on an array. The algorithm performs sequential access, which is cache-friendly and efficient. If you were implementing functional utilities or building a lightweight version of map, this loop-based strategy is the most practical and readable.
Approach 2: Using Recursion (Time: O(n), Space: O(n))
A recursive solution processes the array element by element through function calls. The base case stops when the index reaches the array length. Otherwise, compute the transformed value for the current index and combine it with the recursive result of the remaining elements. Conceptually, the recursion simulates iteration: each call handles one element and delegates the rest of the work to the next call.
The time complexity remains O(n) because each element is still processed once. However, recursion adds call stack overhead, resulting in an additional O(n) stack space in the worst case. This makes it slightly less efficient than the iterative approach for large arrays. Still, recursion is useful when practicing recursion patterns or demonstrating functional-style transformations common in functional programming.
Recommended for interviews: The iterative for loop approach is what interviewers usually expect. It clearly shows you understand array traversal and function application while keeping both time and space complexity optimal at O(n). Mentioning recursion can demonstrate conceptual depth, but the loop version is typically preferred because it avoids unnecessary stack usage and keeps the implementation straightforward.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| For Loop Iteration | O(n) | O(n) | Best general solution. Efficient traversal and minimal overhead. |
| Recursion | O(n) | O(n) | Useful for practicing recursive thinking or functional-style transformations. |