1
  1. How can we sort an array A of positive integers in range [0,n^2/2] in O(n) time?
  2. How can we sort the array if integers are in range [0,n^3/2] in O(n)?

I am new to algorithms. I would appreciate if someone explains the significance of the range along with the solution.

Haroon S.
  • 2,533
  • 6
  • 20
  • 39

1 Answers1

0
#include<bits/stdc++.h>
using namespace std;
int main()
{
    unordered_map<int, int> map;
    int n;
    int *arr = new int [n];

    cin >> n;

    for(int i=0; i<n; i++)
        cin >> arr[i];

    int max = arr[0];
    for(int i=0; i<n; i++)   
        if(arr[i] > max)
            max = arr[i];

    for(int i=0; i<n; i++)
        map[arr[i]] = 1;

    int j = 0;
    for(int i=0; i<=max; i++)
        if(map[i] == 1)
            arr[j++] = i;

    for(int i=0; i<n; i++)
        cout << arr[i] << " ";
}

Use a hash map and increase the value at the key (that is the value of arr[i]) by one. After that loop through the hash map till the max value of the array that you has been found at the beginning. Overwrite the array at index j whenever the value at the particular key is found greater than 1. The resultant array is sorted.

Note: This only only works on positive non-repeating integers.

fayez
  • 1
  • This is not O(n), since you noticed yourself that you have to loop from `0` to `max`. The question is about doing it in O(n) time. Also, it's easily modified to work for all integers, allowing for repetitions. – Maurycyt Sep 07 '22 at 10:06
  • ***Never*** recommend the use of `#include` in an answer on Stack Overflow; read [this](https://stackoverflow.com/q/31816095/10871073) and then replace that line with the relevant standard header(s). – Adrian Mole Sep 10 '22 at 20:25