Problem

Link to the original HackerRank problem

Given the names and grades for each student in a class of N students, store them in a nested list and print the name(s) of any student(s) having the second lowest grade.

Note: If there are mutliple students with the second lowest grade, order their names aphabetically and print each name on a new line.

Example

records = [["chi", 20.0], ["beta", 50.0], ["alpha", 50.0]]

The ordered list of scores is [20.0, 50.0], so the second lowest score is 50.0.

There are tow students with that score: ["beta", "alpha"].

Ordered alphabetically, the names are printed as:

alpha
beta

Input Format

The first line contains an integer, N, the number of students.

The 2N subsequent lines describe each student over 2 lines.

  • The first line contains a student’s name.
  • -100 <= A[i] <= 100

Constraints

  • 2 <= N <= 5
  • There will always be one ore more students having the second lowest grade.

Output Format

Print the name(s) of any student(s) having the second lowest grade in.

If there are multiple students, order their names alphabetically and print each one on a new line.

Sample Output 0

55
Harry
37.21
Berry
37.21
Tina
37.2
Akriti
41
Harsh
39

Sample Output 0

Berry

Explanation 0

There are 5 students in this class whose names and grades are assembled to build the following list:

python students = [['Harry', 37.21], ['Berry', 37.21], ['Tina', 37.2], ['Akriti', 41], ['Harsh', 39]]

The lowest grade of 37.2 belongs to Tina.

The second lowest grade of 37.21 belongs to both Harry and Berry, so we order their names alphabetically and print each name of a new line.

Code

Starter

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

Solutions

Naive and Terse

Implementation

A first naive, yet simple and terse solution is to simply:

  • First, store the names of the student by their grades in a dictionary
  • Then, sort the keys (i.e., grades) of that dictionary
  • Which allows to get the second-lowest grade key via index
  • Use that key to get the associated names in the dictionary
  • Print the names in alphabetical order

To make the implementation even terser, I am using the defaultdict below which initializes a default value using the passed factory function, here, list (empty list) when a new key that hasn’t been already added is being looked up to then append the relevant name (value) relative to its grade.

from collections import defaultdict

if __name__ == '__main__':
    n = int(input())
    students_grade_to_names = defaultdict(list)
    for _ in range(n):
        name = input()
        grade = float(input())
        students_grade_to_names[grade].append(name)
    second_lowest_grade = sorted(students_grade_to_names.keys())[1]
    snd_lowest_grade_names = students_grade_to_names[second_lowest_grade]
    print(*sorted(snd_lowest_grade_names), sep='\n')

Complexity

Time
  • Worst Case: O(n log n)
    • Occurs when all grades are unique (k = n).
    • Sorting the keys takes O(n log n).
  • Best Case: O(n)
    • Only two unique grades exist (k = 2).
    • Sorting becomes O(1).
  • Average Case: O(n + k log k)
    • Depends on the number of unique grades (k).
    • Building the dictionary is O(n), and sorting is O(k log k).
Space
  • Worst | Average | Best Case: O(n)
    • Stores all student names and grades in a dictionary.

Verbose

Implementation

if __name__ == '__main__':
    n = int(input())
    fst_lowest_grade = float('inf')
    snd_lowest_grade = float('inf')
    fst_lowest_grade_names = []
    snd_lowest_grade_names = []
    for _ in range(n):
        name = input()
        grade = float(input())
        if grade < fst_lowest_grade:
            snd_lowest_grade = fst_lowest_grade
            snd_lowest_grade_names = fst_lowest_grade_names
            fst_lowest_grade = grade
            fst_lowest_grade_names = [name]
        elif grade == fst_lowest_grade:
            fst_lowest_grade_names.append(name)
        elif grade < snd_lowest_grade:
            snd_lowest_grade = grade
            snd_lowest_grade_names = [name]
        elif grade == snd_lowest_grade:
            snd_lowest_grade_names.append(name)
    print(*sorted(snd_lowest_grade_names), sep='\n')

Complexity

Time
  • Worst | Average | Best Case: O(n)
    • Each student is processed in constant time (O(1)) per iteration.
    • The loop runs n times, leading to O(n) total time.
Space
  • Worst Case: O(n)
    • Occurs when all students except one share the second-lowest grade (e.g., snd_lowest_grade_names stores nearly all names).
  • Best Case: O(1)
    • Only 1 student has the second-lowest grade.
    • However, in practice, space depends on the number of students with the first/second-lowest grades (O(m), where m is the count of such students).

Key Takeways