Second Largest Element

93.7k
0

Problem Statement

Given an integer array nums, return the second largest distinct element in the array.

The answer must be strictly smaller than the largest element. Return -1 if fewer than two distinct values exist.

Example 1

Input: nums = [12, 35, 1, 10, 34, 1]

Output: 34

Explanation: The largest element is 35, and the second-largest distinct element is 34.

Example 2

Input: nums = [10, 10, 10]

Output: -1

Explanation: All elements are equal, so no second-largest distinct element exists.

Example 3

Input: nums = [5]

Output: -1

Explanation: A single element cannot have a second-largest element.

Brute Force Approach

Sorting arranges the values in non-decreasing order, placing the largest value at the final index.

The positions before the largest may contain duplicate copies of the same value. Moving backward and skipping those duplicates reveals the first value strictly smaller than the largest, which is the second-largest distinct element.

Algorithm

  • Store the array size in n. If n < 2, return -1 because two distinct values cannot exist.

  • Create sortedNums as a copy of nums so that sorting does not change the original array.

  • Sort sortedNums in non-decreasing order and take its last element as largest, since sorting places the maximum value at the end.

  • Start from index n - 2 and move backward while the current value equals largest, as duplicate copies of the maximum cannot be considered distinct.

  • Return the first value that is smaller than largest, since it is the greatest distinct value below the maximum.

  • If no such value is found, return -1 because the array contains fewer than two distinct values.

Dry Run

Second Largest Element Brute Force Dry Run.png

