Find The Derangement Of An Array - Leetcode Solution

Problem:

Given an array nums, write a function to return the "derangement" of nums.

A derangement is a permutation of the elements of a set, such that no element appears in its original position.

Example 1:

Input: nums = [1,2,3] Output: [2,3,1] Explanation: In this example, 1 appears in its original position, so it is moved to position 2. 2 appears in its original position, so it is moved to position 3. 3 appears in its original position, so it is moved to position 1.

Example 2:

Input: nums = [0,1,2,3] Output: [1,3,0,2] Explanation: In this example, each element is moved to a position different from its original position.

Note:

1. The input array nums contains distinct integers.

2. The length of nums is between 1 and 1000.

Solution:

One way to solve this problem is to use a while loop to keep shuffling the array until a derangement is found. We can define a derangement as a permutation of the elements of a set, such that no element appears in its original position. Therefore, we can check if a permutation is a derangement by checking if any element is in its original position.

Algorithm:

1. Initialize a boolean variable found_derangement to False.

2. While found_derangement is False do:

   a. Generate a random permutation of the input array nums.

   b. For each index i of nums, check if nums[i] is equal to the index i. If it is, break out of the loop.

   c. If the loop completes without finding any element in its original position, set found_derangement to True and return the permutation.

Code:

import random

def derangement(nums):
    found_derangement = False
    while not found_derangement:
        permutation = random.sample(nums,len(nums))
        for i in range(len(nums)):
            if permutation[i] == i:
                break
        else:
            found_derangement = True
    return permutation

nums = [1,2,3,4]
print(derangement(nums)) 

Time Complexity: O(n^2)

Space Complexity: O(n)

1