Apply Transform Over Each Element in Array - Solution & Explanation
Problem Statement
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] <= 109fnreturns an integer.
Approach Overview
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 1: Using a For Loop
This approach involves manually iterating over each element of the array using a for loop. For each element, we apply the provided function fn with the current element and its index as arguments. The result is then pushed into a new result array, which is returned at the end.
The C solution defines a function transformArray that takes an array, its size, and a function pointer. It allocates memory for a new result array, iterates over the input array, and applies the function fn, storing results in result. Finally, it returns the result array.
Complexity
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(n) for the resultant array.
Approach 2: Using Recursion
Another approach is to use recursion to apply the function to each element in the array. We define a recursive function that processes elements by moving from the start to the end of the array, applying transformations and constructing the result array.
In the recursive C solution, a helper function transformArrayRecursive is created. It recursively calls itself to apply the function to each element, building up the result array.
Complexity
Time Complexity: O(n)
Space Complexity: O(n) for result array and O(n) for function call stack.
Approach 3: traversal
We traverse the array arr, for each element arr[i], replace it with fn(arr[i], i). Finally, return the array arr.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).
Code
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using a For Loop | Time Complexity: O(n), where n is the number of elements in the array. |
| Using Recursion | Time Complexity: O(n) |
| traversal | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Apply Transform over each Element in Array (Transform) - Leetcode 2635 - JavaScript 30-Day Challenge • NeetCodeIO • 24,279 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Apply Transform Over Each Element in Array easy or hard?
Apply Transform Over Each Element in Array Python/Java solution
How to solve Apply Transform Over Each Element in Array in O(n)?
What is the best approach for Apply Transform Over Each Element in Array?
Is Apply Transform Over Each Element in Array asked at Google/Amazon/Meta?
What data structure is used in Apply Transform Over Each Element in Array?
What is the time complexity of Apply Transform Over Each Element in Array?
Ready to solve this problem?
Practice Apply Transform Over Each Element in Array with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor