Second smallest element in a list

Question

I have to find the names of student(s) with second smallest grade. My code is working fine some test cases but this one in particular is troubling me:

4 Rachel -50 Mawer -50 Sheen -50 Shaheen 51

Output returned is

Mawer Rachel Sheen

Shaheen has the 2nd smallest grade and should be the output. I am not sure where am I going wrong. Also, I am having trouble with grades as float inputs:

4 Shadab 8 Varun 8.9 Sarvesh 9.5 Harsh 10

Output thrown is Sarvesh when it should be Varun.

import heapq
# range(int(input())):
n = int(input())
builtlist = []
temp= []
names = []
for i in range(0, n):
name = input()
score = float(input())
builtlist.append([name, score])

temp = sorted(builtlist, key = lambda x: x[1])
#minvalue = min(temp, key= lambda x: x[1])

for j in range(len(temp)):
secondsmall = heapq.nsmallest(2, temp)[-1]
if (temp[j][1]==secondsmall[1]):
    names.append(temp[j][0])
list = sorted(names)
print(*list, sep = "\n")

I guess there's some trouble with heapq.nsmallest method I have used but I can't figure out what it is.

Also, a somewhat philosophical question; what is the second smallest when there are many with the same (lowest) score? You seem to consider the scores, rather than the people. That is fine, but it is worth to think about. — JohanL, May 17 '17 at 04:30
@e4c5 It's working fine with other inputs. These two are causing trouble. Indentation issue as in where? — rachitmishra25, May 17 '17 at 04:30
as in your code or as in the code you posted in your question — e4c5, May 17 '17 at 04:33
@JohanL In that case, since there are multiple people with the same scores, names of all those people are getting appended in the names list. Then, I would be getting the output with all those names sorted alphabetically. That's one of the requirements of the question. — rachitmishra25, May 17 '17 at 04:33

Pavan · Accepted Answer · 2017-05-17T06:12:41.267

1

You are going wrong here temp = sorted(builtlist, key = lambda x: x[1]) , heapq.nsmallest(2,temp) returns the n smallest elements in the temp, in your case it will be [50,50,50,51] so it'll return [50, 50] use temp = list(set(temp)) then your code will work.

you can use this code to get the same answer, in case you don't want to use heapq.

# range(int(input())):
n = int(input())
builtlist = []
temp= []
names = []
for i in range(0, n):
    name = input()
    score = float(input())
    builtlist.append([name, score])

temp = list(set([x[1] for x in builtlist]))
secondsmall = sorted(temp)[1]

for j in range(len(builtlist)):
    if (builtlist[j][1]==secondsmall):
        names.append(builtlist[j][0])
list_print = sorted(names)
print(*list_print, sep = "\n")

edited May 17 '17 at 06:12

answered May 17 '17 at 04:53

Pavan

108
1
12

Hey thanks it looks fine but is throwing the error at secondsmall = sorted(list(set([x[1] for x in builtlist])))[1] as "list object is not callable" – rachitmishra25 May 17 '17 at 05:32
I edited my answer. Actually that should work, I don't know why you got error. >>> a = [('asdas', 20), ('asdasd', 40), ('fsdgfds',20), ('dsada', 50)] >>> sorted(list(set([x[1] for x in a])))[1] 40 – Pavan May 17 '17 at 05:37
>>> a = [('asdas', 20), ('asdasd', 40), ('fsdgfds',20), ('dsada', 50)] >>> sorted(list(set([x[1] for x in a])))[1] >>>40 – Pavan May 17 '17 at 05:45
temp = list(set([x[1] for x in builtlist])) That's very strange. On this line here, it keeps throwing the error that list object is not callable. I thought list being a built in variable might have gotten overshadowed by the list variable declared at the end but something else is the reason I guess. – rachitmishra25 May 17 '17 at 06:04
yeah that might be the case here. before running a program python creates a `__dict__` which has all the variable and methods. Please avoid using the keywords as a variable name. Edited my code. I just added my part and used rest from your code, sorry for that. – Pavan May 17 '17 at 06:11
Issue sorted. Turns out the list built-in got overshadowed with list = sorted(names). I renamed it, deleted the builtin and then re-invoked it. Thanks a ton! – rachitmishra25 May 17 '17 at 06:12

Erich · Answer 2 · 2017-05-17T04:59:56.410

0

There's a lot of things going on here.

First off, stackoverflow does not exist to debug your code and this is a misuse of the website. Please in the future do not do this, and be aware of the

code tags.

Second, heapq.nsmallest() will return the number requested of smallest elements. If two elements are the least and share a value then they both will be returned. Therefore the code is operating as intended.

I would look into python dictionaries, and hashsets for this problem. There exists a more elegant solution.

edited May 17 '17 at 04:59

answered May 17 '17 at 04:44

Erich

1,902
1
17
23

Didn't intend to misue anything as such plus my bad. I am a newbie here and still getting a hang of how everything on here works out. – rachitmishra25 May 17 '17 at 06:36

score 0 · Answer 3 · answered May 17 '17 at 04:53

Didn't need to use heapq:

def second_smallest(builtlist):
    # sort on key.
    temp = sorted(builtlist, key = lambda x: x[1])
    second_smallest_group = []
    current_val = 0
    # iterate list comparing i with i + 1
    for i in range(len(temp) - 1):
        current_val = temp[i][1]
        # if in set of first smallest ignore.
        if current_val == temp[i+1][1] and len(second_smallest_group) == 0:
            continue
        # if in second set of smallest add.
        elif current_val == temp[i+1][1] and len(second_smallest_group) > 0: 
            second_smallest_group.append(temp[i+1][0])
        # if changing between sets add first member.
        elif len(second_smallest_group) == 0:
            second_smallest_group.append(temp[i+1][0])
        # if we move to another group break.
        else:
            break
    return second_smallest_group



builtlist = [["Rachel", -50], ["Mawer", -50], ["Sheen", -50],["Shaheen",51]]

print(second_smallest(builtlist))

builtlist = [["Shadab",8], ["Varun", 8.9], ["Sarvesh", 9.5], ["Harsh",10]]

print(second_smallest(builtlist))

pylang · Answer 4 · 2017-05-17T05:31:01.317

A more common counterpart to heapq in Python is a Counter.

import collections as ct

def second_smallest(lst):
    """Return the second smallest entry."""
    c = ct.Counter()
    for name, score in lst:
        c.update({name:score})
    return c.most_common()[-2]

Application:

builtlist = [["Rachel", -50], ["Mawer", -50], ["Sheen", -50],["Shaheen", 51]]
second_smallest(builtlist)
# ('Sheen', -50)

builtlist = [["Shadab", 8], ["Varun", 8.9], ["Sarvesh", 9.5], ["Harsh", 10]]
second_smallest(builtlist)
# ('Varun', 8.9)

Here are ways to get the least common (or smallest) value using the Counter.most_common() method.

Second smallest element in a list

4 Answers4