Finding Second Largest Number in Array

Last Updated on June 8, 2023 by Mayank Dham

Learn how to find the second-largest integer in an array in this article. The second-largest number in an array can be found in a variety of ways, each with a different time and space complexity. Additionally, a dry run to fix the problem will be shown.

What is the Second Largest Element in an Array?

Lets see examples to understand what is the second largest element in an array.

Example 1:

In the above example, the second largest element in an array is 86 ( first largest = 98 ).

Example:2

In the above example, the second largest element in an array is 75.

How to Find Second Largest Number in Array?

Lets see different approaches to finding the kth largest element in an array.

Approach 1: Sorting

Below are the steps to find second largest number in array using the sorting method,

• Sort the array into descending order
• The second largest element in an array is arr[1] (0-based indexing).
• If the array is sorted into ascending order then,
• The second largest element in an array is arr[n-2] where n is the size of an array (0-based indexing).

Lets understand this approach to find the kth largest element in an array with an example.

In the above example, after sorting the array into descending order, the second largest number in an array is 75 (arr[1]).

Now, lets see how to write a program to find second largest number in array.

# Python program to find second largest number in array

def secondSmallest(arr, N):

    # Sort the given array in descending order
    arr.sort(reverse=True)

    # return second largest number
    return arr[1]


# Driver code
if __name__ == '__main__':
    arr = [30, 15, 75, 7, 94, 45, 64, 22, 61]
    N = len(arr)

    print("The second smallest number in an array: ",
        secondSmallest(arr, N))

Output:

The second smallest number in an array:  75

Time Complexity: O(nlogn) where n is the size of an array, we are sorting the array which takes nlogn time.

Space Complexity: O(1) as we are not using any extra space.

Approach 2: Heap

In this approach, we will use max-heap to find second largest number in array. We know that the first element of the max-heap is always the largest one. So, we will remove the first elements from the max-heap and now the largest element present in the max-heap is our answer. Lets see a dry run of this approach to understand it better.

In the above image, we can see that we have inserted all the elements into the max-heap and all the elements are in sorted order.

Now, we will extract the first element from the max-heap.

Now, the second largest element is 75 here.

# python program to find second largest element in array using max-heap

from heapq import heappush,heappop

arr=[30, 15, 75, 7, 94, 45, 64, 22, 61]

# create heap
heap=[]
n=len(arr)

# insert all elements into heap
for i in range(n):
    # by default heap is mean heap so we will make element negative to perform max heap
    heappush(heap,-1*arr[i])

# remove first max elements from the heap
heappop(heap)
    
ans=-heappop(heap)

print("The second largest element in an array is:",ans)

Output:

The second largest element in an array is: 75

Time Complexity: O(n*log(n)) where n is the size of an array

Space Complexity: O(n)

Approach 3: QuickSelect Algorithm

In this approach, we will use the technique of the quicksort algorithm to find second largest number in array. Below are steps to find second largest number in array using the quickselect algorithm.

• First, choose any random position as a pivot position.
• Now, use the partition algorithm to split the array into two halves and find the correct position of the pivot.
• In the partition algorithm, all the elements are compared with the pivot, elements that are less than the pivot will be shifted to the left of the pivot, and elements that are greater than the pivot will be shifted to the right of the pivot.
• After performing the partition algorithm, all the elements left to the pivot are smaller than it, and all the elements right to the pivot are greater than it.
• Compare the index of pivot to 1.
• If the index matches then return the answer otherwise find other partition recursively.

# python program to find second largest element in array using quickselect

def secondLargest(arr):
    left=0
    right=len(arr)-1
    ans=0
    
    while(True):
        index=partition(arr,left,right)
        if index==1:
            ans=arr[index]
            break
        if index<1:
            left=index+1
        else:
            right=index-1
    return ans
    
    
def partition(arr, left, right):
    
    pivot=arr[left]
    l=left+1
    r=right
    
    while(l<=r):
        if arr[l]<pivot and arr[r]>pivot:
            arr[l],arr[r]=arr[r],arr[l]
            l+=1
            r-=1
        if arr[l]>=pivot:
            l+=1
        if arr[r]<=pivot:
            r-=1
    arr[left],arr[r]=arr[r],arr[left]
    return r

arr = [30, 15, 75, 7, 94, 45, 64, 22, 61]
N = len(arr)

print("The second largest element in an array is:",
        secondLargest(arr))

Output:

The second largest element in an array is: 75

Time Complexity: Average time complexity O(n) Worst time complexity O(n^2)

