We can cut down the time and space complexities of shuffle with a bit of cleverness - namely, by swapping elements around within the array itself, we can avoid the linear space cost of the auxiliary array and the linear time cost of list modification.
- Generate a random integer between the current index and the last index of the array.
- Swap the elements at the current index and the chosen index.
Time complexity: O(n)
The Fisher-Yates algorithm runs in linear time, as generating a random index and swapping two values can be done in constant time.
Space complexity: O(n)
Although we managed to avoid using linear space on the auxiliary array from the brute force approach, we still need it for reset, so we're stuck with linear space complexity.