Problem overview
The method reverse receives an array of numbers, nums, and returns a new array with the same numbers in reverse order. The task says not to use built-in helpers such as reverse(), so the loop has to do the work.
For nums = [2, 9, 1, 5, 8] the result is [8, 5, 1, 9, 2]: the last element comes first and the first element comes last.
Approach: read from the end, write to a new array
Build the answer one element at a time. Start with an empty array. Visit the indices of nums from the last one down to 0, and append each element to the answer as you go. The last element of nums is appended first, so it ends up first in the answer, and the first element is appended last.
For the example, the loop visits indices 4, 3, 2, 1 and 0, and the answer grows like this:
[8]
[8, 5]
[8, 5, 1]
[8, 5, 1, 9]
[8, 5, 1, 9, 2]
Step by step
- Create the answer array. Declare an empty
number[]namedanswer. It is built up during the loop and returned at the end. - Loop backwards over the indices. Start
iatnums.length - 1, the index of the last element. Continue whilei >= 0and subtract one after each iteration withi--. The condition uses>=so that index 0 is included. - Append each element.
answer.push(nums[i])adds the current element to the end ofanswer. - Return the answer after the loop, when every element has been copied.
The solution in TypeScript
class Solution {
reverse(nums: number[]): number[] {
let answer: number[] = [];
for (let i: number = nums.length - 1; i >= 0; i--) {
answer.push(nums[i]);
}
return answer;
}
}
Details worth knowing:
- The loop header has three parts. The first runs once before the loop (
let i: number = nums.length - 1), the second is checked before every iteration (i >= 0), and the third runs after every iteration (i--). - Annotations are optional.
: numberoniis allowed, but TypeScript would infer it anyway from the initial value. Types are erased when the code is compiled to JavaScript, so they don't change how the loop runs. - Numbers can go below zero. Unlike in some languages, a TypeScript
numberis a signed double, soi--from 0 gives-1and the loop condition fails cleanly. There is no wrap-around. - The input is not changed.
pushmodifies onlyanswer. After the call,numsstill holds its original order, whereas the built-innums.reverse()would reverse the array in place.
Complexity
Time: O(n). The loop runs once per element, and each push takes constant time on average.
Space: O(n). The answer array holds one entry per input element. Reversing in place with two indices that swap elements from both ends would need only O(1) extra space, but this task asks for a new array.
Edge cases and common mistakes
- Empty array.
nums.length - 1is-1, so the conditioni >= 0is false at once. The method returns[]. - One element. The loop runs once, and
[4]comes back as[4]. - Starting at
nums.length. That index is one past the end. Reading it givesundefined, and the answer would start with anundefinedelement:[undefined, 8, 5, 1, 9, 2]. - Using
i > 0. The first element, at index 0, would be left out. - Counting up by mistake. With
i >= 0as the condition andi++as the step,ionly grows, so the condition never becomes false and the loop never ends.
Testing
[2, 9, 1, 5, 8]gives[8, 5, 1, 9, 2].[]gives[].[4]gives[4].[1, 2]gives[2, 1].