Second Largest Element Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int secondLargest(vector<int>& nums) {
int n = nums.size();
/*
* At least two values are needed
* to have a distinct second largest.
*/
if (n < 2) {
return -1;
}
vector<int> sortedNums = nums;
sort(sortedNums.begin(), sortedNums.end());
int largest = sortedNums[n - 1];
/*
* Move backward until a value smaller
* than the maximum is found.
*/
for (int index = n - 2; index >= 0; index--) {
/*
* The first smaller value is the
* second-largest distinct element.
*/
if (sortedNums[index] < largest) {
return sortedNums[index];
}
}
// No second-largest distinct value exists.
return -1;
}
};
int main() {
vector<int> nums = {8, 8, 5, 3, 5};
Solution solution;
cout << solution.secondLargest(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N represents the number of elements. Sorting requires O(N log N) time, while the backward scan takes at most O(N) time.

Space Complexity: O(N), because a copied array of size N preserves the original array. The sorting method may also use language-specific internal memory.

Better Approach

Sorting the entire array is unnecessary because only the largest and second-largest distinct values matter.

The largest value can be identified in the first traversal. A second traversal can then ignore every occurrence of the largest value and retain the greatest remaining value.

Algorithm

  • Store the array size in n. If n < 2, return -1 because a second distinct value cannot exist.

  • Initialize largest with nums[0] and traverse the array once to find the maximum value.

  • Keep secondLargest for the best valid candidate and hasSecond to indicate whether such a candidate has been found. The flag avoids relying on a fixed sentinel value.

  • Traverse the array again and consider only values strictly smaller than largest, since values equal to the maximum do not satisfy the distinctness requirement.

  • If no second-largest candidate exists yet, or the current value is greater than secondLargest, update secondLargest and mark hasSecond as true.

  • Return secondLargest when a valid candidate exists; otherwise, return -1.

Dry Run

Second Largest Element Better Force Dry Run.png

Second Largest Element Better Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int secondLargest(vector<int>& nums) {
int n = nums.size();
/*
* At least two values are needed
* to have a distinct second largest.
*/
if (n < 2) {
return -1;
}
int largest = nums[0];
// First pass finds the largest value.
for (int index = 1; index < n; index++) {
if (nums[index] > largest) {
largest = nums[index];
}
}
int secondLargest = 0;
bool hasSecond = false;
/*
* Only values smaller than largest
* can be valid second-largest values.
*/
for (int num : nums) {
if (num < largest) {
/*
* Keep the greatest valid value
* found below the maximum.
*/
if (!hasSecond || num > secondLargest) {
secondLargest = num;
hasSecond = true;
}
}
}
// No valid candidate was found.
if (!hasSecond) {
return -1;
}
return secondLargest;
}
};
int main() {
vector<int> nums = {8, 8, 5, 3, 5};
Solution solution;
cout << solution.secondLargest(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the number of elements. Two complete traversals require O(2N) operations, which simplifies to O(N).

Space Complexity: O(1), because only the largest value, second-largest candidate, and validity flag require auxiliary storage.

Optimal Approach

Both required values can be maintained during a single traversal.

Start with the first array element as the current largest value. Whenever a larger value appears, the previous largest becomes the second-largest candidate before the new value replaces it.

If the current value is smaller than the largest, it can become the second largest only when no valid candidate exists yet or when it is greater than the current second-largest value.

Values equal to the largest are ignored because the required answer must be distinct.

Algorithm

  • Store the array size in n. If n < 2, return -1 because two distinct values cannot exist.

  • Initialize largest with nums[0]. Keep secondLargest for the second-largest candidate and hasSecond to track whether a valid candidate has been found.

  • Traverse the array from index 1, since the first element has already been used to initialize largest.

  • If the current value is greater than largest, move the previous largest into secondLargest before updating largest. The previous maximum now becomes the best value strictly below the new maximum.

  • Otherwise, if the current value is strictly smaller than largest, update secondLargest when no candidate exists yet or when the current value is greater than the existing candidate. Values equal to largest are ignored to preserve distinctness.

  • Return secondLargest when hasSecond is true; otherwise, return -1.

Dry Run

Second Largest Element Optimal Force Dry Run.png

Second Largest Element Optimal Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int secondLargest(vector<int>& nums) {
int n = nums.size();
/*
* At least two values are needed
* to have a distinct second largest.
*/
if (n < 2) {
return -1;
}
int largest = nums[0];
int secondLargest = 0;
bool hasSecond = false;
for (int index = 1; index < n; index++) {
int current = nums[index];
/*
* A new maximum moves the previous
* maximum into second place.
*/
if (current > largest) {
secondLargest = largest;
largest = current;
hasSecond = true;
}
/*
* Values equal to largest are ignored
* because the answer must be distinct.
*/
else if (current < largest) {
/*
* Keep the greatest valid value
* found below the current maximum.
*/
if (!hasSecond || current > secondLargest) {
secondLargest = current;
hasSecond = true;
}
}
}
// No valid candidate was found.
if (!hasSecond) {
return -1;
}
return secondLargest;
}
};
int main() {
vector<int> nums = {8, 8, 5, 3, 5};
Solution solution;
cout << solution.secondLargest(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the number of elements. Every value is processed exactly once.

Space Complexity: O(1), because only two candidate values and two validity flags require auxiliary storage.

FAQs

Q1. Why do duplicate maximum values not qualify as the second-largest value?

The requirement asks for a distinct value strictly smaller than the maximum. Repeated maximum values represent the same distinct value.

Q2. Why are validity flags useful instead of fixed sentinel values?

Validity flags separate candidate existence from candidate value. Negative arrays and full integer ranges remain safe without dependence on artificial minimum constants.

Q3. Does the two-pass approach remain optimal in asymptotic complexity?

Yes. Two linear traversals still produce O(N) time. The one-pass approach reduces traversal count while preserving the same asymptotic complexity.

Q4. Can the index of the second-largest distinct element also be returned?

Yes. An additional index variable can be updated whenever secondLargest changes. If the value appears multiple times, the implementation should clearly define whether the first or any occurrence is returned.

Q5. How can the Kth-largest distinct value be found?

Sorting with duplicate removal, an ordered set, or a size-K heap can extend the same distinct-ranking requirement.

Arrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.6k
Arrays

Main Diagonal Print

Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0] , mat[1][1] , and mat[2][2] . Input: mat = [[10, 20, 30], [40, 50, 60]] Output: 10 50 Exp...

67k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0