Explorer
Data Structures & Algorithms

Find the second largest element in an array without sorting. Keep track of the largest and second largest while iterating.

Problem Statement

Given an array of integers, return the second largest element. If it does not exist, return -1.

Examples

Input: arr = [1, 2, 4, 7, 7, 5]

Output: 5

Explanation: The largest is 7, the second largest is 5.

Constraints

Standard constraints

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: Can you solve this in a single pass without sorting? Sorting takes O(N log N). šŸ’” Hint 2: Keep two variables: largest and secondLargest, both initialized to -Infinity. šŸ’” Hint 3: When num > largest, update secondLargest = largest, then largest = num. If num is strictly between largest and secondLargest, update secondLargest.

Editorial & Approach

Problem Overview & Intuition

To find the second largest distinct element in one pass, maintain two variables: the largest and the second largest. For each element in the array, compare it with largest and secondLargest while ignoring duplicates.

Step-by-Step Approach

  1. Initialize max = -Infinity and secondMax = -Infinity.
  2. Iterate through every num in arr.
  3. If num > max, shift: secondMax = max, then max = num.
  4. Else if num > secondMax && num !== max, update secondMax = num.
  5. After loop, return secondMax === -Infinity ? -1 : secondMax.

Optimal Implementation (JavaScript)

function secondLargest(arr) {
  let max = -Infinity, secondMax = -Infinity;
  for (let num of arr) {
    if (num > max) {
      secondMax = max;
      max = num;
    } else if (num > secondMax && num !== max) {
      secondMax = num;
    }
  }
  return secondMax === -Infinity ? -1 : secondMax;
}

Complexity Analysis

Time Complexity O(N) ā€” single linear pass through the array.
Space Complexity O(1) ā€” constant auxiliary space.

Edge Cases & Corner Traps Handled

  • All elements equal: return -1 since no distinct second largest exists.
  • Length < 2: returns -1.
  • Negative values: handled properly by starting with -Infinity.

Second Largest Element in an Array

Easy
Given an array of integers, return the second largest element. If it does not exist, return -1.
Example Scenarios
1Example 1
Input: arr = [1, 2, 4, 7, 7, 5]
Output: 5
Explanation:

The largest is 7, the second largest is 5.

Constraints
ā€¢Standard constraints
Editor
Loading Editor...
arr =
[1, 2, 4, 7, 7, 5]
Output:Click "Run" above to execute and verify your code here.
5