Intuition:

To shuffle an array randomly, we can iterate through each element in the array and swap it with a randomly chosen element from the remaining unshuffled elements. This process ensures that each permutation of the array has an equal probability of being generated. It is also known as the Fisher-Yates shuffle algorithm.

Solution:

from typing import List
import random

def shuffle_array(nums: List[int]) -> List[int]:
    shuffled_nums = nums[:]  # Create a copy of the original array
    
    # Iterate through each element in the array
    for i in range(len(shuffled_nums)):
        # Generate a random index to swap with
        j = random.randint(i, len(shuffled_nums) - 1)
        # Swap the current element with the randomly chosen element
        shuffled_nums[i], shuffled_nums[j] = shuffled_nums[j], shuffled_nums[i]
    
    return shuffled_nums

# Test case
nums = [1, 2, 3, 4, 5]
result = shuffle_array(nums)
print(result)  # Output should be a randomly shuffled version of nums

Time Complexity:

  • The time complexity of the shuffle_array function is O(n), where n is the number of elements in the array.
  • In each iteration of the loop, we generate a random index and perform a constant-time swap operation.
  • Since we iterate through each element of the array once, the overall time complexity is linear in terms of the number of elements.

Space Complexity:

  • The space complexity of the shuffle_array function is O(n), where n is the number of elements in the array.
  • We create a copy of the original array to store the shuffled elements, which requires additional space proportional to the size of the input array.
  • Therefore, the space complexity is linear in terms of the number of elements in the array.