Given an array of integers, implement a function to shuffle the array randomly. Each permutation of the array should be equally likely.

Function Signature:

from typing import List
import random

def shuffle_array(nums: List[int]) -> List[int]:
    """
    Shuffles the array randomly.

    Parameters:
    - nums: A list of integers.

    Returns:
    - List[int]: The shuffled array.
    """
    # Your code here

Example:

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

Note:

  • All permutations of the array should have an equal probability of being generated.
  • You must use a random number generator to implement the shuffle algorithm.
  • You cannot use the Python built-in random.shuffle() function or any other library functions that directly implement shuffling.

Instructions:

  • Implement the shuffle_array function to solve the problem.
  • Use Python for your implementation and utilize the provided random module to generate random numbers.
  • Provide clear comments in your code to explain the logic.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