Skip to main content

Find the largest and second largest element in an array

The problem at hand is to find the largest and second-largest elements in an array of integers. This task involves iterating through the array and identifying the two largest values present in it. This can be helpful in various scenarios, such as finding the top-scoring students in a class or the highest and second-highest sales figures in a dataset.

Problem Statement and Description

Given an array of integers, we need to determine the largest and second-largest values present in the array. For instance, consider the array [10, 3, 23, 86, 8, 9, 44, 5, 7]. The largest element in this array is 86, and the second-largest element is 44.

Examples


Example A
arr1[] = {10 , 3 , 23 , 86 , 8 , 9 , 44 , 5 , 7}
                        ⇧            ⇧
--------------------
First Largest   : 86
Second Largest  : 44

Example B
arr2[] = {10 , 3 , 11 , 16 , 8 , 16 , 5 , 9 , 7}
                        ⇧         ⇧
--------------------
First Largest   : 16
Second Largest  : 16

Example C
arr3[] = { 10 }
--------------------
None
(Because less than 2 element)

Idea to Solve the Problem

To find the largest and second-largest elements in the array, we can iterate through the array while keeping track of the two largest values encountered so far. We'll initialize two variables, first and second, to store these values. As we traverse the array, we'll compare each element with these variables and update them accordingly. By the end of the iteration, we'll have the largest and second-largest elements.

Pseudocode

twoLargest(arr, size):
    if size <= 1:
        return
    else:
        first = INT_MIN
        second = INT_MIN
        for i in range(0, size):
            if arr[i] > first:
                second = first
                first = arr[i]
            else if arr[i] > second:
                second = arr[i]
        print "First Largest: ", first
        print "Second Largest: ", second

Algorithm Explanation

  1. Check if the size of the array is less than or equal to 1. If so, there can't be a second-largest element, and we return.
  2. Initialize two variables, first and second, to INT_MIN. These will be used to store the largest and second-largest elements.
  3. Iterate through the array. For each element arr[i]:
    • Compare arr[i] with first. If it's greater than first, update second with the value of first and update first with the value of arr[i].
    • If arr[i] is not greater than first but is greater than second, update second with the value of arr[i].
  4. After the iteration, the first variable will contain the largest element, and the second variable will contain the second-largest element.
  5. Print the values of first and second.

Code Solution

Time Complexity Analysis

The algorithm iterates through the array once, performing constant-time comparisons and updates for each element. Therefore, the time complexity of the algorithm is O(n), where n is the size of the input array. This linear time complexity indicates that the algorithm's execution time increases linearly with the size of the input.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment