Second Largest

Slug: second-largest3735 Difficulty: Easy Id: 703089 Topic Tags: Arrays, Searching, Data Structures, Algorithms Company Tags: SAP Labs, Rockstand

Summary

Find the second largest element in an unsorted array. This problem involves basic searching and data structures concepts.

Detailed Explanation

The algorithm for this problem is quite straightforward. We can solve it by first finding the maximum element in the array (which could be one of the two elements we're interested in). Then, we just need to find the next largest element. If there are multiple equal largest elements, we can simply return any of them as the "first" largest and then proceed with finding the second largest.

Here's a step-by-step breakdown:

Initialize variables max and second_max to negative infinity.
Iterate through the array from left to right:
- If the current element is greater than max, update both max and second_max.
- If the current element is equal to max, update second_max.
Return second_max.

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

Here's a simple ASCII art diagram illustrating this:

[5, 2, 8, 12, 3]
    ^         ^
    |         |
 max=12  second_max=8

Optimized Solutions

Java

public class Solution { public int findSecondLargest(int[] arr) { if (arr.length < 2) { return -1; // or throw an exception } int max = Integer.MIN_VALUE; int secondMax = Integer.MIN_VALUE; for (int num : arr) { if (num > max) { secondMax = max; max = num; } else if (num == max) { secondMax = Math.max(secondMax, num); } } return secondMax; } }