2

I am trying to find the second largest element in an array. My code is working for most inputs but for some inputs, it is failing. Also, if I input [6, 6, 6, 5], the program should output 5 as the second largest and not 6.

For [6,6,6,6,6,6,6,6,6,5], it is printing 6 instead of 5. For repeating elements it is giving wrong results.

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


if __name__ == '__main__':
    n = int(input("Enter the total numbers: "))
    arr = list(map(int, input("Enter the numbers: ").split()))
    if arr[0] >= arr[1]:
        first_max = arr[0]
        second_max = arr[1]
    else:
        first_max = arr[1]
        second_max = arr[0]
    for i in range(2, n):
        if arr[i] > first_max:
            second_max = first_max
            first_max = arr[i]
        elif arr[i] > second_max and arr[i] != first_max:
            second_max = arr[i]

    print(second_max)

Please, someone, explain the logic behind it.

dsaharia
  • 67
  • 2
  • 13
  • 2
    Why not `sorted(set(arr))[-2]`? – Berriel Apr 14 '19 at 15:07
  • Possible duplicate of [How to find second largest number in a list?](https://stackoverflow.com/questions/19697504/how-to-find-second-largest-number-in-a-list) – Madusudhanan Apr 14 '19 at 15:09
  • That would work. But I want to know the general logic, not the language-specific solutions. – dsaharia Apr 14 '19 at 15:09
  • I am mainly asking for duplicate elements. – dsaharia Apr 14 '19 at 15:10
  • One up for including a problem statement in the source code - next time, use a [docstring](https://www.python.org/dev/peps/pep-0257/#what-is-a-docstring). If you defined a function for the business logic, you would add one there, too. – greybeard Jan 03 '22 at 07:22

7 Answers7

2

The problem is with the initialization of the first and second max you wrote here 

    if arr[0] >= arr[1]:
    first_max = arr[0]
    second_max = arr[1]
else:
    first_max = arr[1]
    second_max = arr[0]

In the case of [6,6,6,6,6,6,6,6,6,5], you had both first_max and second_max equal to 6, and those can't be changed when given a 5, since the second max is still larger than 5.

A solution would be to edit this portion of the code

BEFORE

elif arr[i] > second_max and arr[i] != first_max: second_max = arr[i]

AFTER

elif first_max == second_max or (arr[i] > second_max and arr[i] != first_max: second_max = arr[i])

Ahmed Ragab
  • 836
  • 5
  • 10
2

Your problem start when the first 2 element are 6. So both first and second max are 6 so it ignore the 5.

Best practice will be to throw all duplicate value - you can use python build-in function to do so (set). Then try run you code.

Second approach will be to init first max as first element and second as -1 so the first time you encounter element bigger then one of the max it will be set. If the loop is over and the second max is still -1 it means all the element are the same

dWinder
  • 11,597
  • 3
  • 24
  • 39
1
def second_biggest(l):
  """ Get second biggest entry in a list

    1. make a `set` out of `list`: guarantees that every entry only appears once
    2. sort the `set` by value
    3. get the second biggest entry
  """
  return sorted(set(l))[-2]
Ente
  • 2,301
  • 1
  • 16
  • 34
  • That would work. But I want to know the general logic, not the language-specific solutions. – dsaharia Apr 14 '19 at 15:11
  • I don't understand what you mean by the 'general logic'. Making all entries unique, sorting and getting the second biggest from the sorted list is kind of the 'general logic' which you would need to apply in all programming languages. – Ente Apr 14 '19 at 15:15
  • How can I apply this in C? I am a beginner. – dsaharia Apr 14 '19 at 15:19
  • 1
    Well explaining all this is quite a mouthful. But maybe if you read up on [how to implement a set datastructure](https://stackoverflow.com/questions/2630738/c-how-to-implement-set-data-structure) and [sorting algorithms](https://www.geeksforgeeks.org/sorting-algorithms/) you will get an idea. Hope this helps. Keep up the good work, learning about programming is very valuable and every minute invested pays off eventually. – Ente Apr 14 '19 at 18:48
1

Here's a different approach: convert the data to a set (which consequently removes duplicate elements), remove the maximum, and print the then-maximum. Eg:

data = [6,6,6,6,6,6,6,6,6,5]
sb = set(data) # remove duplicate elements
sb.remove(max(sb)) # remove the max element
print(max(sb)) # print the new max

Output:

5

If you just wanted to remove duplicate elements, convert the set back to a list:

data = [6,6,6,6,6,6,6,6,6,5]
data = list(set(data))

Output:

>>> data
[5, 6]
PrinceOfCreation
  • 389
  • 1
  • 12
0

You can try using sorted method to sort and then find the second largest element by converting to set for removing duplicate elements and then select last second element.

arr = [2, 4, 5, 5, 455, 34]
unique_arr = sorted(set(arr))

print(unique_arr[-2])

Edit:
Without using python set or sorted function:

arr = [1, 4, 5, 723, 64, 76, 34]

max_1 = max(arr)
max_2 = min(arr)

for item in arr:
    if item > max_2 and item != max_1:
        max_2 = item

print("Second largest item: ", max_2)
AVX-42
  • 755
  • 2
  • 13
  • 21
0

Try:

list1 = list(arr)
    
    
new_set = set(list1)
    
    
new_list = list(new_set)
new_list.sort()
    
    
new_list.pop(-1)
    
print(new_list[-1])
U13-Forward
  • 69,221
  • 14
  • 89
  • 114
Shanmuga Natraj
  • 1
0

Since, there might be multiple occurrences of the largest value, we find the largest value in the list and create a list without the largest value. Then we find the largest value from the new list, which gives us the second largest value.

   n = int(input("Enter the total numbers: "))
   arr = list(map(int, input("Enter the numbers: ").split()))

   max_val = max(arr)

   lst = [x for x in arr if x!=max_val]
   second_max = max(lst) 
   
   print(second_max)
faiaz000
  • 39
  • 4