Print largest, second largest, smallest, and second smallest values in a list in O(n) (linear time)

Question

l = [5, 4, 3, 2, 1, 100, 69]
largest = l[0]
smallest = l[0]
seclargest = 0
secsmallest = 0
a = len(l)
b = a - 1
for i in range(a):
    if l[i] > largest:
        seclargest=largest
        if b == i:
            print(seclargest)
        largest = l[i]
    if l[i] < smallest:
        if b>i:
            secsmallest = smallest
        smallest = l[i]

print(largest)
print(seclargest)
print(smallest)
print(secsmallest)

Help, please. This code only prints the smallest and second smallest correctly but not the largest and second largest values.

here: https://stackoverflow.com/questions/4215472/python-take-max-n-elements-from-some-list — Jean-François Fabre, Jan 10 '18 at 19:06
Is it really necessary to use the above code? You can simply do `l.sort()` and then take the `l[0], l[1], l[-1], l[-2]`. — Vasilis G., Jan 10 '18 at 19:06
@Jean-FrançoisFabre I think OP is asking for this to be done in `O(n)` (probably a HW assignment) so technically this isn't a dupe. — pault, Jan 10 '18 at 19:07
@VasilisG. you don't even need the len(l) calls: l[-1] and l[-2] are also good. — Gábor Fekete, Jan 10 '18 at 19:07
To everyone recommending sorting: Sorting is O(NLogN). If you want just the first 2 elements, calling sorted is a wasteful operation. OP's O(N) solution is better. OTOH, the `heapq` method is good, but constructing the heap takes linear time, not to mention N deletions, each of which is O(Log N). — cs95, Jan 10 '18 at 19:15

pault · Answer 1 · 2018-01-10T19:21:59.500

If you want to do it in linear time (one for loop), you can modify your code as follows:

l = [5, 4, 3, 2, 1, 100, 69]
largest = -1e10  # initialize to large negative number
smallest = 1e10  # initialize to large positive number
seclargest = -1e9 
secsmallest = 1e9
for x in l:
    if x > largest:
        seclargest=largest
        largest = x
    elif x > seclargest:
        seclargest = x
    elif x < smallest:
        secsmallest = smallest
        smallest = x
    elif x < secsmallest:
        secsmallest = x

print(largest)
print(seclargest)
print(smallest)
print(secsmallest)

Which outputs:

You were pretty close. You just needed to add one condition for the case where the number was smaller than the largest, but larger than the second largest and one similar condition for the second smallest.

Also, you can iterate through the list simply using for x in l, there's no need to iterate over the indices.

Print largest, second largest, smallest, and second smallest values in a list in O(n) (linear time)

1 Answers1