HackerRank's Nested Lists Problem

Ramin Melikov — Tue, 12 May 2020 18:18:08 +0000

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.

DEV Community: Ramin Melikov

HackerRank's Nested Lists Problem