@singhabhinandan see this code..try to learn how this works...this code is awesome . thanks @marioquiroga2912 for this brilliant piece of code.

@marioquiroga2912 Just brilliant !! But you are not doing what it says to do. You are just appending the strings in the order they appear at their poisitions(which is a great idea though), here we have been told to implement counting sort. So I implemented it, but my 5th test case is failing(Seg fault), which i think is due to memory limits. i have used 3 arrays of size n(1<=n<=1000000), help please! Here's my submission link mySubmission

@marioquiroga2912 Just one correction, since all x(keys) are between 1 to 100. You don't need to allocate string ar[] of size 'n', 101 is enough and hence the limit of last for loop would also change.

Thank you for great solution. I think string ar[n]; - array size of 100 is enough.

brilliant

nic answer

You are truly an amazing guy !

there is still segmentation fault in test 5

really brilliant

really birilliant

Superb ! Everyone who has commented here (including me) has been like :

legend

this won't work for test case 5.

Seriously, This is a simple and yet elegant solution.

brilliant piece of code.

Hats Off!!! Awesome Code!

For anyone stuck at testcase #5: using same above solution, but need some revise: 1. ostringstream instead of string (ostringstream ar[100];) 2. 100 instead of n when alocate ar because 0 <= x < 100. 3. using ostringstream to build output string and print it to stdout only one times when finished. marioquiroga2912: thank so much for your brilian solution. Good luck you guys.

but where is the sorting??

Your solution is brilliant. I used pair in C++ to establish counting sort table with O(n). Passed all test cases too

void countSort(vector<vector<string>> arr) {
    int n = arr.size();
    // create a "helper" array of vectors of pairs for counting sort with structure:
    // -----------------------
    // associated_int   vector of pairs
    //      0           <i, str_ith>, ... 
    //      1           ...
    //      ...
    //      99          ...
    // -----------------------
    // since the integer associated with string in range [0,100) so inititialize size 
    // of "helper" array to 100
    vector<vector<pair<int,string>>> countingList(100);
    for (int i = 0; i < n; i++) {
        pair<int, string> p(i, arr[i][1]);
        countingList[stoi(arr[i][0])].push_back(p);
    }

    for (int i=0; i<countingList.size(); i++) {
        if (countingList[i].size()) {
            for (auto const &e: countingList[i]) {
                if (e.first < n/2) {
                    cout << "- ";
                } else {
                    cout << e.second << " ";
                }
            }
        }
    }
}

Respect, man. Impressive.

respect man!!

thanks it worked

Nice Code

OKay My mind was blown!!!!!!!

I used multimaps..

void countSort(vector<vector<string>> arr) {
    
    multimap<int,string> m;

    for(int i = 0 ; i<arr.size()/2 ; i++)
        arr[i][1] = "-";

    for(auto a : arr)
        m.insert(make_pair(stoi(a[0]),a[1]));

    for(auto itr : m)
        cout<< itr.second + " ";

}

Python 3

Time complexity: n

A straight forward approach but i havent used counting sort but a dictionary to save the string as ecountered in the loop with key as the integer associated with it. This was the sorting part is done on the go. Aslo available on github

# Complete the countSort function below.
def countSort(arr,n):
    coll = dict()      # key is x[i] and value is list of all s[i] which have x[i]
    count = 0          # will be used to replace first half string with '-'
    for [i,j] in arr:
        if count < n/2:
            coll.setdefault(int(i),[]).append('-') # first half s[i] saved as '-'
            count += 1
        else:
            coll.setdefault(int(i),[]).append(j)   # next half s[i] as original string
    ans = []
    ele = list(sorted(list(coll.keys())))    # get all x[i] and sort
    for i in ele:
        temp = coll[i]
        ans.extend(temp)
    print(' '.join(ans))
    

if __name__ == '__main__':
    n = int(input().strip())

    arr = []

    for _ in range(n):
        arr.append(input().rstrip().split())

    countSort(arr,n)

man you're cool!

'''

'''arr=[] ans={} n=int(input()) for _ in range(n): x,s=input().strip().split() arr.append( [int(x),s] )

for i in range(n//2): arr[i][1]="-"

for k,v in arr: if k in ans: ans[k].append(v) else: ans[k]=[v]

sorted_items=sorted(ans.items(), key=lambda tup:tup[0])

for k , v in sorted_items: print(" ".join( i for i in v),end=" ")

Hey, you have a written an awesome code. Nice and simple approach. But instead if taking string array arr of size n, just take it of size 100. Bcuz the integer x in the constraints range from 0<=x<100 only. Even if n is 30000, ur array will be maximum of 100 elements. Just a thought. But a wonderful approach.

don't show answer in the discussion section , it would be decreased the glory of the question

Why do we need long int if it's given that n < 1000000?

Nice, i used sorting which added O(nlogn), it can be donw with counting sort easily

This logic is AWESOME! (BY marioquiroga2912)

Looks like I thought the same logic as you but in python : )

def countSort(arr):
    resarray=list("" for i in range(len(arr)))
    for i in range(len(arr)//2):
        resarray[int(arr[i][0])]+='- '
    for i in range(len(arr)//2,len(arr)):
        resarray[int(arr[i][0])]+=arr[i][1]+' '
    res=''
    for i in resarray:
        res+=i
    print(res)

This logic is exactly what they want from us