Problem

Link to the original HackerRank problem

Given the participants’ score sheet for your University Sports Day, you are required to find the runner-up score. You are given n scores. Store them in a list and find the score of the runner-up.

Input Format

The first line contains n. The second line contains an array A[] of n integers each separated by a space.

Constraints

  • 2 <= n <= 10
  • -100 <= A[i] <= 100

Output Format

Print the runner-up score.

Sample Input 0

5
2 3 6 6 5

Sample Output 0

5

Explanation 0

Given list is [2, 3, 6, 6, 5]. The maximum score is 6, second maximum is 5. Hence, we print as the runner-up score.

Code

Starter

if __name__ == '__main__':
    n = int(input())
    arr = map(int, input().split())

Solution

Expensive one-liner

Implementation

One easy way is to sort the distinct numbers and get the second to last:

from collections import OrderedDict

if __name__ == '__main__':
    n = int(input())
    arr = map(int, input().split())
    print(sorted(set(arr))[-2])

Complexity

Time
  • Worst Case: O(n log n)
    • Occurs when all elements are unique.
    • Converting to a set takes O(n), and sorting the set of size n takes O(n log n).
  • Average Case: O(n + m log m)
    • m = number of unique elements.
    • Creating the set is O(n), and sorting the unique elements dominates with O(m log m).
  • Best Case: O(n)
    • All elements are identical.
    • The set reduces to 1 element, and sorting is O(1), but creating the set still requires O(n).
Space
  • Worst Case: O(n)
    • All elements are unique.
    • Storing the set and sorted list requires O(n) space.
  • Average Case: O(m)
    • Depends on the number of unique elements m.
  • Best Case: O(1)
    • All elements are identical (only 1 unique element stored).

Cheaper Single-pass Naive loop

Implementation

We can achieve the same given the constraints by pre-assigning the 1st and 2nd place scores to a value that is way below that can be expected in the input data (i.e., -100 <= A[i] <= 100), aka -inf.

We then iterate the scores and check for each if it is above the value of the 1st place, and if it is, we then assign:

  • the 1st place score to the 2nd place score.
  • the current iterated input score to the 1st place score.

If it is not and that the current iterated score is between the 1st and 2nd place scores, we then assign:

  • the current iterated input score to the 2nd place score.
if __name__ == '__main__':
    n = int(input())
    arr = map(int, input().split())
    fst = snd = int('-inf')
    for i in arr:
        if i > fst:
            snd = fst
            fst = i
        elif fst > i > snd:
            snd = i
    print(snd)

Complexity

Time
  • Worst | Best | Average Case: O(n)
    • Single pass through the input array.
    • Each iteration performs constant-time comparisons and updates.
Space
  • Worst | Best | Average Case: O(1)
    • Uses only a fixed number variables (fst, snd, i).
    • Does not store the input array.

Key Takeways