Discussion on Find the Runner-Up Score! Challenge

gtorrecilla 4 years ago+ 1 comment

The problem with this implementarion is the complexity. You are doing it in O(n²), while you can do this in O(n). Even sorting the list have a better complexity O(n*log(n)). An example of a patological case is the list [5, 5, 5, 5, 5 ,6] or something like that.

bicole 4 years ago+ 2 comments

gtorrecilla. What do you think of this? Its not the best by line count, but I believe it finds the 2nd largest within O(n).

max = max2 = -100 - int(raw_input())
nums = map(int,raw_input().split(' '))
for i in range(len(nums)):
    if nums[i] > max2:
        if nums[i] > max:
            max,max2 = nums[i],max
        elif nums[i] < max:
            max2 = nums[i]
print(max2)

omnius42 4 years ago+ 0 comments

You're doing a bit more work than you need to. Instead of iterating over a range, just iterate over the number list.

raw_input()
max = max2 = -101
for n in map(int,raw_input().split()):
    if n > max2:
        if n > max:
            max,max2 = n,max
        elif n < max:
            max2 = n
print(max2)

evandam92 3 years ago+ 1 comment

I think this is the best approach too to stay within O(n). My solution was something similar:

n = int(input())
a = [int(x) for x in input().split()]
largest = secondlargest = -100
for x in a:
    if x > largest:
        tmp = largest
        largest = x
        secondlargest = tmp
    elif x > secondlargest and x != largest:
        secondlargest = x
print(secondlargest)

somewhatabstract 2 years ago+ 1 comment

You don't need that tmp var, just reorder your first condition:

n = int(input())
a = [int(x) for x in input().split()]
largest = secondlargest = -100
for x in a:
    if x > largest:
        secondlargest = largest
        largest = x
    elif x > secondlargest and x != largest:
        secondlargest = x
print(secondlargest)

youngshawzju 2 years ago+ 0 comments

works!but a little improvement is needed