Reorganize The Array

Given an array of elements arr[] with indices ranging from 0 to arr.size() – 1, your task is to write a program that rearranges the elements of the array such that arr[i] = i. If an element i is not present in the array, -1 should be placed at the corresponding index.

Examples:

Input: arr[] = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
Output: [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
Explanation: Here We can see there are 10 elements. So, the sorted array will look like [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] but in our array we are not having 0, 5, 7 and 8. So, at there places we will be printing -1 and otherplaces will be having elements.

Input: arr[] = [2, 0, 1]
Output: [0, 1, 2]
Explanation: Here We can see all the elements are present so no -1 is returned in array.

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).

Constraints:
0 ≤ arr.size() ≤ 10⁵
-1 ≤ arr[i] ≤ arr.size()-1

Approach 01:

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> rearrange(const vector<int>& numbers) {
        int size = numbers.size();
        unordered_map<int, int> frequencyMap;
        vector<int> resultArray(size, -1);

        // Count frequencies of each number
        for (int number : numbers) {
            frequencyMap[number]++;
        }

        // Assign values to resultArray based on frequency map
        for (int i = 0; i < size; ++i) {
            if (frequencyMap.find(i) != frequencyMap.end()) {
                resultArray[i] = i;
            }
        }

        return resultArray;
    }
};

import collections

class Solution:
    def rearrange(self, numbers):
        size = len(numbers)
        frequencyMap = collections.Counter(numbers)
        resultArray = [-1] * size
        
        for i in range(size):
            frequency = frequencyMap.get(i)
            if frequency is not None:
                resultArray[i] = i
        
        return resultArray

Time Complexity

• Counting frequencies:

  The function iterates through the input vector to count the frequency of each number and store it in an unordered map. This takes \(O(n)\), where \(n\) is the size of the input vector.

• Building the result array:

  The function then iterates through the indices from 0 to \(n-1\), and for each index, it checks if the number exists in the frequency map and assigns it to the result array. This takes \(O(n)\) as well.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the input vector, because both the frequency counting and result array construction each take linear time.

Space Complexity

• Auxiliary Space:

  The function uses an unordered map to store the frequencies of the numbers. In the worst case, the map will store \(n\) elements. Additionally, the result array has a size of \(n\). Therefore, the space complexity is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the size of the input vector, due to the space used by the unordered map and the result array.