Finding Second Largest Number in Array

In this article, we will learn how to find second largest number in an array. We will see various approaches to finding second largest number in an array with the time and space complexity of each approach. We will also see a dry run to solve the problem.

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)

FAQs Related To Find Second Largest Number in an Array

1) How to sort an array in reverse order in various languages?

Python: arr.sort(reverse = True)
Java: Arrays.sort(arr, Collections.reverseOrder())
C++: arr.sort(arr, arr+n, greater())

2) How to initialize heap data structure in different languages?

Python: heapq.heapify(heap)
Java: PriorityQueue pQueue = new PriorityQueue()
C++: priority_queue pq;

3) What is the best technique to find second largest number in array?
Out of the above-mentioned techniques last approach using two variables is the best technique to find second largest number in array because it always works in O(n) time complexity and the space complexity is also O
(1).