Space Complexity: O(1)

Approach 4: Efficient Approach using Two Variables

In this approach, we will use two variables to keep track of the largest and second-largest elements so far. Let’s see an algorithm of this approach.

Algorithm:

• Initialize the largest and second_largest as min
• Start traversing the array,
  • If the current element in the array say arr[i] is greater
    than largest. Then update largest and second_largest as,
    second_largest = largest
    largest = arr[i]
  • If the current element is in between largest and second_largest,
    then update second_largest to store the value of the current
    variable as
    second_largest = arr[i]
• Return the value stored of second_largest.

Lets see a dry run of this algorithm to understand it better.

arr= [30, 15, 75, 7, 94, 45, 64, 22, 61]
Initial largest = -2147483648, second_largest = -2147483648

    i = 0:
        arr[0] (30) >largest
        largest = 30 (value of arr[0])
        second_largest = -2147483648 (value of largest)

    i = 1:
        largest > arr[1] (15) > second_largest
        largest = 30
        second_largest = 15 (value of arr[2])

    i = 2:
        arr[1] (75) >largest
        largest = 75 (value of arr[2])
        second_largest = 30 (value of largest)

    i = 3:
        arr[3] (7) largest
        largest = 94 (value of arr[4])
        second_largest = 75 (value of largest)

    i = 5:
        arr[5] (45) < second_largest
        largest = 94
        second_largest = 75

    i = 6:
        arr[6] (64) < second_largest
        largest = 94
        second_largest = 75

    i = 7:
        arr[7] (22) < second_largest
        largest = 94
        second_largest = 75

    i = 8:
        arr[8] (61) < second_largest
        largest = 94
        second_largest = 75

Now, we can see that the second largest number is 75.

# python program to find second largest number in array

def secondLargest(arr, n):
 
    if (n < 2):
     
        print(" Invalid Input ")
        return
     
 
    largest = second_largest = -2147483648
    for i in range(n):
        if (arr[i] > largest):
         
            second_largest = largest
            largest = arr[i]
         
        elif (arr[i] > second_largest and arr[i] != largest):
            second_largest = arr[i]
     
    if (second_largest == -2147483648):
        print("There is no second largest element")
    else:
        print("The second largest element is", second_largest)
 
 
arr = [30, 15, 75, 7, 94, 45, 64, 22, 61]
n = len(arr)
 
secondLargest(arr, n)

Output:

The second largest element is 75

Time Complexity: O(n)
Space Complexity: O(1)

Conclusion
Finding the second largest number in an array is a common problem in programming, and there are multiple approaches to solve it. One straightforward approach is to iterate through the array and keep track of the largest and second largest numbers. By comparing each element with these two numbers, we can update them accordingly. Another approach involves sorting the array in descending order and then accessing the element at the second index. Both approaches have their advantages depending on the requirements and constraints of the problem.

Frequently Asked Questions (FAQs):

Q1: What is the significance of finding the second largest number in an array?
A1: Finding the second largest number in an array can be useful in various scenarios. It helps in tasks like finding the runner-up in a competition, identifying the second highest score in a game, or analyzing data where the second largest value is relevant.

Q2: How can I find the second largest number in an array using iteration?
A2: To find the second largest number using iteration, you can initialize two variables: largest and secondLargest to the smallest possible value. Then, iterate through the array and update these variables based on the comparison with each element. At the end of the iteration, the secondLargest variable will hold the second largest number.

Q3: What is the time complexity of finding the second largest number using iteration?
A3: The time complexity of finding the second largest number using iteration is O(n), where n is the length of the array. This is because we need to iterate through each element of the array once to compare and update the largest and second largest numbers.

Q4: Can I find the second largest number by sorting the array?
A4: Yes, sorting the array in descending order and accessing the element at the second index will give you the second largest number. However, sorting the entire array can be less efficient if you only need the second largest number and not a sorted array.

Q5: What is the time complexity of finding the second largest number by sorting the array?
A5: The time complexity of sorting an array using efficient sorting algorithms like quicksort or mergesort is O(n log n), where n is the length of the array. Therefore, the time complexity of finding the second largest number by sorting the array is the same—O(n log n). However, this approach may be less efficient if you only need the second largest number and not the entire sorted array.

Q6: How do I handle edge cases when finding the second largest number?
A6: When finding the second largest number, consider edge cases like an array with fewer than two elements or an array where all elements are the same. In these cases, you may need to define appropriate behavior, such as returning a special value or indicating that there is no second largest number.