DSA Coding Contest - October '23 (Hacker Earth)

Question

Guys today i solved the below problem in hacker earth DSA coding contest, it passed on sample test cases but i'm not able check it on hidden test cases because the time gets over so i don't know whether my logic is right or wrong and my code is not a efficient one. So if anyone know the logic help me to solve the problem more efficiently.

Problem Statement :

Given an array monsters denoting strengths of N monsters, we start with an empty battlefield, at each minute i, the i-th monster joins the battlefield and kills all monsters whose strength is less than or equal to his strength.
Find the number of monsters alive in the battlefield at end of i-th minute for each 0≤ i <N.

Input Format :
T ==> no of test cases
N ==> first line of each test cases contain the no of monsters
M ===> second line of each test cases contain the N separated integers represents the strength of N monsters

Output Format :
For each test case, output N integers denoting the number of monsters alive after i-th minute for each 0 ≤ i< N.

Sample Input :
3
5
3 0 3 4 1
5
5 4 3 2 1
7
1 2 3 3 4 4 0

Sample Output :
1 2 1 1 2
1 2 3 4 5
1 1 1 1 1 1 2

My Solution :
https://code.sololearn.com/cfM7pHbrrdGJ/?ref=app
If you guys not understand the problem kindly use the below link to get more explanation about the problem

https://www.hackerearth.com/challenges/competitive/dsa-coding-contest-october-23/algorithm/killer-monsters-0b5cb283/

Answer 1

You are right, your algorithm seems to be very inefficient. Even though you are not explaining your code, you seem to use lists and you have multiple internal loops, so your algorithm has exponential time complexity. Lists are ok for small amount of data, but the hidden tests reveal its weakness, they are bad at iterating through large data sets.

I will not attempt to solve it if it's an ongoing competition. But I give you an idea. You could store the 'battle map' as a dictionary, where the keys are the strength level of each monster, and the value is how many monsters alive are that strong. In Python it is actually easy to create such an object with collections.Counter
Then you can examine in each round, which keys are lower than the monster just appearing, and reset those keys to zero. The remaining monsters are the sums of the dict values.

I am not actually sure if this approach will meet the task performance benchmark, but using a hashmap is always more efficient than iterating through a linked list.

Answer 2

Tibor Santa Thank you for your response bro, I'll try it with your idea

Answer 3

Kabilan K are you required to use Python? A compiled language could give the code a tremendous performance boost.

Answer 4

Brian No bro, we can use any language