# 384. Shuffle an Array

## brute force

<https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/>

A simple solution is to create an auxiliary array *temp\[]* which is initially a copy of *arr\[]*.&#x20;

Randomly select an element from *temp\[]*, copy the randomly selected element to *arr\[0]* and remove the selected element from *temp\[]*.&#x20;

Repeat the same process n times and keep copying elements to *arr\[1], arr\[2], … .* The time complexity of this solution will be O(n^2).

T: O(n^2)

```java
public int[] shuffle() {
    List<Integer> aux = getArrayCopy();

    for (int i = 0; i < array.length; i++) { // O(n)
        int removeIdx = rand.nextInt(aux.size());
        array[i] = aux.get(removeIdx);
        aux.remove(removeIdx); // this is also O(n)
    }

    return array;
}
```

## use fisher yates shuffle algorithm

refer:

{% embed url="<https://www.youtube.com/watch?v=CoI4S7z1E1Y>" %}

{% embed url="<https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm>" %}

T:O(n)

S:O(n)

```java
class Solution {

    int[] nums;
    Random rand;
    public Solution(int[] nums) {
        this.nums = nums;
        this.rand = new Random();
    }
    
    // The solution expects that we always use 
    // " the original array " to shuffle() else some of the test cases fail
    
    // because this q needs reset to nums, so we need keep nums
    public int[] reset() {
        return this.nums;
    }
    
    public int[] shuffle() {
        int[] clone = nums.clone();
        for (int i = nums.length - 1; i > 0; i--) {
            int j = rand.nextInt(i+1);
            int temp = clone[i];
            clone[i] = clone[j];
            clone[j] = temp;
        }
        return clone;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */
```

#### latest explain

```java
class Solution {

    private int nums[];
    private Random rand = new Random();
    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    public int[] reset() {
        return this.nums;
    }
    
    public int[] shuffle() {
        int[] clone = nums.clone();
        int n = clone.length;
        for (int i = n - 1; i > 0; i--) {
            int pickIdx = rand.nextInt(i+1); // 
            int temp = clone[i];
            clone[i] = clone[pickIdx];
            clone[pickIdx] = temp;
        }
        return clone;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 
 fisher-yates
 
 random()
 
 i from end (n-1) i > 0
 
 // random.nextInt(2) -> will generate 0~1
 
 random pik a poistion (0~n-1), do swap
 
 n-1 swap with random [0~n-1]
 
 n-2 swap with random [0~n-2]
 ..
 
 1 swap with random [0~1]
 
 

 
 
 T: O(n)
 S: O(n), this q needs keep original array
 */
```

ex:

so you can see the index and rand index maybe the same, means don't move&#x20;

```
i:2,pickIdx:2
i:1,pickIdx:1
i:2,pickIdx:0
i:1,pickIdx:0
```

```
 ex:["Solution","shuffle","reset","shuffle"]
[[[1,2,3]],[],[],[]]
 // i= 2 => 2+1 => 0~2
 
 i from 2 to 1, (0 不換
 i = 2 swap for all elements （0~2
 i = 1 swap for 0~1
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/math/384.-shuffle-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.