Data Structure And Algorithm

Finding the Second-Largest Element in an Array

Finding the Second-Largest Element in an Array

Pankaj Kholiya's photo
Pankaj Kholiya
·

2 min read

Table of contents

Overview

The optimal approach to finding the second-largest element in an array involves iterating through the array and maintaining two variables (largest and secondLargest). This approach efficiently identifies the largest and second-largest elements in a single pass through the array.

Algorithm Description

  1. Initialize two variables (largest and secondLargest).

    • Initialize largest with the first element in the array.

    • Initialize secondLargest with a value that won't interfere with actual array elements.

int largest = arr[0];
int secondLargest = INT_MIN; // A very small integer to initialize

  1. Iterate through the array and update largest and secondLargest as needed.

    • If the current element is greater than largest, update both largest and secondLargest.

    • If the current element is greater than secondLargest and not equal to largest, update only secondLargest.

for (int i = 0; i < n; i++) {
    if (arr[i] > largest) {
        secondLargest = largest;
        largest = arr[i];
    } else if (arr[i] > secondLargest && arr[i] != largest) {
        secondLargest = arr[i];
    }
}

Time Complexity

The time complexity of finding the second-largest element using this optimal approach is O(n), where n is the number of elements in the array. The algorithm iterates through the array once.

Usage

To find the second-largest element in an array, use the provided optimal approach by initializing two variables (largest and secondLargest) and iterating through the array to update them.

Example

Consider the array: [10, 5, 25, 8, 15]

int largest = arr[0];
int secondLargest = INT_MIN;

for (int i = 0; i < 5; i++) {
    if (arr[i] > largest) {
        secondLargest = largest;
        largest = arr[i];
    } else if (arr[i] > secondLargest && arr[i] != largest) {
        secondLargest = arr[i];
    }
}

// At this point, 'secondLargest' contains the value 15

Note

This optimal approach efficiently finds the second-largest element in an array by iterating through the array once and updating two variables. Adjustments can be made based on specific project needs.

DSA