Shuffle array using random integer API

You are given an array nums of length n representing a deck of distinct cards.

You do not have access to a built-in shuffle function, but you are given the following API:

Task

Implement a function shuffle(nums) that randomly permutes the array in place such that every one of the n! permutations is equally likely.

Requirements

• You may only use rand_int(l, r) as your source of randomness.
• The algorithm should run in O(n) time and O(1) extra space.
• You may assume rand_int itself is perfectly uniform and independent between calls.

Describe your algorithm, argue why the resulting permutation is uniform, and give the time and space complexity.