Problem overview
The method reverse takes an array of integers, nums, and returns a List[Int] with the same numbers in the opposite order. 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.
The task rules out built-in helpers such as reverse, so you write the loop yourself.
Approach
To build the reversed sequence, read nums from its last index down to index 0 and add each element to a new collection. The first element added is then the last element of nums, which is exactly what the reversed order needs.
Two choices shape the code. First, the loop has to count downwards, so a plain nums.indices won't do. Second, the result has to grow one element at a time, so you need a growable buffer rather than an array, since an array's size is fixed. At the end, the buffer becomes the List[Int] that the method promises to return.
Step by step
- Create the buffer. Declare
answeras an emptyscala.collection.mutable.ArrayBuffer[Int](). Type parameters in Scala go in square brackets. - Count down over the indices. The loop runs over
nums.size - 1 to 0 by -1. The last valid index isnums.size - 1. The wordtomakes the range include its end, so 0 is visited, andby -1sets the step so the range moves downward. Withoutby -1, a range from a larger number to a smaller one is empty. - Append each element. In the body,
answer += nums(i)adds the element at indexito the end of the buffer. - Convert and return. After the loop,
answer.toListturns the buffer into an immutable list, which matches the return type.
Tracing the example: i takes the values 4, 3, 2, 1, 0, and the buffer grows through [8], [8, 5], [8, 5, 1], [8, 5, 1, 9] and finally [8, 5, 1, 9, 2].
The solution in Scala
class Solution {
def reverse(nums: Array[Int]): List[Int] = {
val answer = scala.collection.mutable.ArrayBuffer[Int]()
for (i <- nums.size - 1 to 0 by -1) {
answer += nums(i)
}
return answer.toList
}
}
Scala details worth knowing:
- Ranges.
0 until 5gives 0, 1, 2, 3, 4 and leaves out 5.0 to 5includes 5. With a negative step,4 to 0 by -1gives 4, 3, 2, 1, 0. valand a growing buffer.val answerfixes which buffer the name points to, not how many elements it holds, so+=works on it.- Indexing with parentheses. Scala reads an element with
nums(i). - The input is untouched. The method builds a new list and never changes
nums.
Complexity
Time: O(n). The loop runs once for each of the n elements, and appending to an ArrayBuffer takes constant time on average. Converting to a list is one more pass over n elements, which is still O(n) in total.
Space: O(n). The result holds n numbers, and the buffer holds the same numbers until it is converted.
Edge cases and common mistakes
- Empty array. The range
-1 to 0 by -1is empty, so the loop doesn't run and the result is an empty list. - One element. The range is just
0, and the result is the same single number. - Starting at
nums.size. The last valid index isnums.size - 1. Starting atnums.sizereads past the end and throws anArrayIndexOutOfBoundsException. - Using
untilfor the end.nums.size - 1 until 0 by -1stops before 0 and never adds the first element, so the result is one element short. - Forgetting the step.
nums.size - 1 to 0counts upward by default, so for any array with more than one element the range is empty and the result is an empty list. - Returning the buffer. An
ArrayBufferisn't aList, so the buffer must be converted withtoList.
Testing
[2, 9, 1, 5, 8]gives[8, 5, 1, 9, 2].[4]gives[4].[]gives[].
