Problem with finding the second largest number with pointers

Question

I made a method that tries to find the second largest number in an unsorted list of integers with pointers. When I pass any list of integers that has the second largest number placed side by side before the largest number, I dont get the expected results. For example, when I pass [2, 6, 6, 2, 11], I get as output:

Largest: 11
Second Largest: 2

The 6 is never assigned to the second_max because of this line:

elif j > second_max and first_max != j:

If I remove the second condition, the method can potentially assign duplicates to first_max and second_max and not output the actual second largest number.

first_max=float('-inf')
second_max=float('-inf')

for i,j in enumerate(nums):
    if j > first_max:
        first_max=j
    elif j > second_max and first_max != j:
        second_max=j 

if first_max == float('-inf'):
    first_max,second_max=None,None

elif second_max == float('-inf'):
    second_max=None

print("Largest: {}".format(first_max))
print("Second Largest: {}".format(second_max))

Would appreciate any help on this.

EDIT: I know there's a similar post to this but it does not answer my question of dealing with duplicates. I want the method to evaluate duplicates as one number only.

The output for this [5,5,4,2] and [2, 6, 6, 2, 11] as inputs should be respectively:

Largest: 5 Second Largest: 4

Largest: 11 Second Largest: 6

What do you mean by "pointers"? python does not have pointers (in the sense of C/C++ pointers) — Valentino, Jul 13 '19 at 15:43
What happens to the old value of `first_max` when you find a new one? — Thierry Lathuille, Jul 13 '19 at 15:46
sorted() is O(nlogn) time complexity, while this approach has O(n) time complexity. — vb_rises, Jul 13 '19 at 15:49
@AndrewAllen The question is about implementing a method to find them, and `sorted(myList)[-2]` could output duplicates, which the OP doesn't want. — Thierry Lathuille, Jul 13 '19 at 15:49
Possible duplicate of [Get the second largest number in a list in linear time](https://stackoverflow.com/questions/16225677/get-the-second-largest-number-in-a-list-in-linear-time) — Tomerikoo, Jul 13 '19 at 15:54
@Vishal OP doesn't mention whether complexity is a concern. I think it's right to point (no pun intended) out that there is a much simpler solution. — Andrew Allen, Jul 13 '19 at 15:57
if the kth order statistic is required in O(n) implement the selection algorithm here https://en.wikipedia.org/wiki/Selection_algorithm — Andrew Allen, Jul 13 '19 at 16:02
@AndrewAllen I know there are much more simpler approaches to this but I just want to know how to fix my problem by using this method. — pizza man, Jul 13 '19 at 16:11

score 0 · Answer 1 · answered Jul 13 '19 at 15:47

0

When you find a new first_max, the old first_max should become second_max, as hinted at by @Thierry.

answered Jul 13 '19 at 15:47

John Gordon

29,573
7
33
58

Deepstop · Answer 2 · 2019-07-13T16:48:11.653

0

As stated in the previous answer. I also removed the enumerate function as it didn't add anything useful.

nums = [1.0, 3.6, 2.2, 7.3, 5.1, 9.6, 1.1]
first_max=float('-inf')
second_max=float('-inf')

for j in nums:
    if j > first_max:
        second_max = first_max
        first_max=j
    elif second_max < j and j < first_max:
        second_max = j

if first_max == float('-inf'):
    first_max,second_max=None,None

elif second_max == float('-inf'):
    second_max=None

print("Largest: {}".format(first_max))
print("Second Largest: {}".format(second_max))

edited Jul 13 '19 at 16:48

answered Jul 13 '19 at 15:51

Deepstop

3,627
2
8
21

Hey, I just passed [5,5,4,2] into the function and as output, I get Largest: 5 Second Largest: None – pizza man Jul 13 '19 at 16:26
You are right. Fixing it. Makes it more complicated though, but hopefully correct this time. Your original produced incorrect results with my example so perhaps the complexity is required for this method. – Deepstop Jul 13 '19 at 16:44
Thanks for taking the time to help me. – pizza man Jul 13 '19 at 16:48

Problem with finding the second largest number with pointers

2 Answers2