HackerRank's Nested Lists Problem

#python #efficiency #hackerrank #solution

HackerRank's Nested Lists problem can be solved in many ways. One of the solutions that you might find in the discussion area of the problem is the following:

marksheet = []
for _ in range(0,int(input())):
    marksheet.append([input(), float(input())])
second_highest = sorted(list(set([marks for name, marks in marksheet])))[1]
print('\n'.join([a for a,b in sorted(marksheet) if b == second_highest]))

However, there is a problem there. Do you see it? This solution performs 2 sorts and then it conducts a linear search.

We can do better than that. Here is a solution that sorts 1 time, ends the operation sooner, and performs a binary search.

from bisect import bisect, bisect_left
from heapq import heappush, heappop

n = 2
scores_names = []
scores_sorted = []
scores_names_sorted = []
ordinal_map = {}
seen = set()
enum = 1

if __name__ == '__main__':
    for _ in range(int(input())):
        name = input()
        score = float(input())
        heappush(scores_names, (score, name))

for i in range(len(scores_names)):
    score_name = heappop(scores_names)
    scores_sorted.append(score_name[0])
    scores_names_sorted.append(score_name)

    if score_name[0] not in seen:
        if enum > n:
            break
        seen.add(score_name[0])
        ordinal_map[enum] = score_name[0]
        enum += 1

low = bisect_left(scores_sorted, ordinal_map[n])
high = bisect(scores_sorted, ordinal_map[n])

for i in range(low, high):
    print(scores_names_sorted[i][1])

It's a little bit more code and it would be an overkill for simple things. However, for bigger problems, this would perform drastically better.

Feel free to suggest an improvement.

Top comments (1)

Marcio Guillardi da Silva • May 25 '21

My code... more Pynthonic...

if __name__ == '__main__':
    records = []
    for _ in range(int(input())):
        name = input()
        score = float(input())
        records.append([name, score])

    scores = sorted(set([score for name, score in records]))

    print(*sorted([name for name, score in records if scores[1] == score]), sep = "\n")

DEV Community

HackerRank's Nested Lists Problem

Top comments (1)

Read next

Chat with your PDF using Pinata,OpenAI and Streamlit

LuxDevHQ (Lux Academy and Data Science East Africa) Training Program in AI, Data Science, Analytics, and Data Engineering

💡Never forget again: Build a scheduled reminder app in <50 lines of Python using REST and Postgres

Python Decorators: Simplifying Code