Ninja's task

Moderate
0/80
Average time to solve is 30m
2 upvotes
Asked in companies
SamsungSnapdeal Ltd.

Problem statement

Ninja’s teacher has given him a task to sort a list of the numbers containing N numbers. But the teacher has added the condition that as the range of the numbers in the list is limited, he must do this task in linear time complexity.

Your task is to help Ninja to complete the task.

Example 
If n = 10 and nums = [1, 6, 0, -1, 9, 4, 32, 76, -98, 3], then the sorted list would be [-98, -1, 0, 1, 3, 4, 6, 9, 32, 76].
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of the input contains an integer ‘N’ denoting the number of elements in the list.

The next line contains N space-separated integers denoting the elements in the list.
Output Format 
For each test case return the sorted list.

Note:- You don’t need to take input or print anything. This already has been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= N <= 5000
-10^3 <= nums[i] <= 10^3, where 0<=i<N-1
Sample Input 1
2
5
1 2 8 3 0
7
1 -1 9 0 3 4 8
Sample output 1
0 1 2 3 8 
-1 0 1 3 4 8 9
Explanation :
For the first test case,
Given array is [1,2,8,3,0]
So the sorted array will be [0,1,2,3,8]

For the second test case,

Given array is [1,-1,9,0,3,4,8]
So the sorted array will be [-1,0,1,3,4,8,9]
Sample input 2 :
2
6
4 3 2 1 0 -1
5
1 2 3 4 5
Sample output 2 :
-1 0 1 2 3 4
 1 2 3 4 5
Hint

Think of implementing a sorting algorithm, similar to hashing.

Approaches (1)
Using Count sort

Approach:

In count sort first, we find the number of the object with the specific key values, similar to what we do in hashing.

Then we will find the position of each object in the output.

Algorithm:

  • Take an array numCount of size equal to the range of elements of a given array.
  • Now store the occurrence of each element in the numCount array but Subtract the minimum element of the given array from every element of the numCount array such that any negative index becomes positive.

numCount[a[i] - min]+=1; where ‘a’ is the given array and min is the minimum element in the given array.

  • Modify the numCount array such that each element in the array is equal to the sum of the current value and the previous value.

numCount[i] = numCount[i] + numCount[i-1].

  • Now numCount indicates the position of the element in the array.
  • Place each element in the ans array as index calculated and after placing the element, decrease its count by one.

ans[numCount[a[i] - min] - 1] = a[i];

Time Complexity

O(n+k) 

where ‘n’ is the length of a given array and ‘k’ is the range of elements in the given array.

As we will iterate every element once and we will also iterate the numCount array which is of the size of the range of the given array.

Space Complexity

O(n+k) 

where ‘n’ is the length of a given array and ‘k’ is the range of elements in the given array.

The numCount array will store k elements in the array and ans array will store n elements.

Code Solution
(100% EXP penalty)
Ninja's task
Full screen
Console