Code Implementation

class Solution:
    def findDerangement(self, nums):
        n = len(nums)
        res = nums[:]
        for i in range(n - 1):
            if res[i] == nums[i]:
                res[i], res[i + 1] = res[i + 1], res[i]
        if res[-1] == nums[-1]:
            res[-1], res[-2] = res[-2], res[-1]
        return res
      

class Solution {
public:
    vector<int> findDerangement(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(nums);
        for (int i = 0; i < n - 1; ++i) {
            if (res[i] == nums[i]) {
                swap(res[i], res[i + 1]);
            }
        }
        if (res[n - 1] == nums[n - 1]) {
            swap(res[n - 1], res[n - 2]);
        }
        return res;
    }
};
      

class Solution {
    public int[] findDerangement(int[] nums) {
        int n = nums.length;
        int[] res = nums.clone();
        for (int i = 0; i < n - 1; i++) {
            if (res[i] == nums[i]) {
                int temp = res[i];
                res[i] = res[i + 1];
                res[i + 1] = temp;
            }
        }
        if (res[n - 1] == nums[n - 1]) {
            int temp = res[n - 1];
            res[n - 1] = res[n - 2];
            res[n - 2] = temp;
        }
        return res;
    }
}
      

var findDerangement = function(nums) {
    let n = nums.length;
    let res = nums.slice();
    for (let i = 0; i < n - 1; i++) {
        if (res[i] === nums[i]) {
            let temp = res[i];
            res[i] = res[i + 1];
            res[i + 1] = temp;
        }
    }
    if (res[n - 1] === nums[n - 1]) {
        let temp = res[n - 1];
        res[n - 1] = res[n - 2];
        res[n - 2] = temp;
    }
    return res;
};
      

Problem Description

Given an array nums containing n distinct integers, return any derangement of nums. A derangement is a permutation where no element remains in its original position; that is, for every index i, res[i] != nums[i].

• Each element must appear exactly once in the result.
• You only need to return one valid derangement.
• Do not reuse elements or leave any element out.

Thought Process

The problem asks for a permutation where no element stays in its original spot. The most straightforward way is to try all permutations and check if any is a derangement. However, generating all permutations is highly inefficient for large arrays.

Instead, we can look for a more direct approach. Since the array has unique elements, we can try to shuffle elements so that none are in their original position. A simple, greedy way is to swap elements with their neighbors whenever a conflict is detected.

This avoids the need for checking all permutations and instead constructs a derangement directly by making local swaps.

Solution Approach

• Step 1: Make a copy of nums to keep track of the derangement as we build it.
• Step 2: Iterate through the array from the first element to the second-to-last element.
• Step 3: For each index i, if the element at res[i] is the same as nums[i], swap it with the next element (res[i+1]).
• Step 4: After the loop, check if the last element is still in its original position. If so, swap it with the previous element.
• Why does this work? By always swapping with the next (or previous) element on conflict, we ensure that no element stays in its original spot. Since all elements are unique and the swaps are local, we avoid introducing new conflicts.
• Edge Cases: For arrays of size 1, no derangement is possible. For size 2, simply swap the two elements.

Example Walkthrough

Example: nums = [1, 2, 3, 4]

1. Start with res = [1, 2, 3, 4].
2. At i = 0, res[0] == nums[0] (1 == 1), so swap res[0] and res[1]: res = [2, 1, 3, 4].
3. At i = 1, res[1] == nums[1] (1 == 2) is false, so no swap.
4. At i = 2, res[2] == nums[2] (3 == 3), so swap res[2] and res[3]: res = [2, 1, 4, 3].
5. Check last element: res[3] == nums[3] (3 == 4) is false, so no swap needed.
6. Final derangement: [2, 1, 4, 3]. None of the elements are in their original positions.

Time and Space Complexity

• Brute-force: Generating all permutations is O(n!) time and O(n) space, which is infeasible for large n.
• Optimized Approach: The greedy swap method only requires a single pass through the array, so it runs in O(n) time and uses O(n) space for the result array.
• Why? Each element is checked once, and swaps are constant-time operations. No extra data structures are needed beyond the output array.

Summary

The derangement problem can be solved efficiently by making local swaps to avoid any element staying in its original position. This greedy strategy is both simple and effective, requiring only a single pass through the array. It avoids the inefficiency of generating all permutations and leverages the fact that all elements are unique. The solution is elegant due to its linear time and space complexity and its straightforward logic.