Problem

Given an array of length N where elements are in the range of 1 to N, and some elements may not be present, being represented by -1, rearrange the array such that A[i] = i. If an element i is not present, the position should be filled with -1.

Examples

Example 1:

1
2

Input: nums = [2, 3, -1, -1, 5, 4, -1, -1, 8, -1]
Output: [-1, -1, 2, 3, 4, 5, -1, -1, 8, -1]

Example 2:

1
2

Input: nums = [-1, -1, 3, 2, -1, 5]
Output: [-1, 2, 3, -1, -1, 5]

Solution

Method 1 - Simply iterate and swap with -1

Iterate through the array and place elements at their correct positions (A[i] = i). Use repeated swapping to ensure each element goes to its correct position.

  • If an element is -1 or already in its correct position, move to the next element.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Solution {
    public void rearrangeArray(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n; ) {
            if (arr[i] >= 0 && arr[i] != i) {
                int correctIndex = arr[i];
                if (arr[correctIndex] != arr[i]) {
                    swap(arr, i, correctIndex);
                } else {
                    i++;
                }
            } else {
                i++;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (arr[i] != i) {
                arr[i] = -1;
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr1 = {2, 3, -1, -1, 5, 4, -1, -1, 8, -1};
        sol.rearrangeArray(arr1);
        System.out.println("Rearranged array: " + Arrays.toString(arr1));  // Expected output: [-1, -1, 2, 3, 4, 5, -1, -1, 8, -1]

        int[] arr2 = {-1, -1, 3, 2, -1, 5};
        sol.rearrangeArray(arr2);
        System.out.println("Rearranged array: " + Arrays.toString(arr2));  // Expected output: [-1, 2, 3, -1, -1, 5]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def rearrangeArray(self, arr: List[int]) -> None:
        n = len(arr)

        for i in range(n):
            while arr[i] != -1 and arr[i] != i and arr[i] < n:
                correct_index = arr[i]
                if arr[correct_index] != arr[i]:
                    self.swap(arr, i, correct_index)
                else:
                    break
        
        for i in range(n):
            if arr[i] != i:
                arr[i] = -1
        
        print("Rearranged array:", arr)

    def swap(self, arr: List[int], i: int, j: int) -> None:
        arr[i], arr[j] = arr[j], arr[i]

# Example usage
sol = Solution()
arr1 = [2, 3, -1, -1, 5, 4, -1, -1, 8, -1]
sol.rearrangeArray(arr1)  # Expected output: [-1, -1, 2, 3, 4, 5, -1, -1, 8, -1]

arr2 = [-1, -1, 3, 2, -1, 5]
sol.rearrangeArray(arr2)  # Expected output: [-1, 2, 3, -1, -1, 5]

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in the array. Each element is moved to its correct position in a single pass.
  • 🧺 Space complexity: O(1), as the transformation is done in place without using extra space.