Finding the second largest number in an array is one of the most frequently asked Java array interview questions.

This problem looks simple, but it tests your understanding of:

• Array Traversal
• Comparison Logic
• Variables
• Duplicate Handling
• Edge Cases
• Time Complexity
• Space Complexity

Many advanced problems are built on this concept:

• Kth Largest Element
• Top K Elements
• Ranking Systems
• Leader Elements
• Running Maximum Problems

---

What is the Second Largest Element?

The second largest element is the second highest distinct value present in an array.

Example:

Array

[10, 25, 8, 45, 30]

Largest

45

Second Largest

30

---

Example with Duplicates

Input

[10, 45, 45, 30, 20]

Largest

45

Second Largest

30

Because duplicate 45 values are not considered separate elements.

---

Why is This Question Asked in Interviews?

Interviewers ask this problem because it evaluates:

• Understanding of array traversal
• Handling duplicates
• Maintaining multiple variables
• Optimization thinking
• Edge case handling

A beginner solution may sort the array.

An experienced developer should identify that sorting is unnecessary.

---

Real-World Applications

Finding the second highest value appears in many systems.

---

Employee Salary Ranking

Example:

Salaries

85000

72000

95000

65000

Highest Salary

95000

Second Highest Salary

85000

---

Sports Ranking

Scores:

98

92

87

95

Winner:

98

Runner Up:

95

---

E-Commerce

Product Reviews:

5.0

4.8

4.9

4.5

Highest Rating:

5.0

Second Highest:

4.9

---

Cloud Monitoring

Server Performance:

99%

97%

95%

98%

Highest:

99%

Second Highest:

98%

---

Problem Statement

Given an integer array,

find the second largest distinct element.

---

Example 1

Input

[12, 35, 1, 10, 34, 1]

Output

34

Explanation:

Largest = 35

Second Largest = 34

---

Example 2

Input

[10, 20, 30, 40]

Output

30

---

Example 3

Input

[5, 5, 5]

Output

No second largest element

---

Example 4

Input

[-10, -5, -20]

Output

-10

---

Understanding Second Largest Search

Consider:

[12, 45, 8, 30, 25]

Maintain two values:

Largest

Second Largest

---

Start:

Largest = 12

Second Largest = -∞

---

Read:

45

Update:

Largest = 45

Second Largest = 12

---

Read:

8

Ignore.

---

Read:

30

Update:

Second Largest = 30

---

Read:

25

Ignore.

---

Final:

Largest = 45

Second Largest = 30

---

Mathematical Concept

For every element:

Case 1

Current element is greater than largest:

Second Largest = Largest

Largest = Current

---

Case 2

Current element is between largest and second largest:

Second Largest = Current

---

Array Traversal Visualization

Input:

[10, 50, 20, 40, 30]

Initial:

Largest = 10

Second = -∞

---

Process:

50

Largest = 50
Second = 10

---

Process:

20

Largest = 50
Second = 20

---

Process:

40

Largest = 50
Second = 40

---

Process:

30

No change.

Result:

Second Largest = 40

---

Dry Run

Input:

[15, 8, 25, 10, 20]

Element	Largest	Second Largest	Action
15	15	-∞	Initialize
8	15	8	Update second
25	25	15	New maximum
10	25	15	Ignore
20	25	20	Update second

Output:

20

---

Approach 1 — Single Traversal (Optimal & Recommended)

This is the best interview solution.

Instead of sorting the array,

we maintain:

largest

secondLargest

and update them while traversing once.

---

Algorithm

1. Initialize:

   • largest = Integer.MIN_VALUE
   • secondLargest = Integer.MIN_VALUE

2. Traverse the array.

3. If current element is greater than largest:

secondLargest = largest

largest = current

4. Else if current element is greater than secondLargest and smaller than largest:

secondLargest = current

5. Return secondLargest.

---

Java Program

public class SecondLargestSingleTraversal {

    public static int findSecondLargest(int[] numbers) {

        if (numbers == null || numbers.length < 2) {
            throw new IllegalArgumentException(
                    "Array must contain at least two elements");
        }

        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;

        for (int number : numbers) {

            if (number > largest) {

                secondLargest = largest;
                largest = number;

            } else if (number > secondLargest 
                    && number < largest) {

                secondLargest = number;

            }

        }

        if (secondLargest == Integer.MIN_VALUE) {
            throw new IllegalArgumentException(
                    "No second largest element exists");
        }

        return secondLargest;

    }

    public static void main(String[] args) {

        int[] numbers = {
                12, 35, 1, 10, 34, 1
        };

        System.out.println(
                findSecondLargest(numbers));

    }

}

---

Output

34

---

Step-by-Step Code Explanation

Initialize variables:

int largest = Integer.MIN_VALUE;

int secondLargest = Integer.MIN_VALUE;

This handles negative numbers correctly.

---

Traverse:

for(int number : numbers)

---

Check new largest:

number > largest

Update:

secondLargest = largest;

largest = number;

---

Check second largest:

number > secondLargest
&&
number < largest

Update:

secondLargest = number;

---

Dry Run of Optimal Approach

Input:

[7, 15, 3, 12]

Initial:

largest = -∞

second = -∞

---

Read 7:

largest = 7

second = -∞

---

Read 15:

largest = 15

second = 7

---

Read 3:

Ignore.

---

Read 12:

second = 12

Final:

Second Largest = 12

---

Advantages

• Optimal O(n) solution.
• Only one traversal.
• Constant extra space.
• Handles negative numbers.
• Interview preferred approach.

---

Drawbacks

• Logic is slightly harder than sorting.
• Must carefully handle duplicates.

---

Approach 2 — Using Sorting

The easiest approach is:

1. Sort the array.
2. Traverse from the end.
3. Find the first value smaller than the largest.

---

Example

Input:

[10,45,30,45,20]

Sorted:

[10,20,30,45,45]

Largest:

45

Second Largest:

30

---

Java Program

import java.util.Arrays;

public class SecondLargestSorting {

    public static int findSecondLargest(int[] numbers) {

        Arrays.sort(numbers);

        int largest =
                numbers[numbers.length - 1];

        for (int i = numbers.length - 2;
             i >= 0;
             i--) {

            if (numbers[i] != largest) {
                return numbers[i];
            }

        }

        throw new IllegalArgumentException(
                "No second largest element");

    }

    public static void main(String[] args) {

        int[] numbers = {
                12,35,1,10,34,1
        };

        System.out.println(
                findSecondLargest(numbers));

    }

}

---

Output

34

---

Time & Space Complexity

Approach	Time	Space
Single Traversal	O(n)	O(1)
Sorting	O(n log n)	O(1)*

---

Comparison

Feature	Single Traversal	Sorting
Interview Preferred	⭐⭐⭐⭐⭐	⭐⭐⭐
Performance	⭐⭐⭐⭐⭐	⭐⭐
Simple Logic	⭐⭐⭐⭐	⭐⭐⭐⭐⭐
Handles Large Data	✅	Less Efficient

---

Advantages

Single Traversal:

• Fastest.
• Memory efficient.
• Production ready.

Sorting:

• Easier implementation.
• Useful when sorted data is needed anyway.

---

Drawbacks

Single Traversal:

• Requires careful duplicate handling.

Sorting:

• Extra unnecessary work.
• Changes original array.

---

Approach 3 — Using Java Streams

Java Streams provide a functional programming approach to solve the second largest element problem.

The idea is:

1. Remove duplicate values.
2. Sort values in descending order.
3. Skip the first element.
4. Return the next element.

---

Algorithm

1. Convert array into Stream.
2. Remove duplicate values using distinct().
3. Sort in descending order.
4. Skip the largest element.
5. Find the first remaining element.

---

Java Program

import java.util.Arrays;

public class SecondLargestStreams {

    public static int findSecondLargest(int[] numbers) {

        return Arrays.stream(numbers)
                .distinct()
                .boxed()
                .sorted((a, b) -> b - a)
                .skip(1)
                .findFirst()
                .orElseThrow(() ->
                        new IllegalArgumentException(
                                "No second largest element"));

    }

    public static void main(String[] args) {

        int[] numbers = {
                12, 35, 1, 10, 34, 1
        };

        System.out.println(
                findSecondLargest(numbers));

    }

}

---

Output

34

---

Step-by-Step Explanation

Convert array into Stream:

Arrays.stream(numbers)

---

Remove duplicates:

.distinct()

Example:

45,45,30,20

becomes

45,30,20

---

Sort descending:

.sorted((a,b) -> b-a)

Result:

45,30,20

---

Skip largest:

.skip(1)

Remaining:

30,20

---

Get first value:

.findFirst()

Result:

30

---

Advantages

• Clean and concise.
• Uses modern Java features.
• Handles duplicates easily.
• Good for functional programming style.

---

Drawbacks

• Creates intermediate streams.
• More memory overhead than single traversal.
• Less preferred for coding interviews.

---

Approach 4 — Using TreeSet

A TreeSet automatically:

• Removes duplicates.
• Maintains sorted order.

This makes it a simple solution for finding the second largest distinct value.

---

How TreeSet Works

Input:

[10,45,30,45,20]

TreeSet stores:

10

20

30

45

Largest:

45

Second Largest:

30

---

Algorithm

1. Insert all elements into TreeSet.
2. Remove the largest element.
3. Return the new largest element.

---

Java Program

import java.util.TreeSet;

public class SecondLargestTreeSet {

    public static int findSecondLargest(int[] numbers) {

        TreeSet<Integer> set = new TreeSet<>();

        for (int number : numbers) {

            set.add(number);

        }

        if (set.size() < 2) {

            throw new IllegalArgumentException(
                    "No second largest element");

        }

        set.pollLast();

        return set.last();

    }

    public static void main(String[] args) {

        int[] numbers = {
                12, 35, 1, 10, 34, 1
        };

        System.out.println(
                findSecondLargest(numbers));

    }

}

---

Output

34

---

Step-by-Step Explanation

Create TreeSet:

TreeSet<Integer> set =
        new TreeSet<>();

---

Add values:

set.add(number);

TreeSet automatically sorts.

Example:

Input:

12,35,1,10,34

TreeSet:

1,10,12,34,35

---

Remove largest:

set.pollLast();

Remaining:

1,10,12,34

---

Return last element:

set.last();

Result:

34

---

Advantages

• Very simple implementation.
• Automatically handles duplicates.
• Maintains sorted order.

---

Drawbacks

• Uses additional memory.
• Slower than O(n) solution.
• Tree operations require O(log n).

---

Approach 5 — Using Priority Queue (Min Heap)

Priority Queue can be used to keep track of the two largest elements.

For finding only the second largest,

we maintain a Min Heap of size 2.

---

Idea

Example:

Input:

[12,35,1,10,34]

Maintain:

Heap Size = 2

Process:

12

Heap:

12

---

Process:

35

Heap:

12,35

---

Process:

34

Remove smallest:

12

Heap:

34,35

Smallest value in heap:

34

is the second largest.

---

Java Program

import java.util.PriorityQueue;

public class SecondLargestPriorityQueue {

    public static int findSecondLargest(int[] numbers) {

        PriorityQueue<Integer> heap =
                new PriorityQueue<>();

        for (int number : numbers) {

            if (!heap.contains(number)) {

                heap.offer(number);

                if (heap.size() > 2) {

                    heap.poll();

                }

            }

        }

        if (heap.size() < 2) {

            throw new IllegalArgumentException(
                    "No second largest element");

        }

        return heap.peek();

    }

    public static void main(String[] args) {

        int[] numbers = {
                12,35,1,10,34,1
        };

        System.out.println(
                findSecondLargest(numbers));

    }

}

---

Output

34

---

Advantages

• Useful when solving Kth largest problems.
• Extends naturally to Top K problems.
• Efficient for streaming data.

---

Drawbacks

• More complex than required.
• Heap operations add overhead.
• contains() operation makes this implementation less optimal.

---

Handling Duplicate Values

Important interview clarification:

What does "second largest" mean?

---

Case 1 — Distinct Second Largest

Example:

[10,20,20,15]

Answer:

15

Because:

Largest = 20

Second Largest = 15

---

Case 2 — Including Duplicates

Example:

[10,20,20,15]

Sorted:

10,15,20,20

Second element from end:

20

Different interpretation.

Always clarify with interviewer.

---

Handling Negative Numbers

Example:

[-10,-5,-20,-1]

Largest:

-1

Second Largest:

-5

Incorrect:

int largest = 0;

because zero is greater than all values.

Correct:

int largest = Integer.MIN_VALUE;

---

Integer Overflow Considerations

Comparison operations do not cause overflow.

Example:

if(number > largest)

is safe.

However, avoid:

b - a

inside comparators for extreme values.

Example:

Integer.MAX_VALUE - (-1)

can overflow.

Safer:

Integer.compare(b, a)

Example:

.sorted((a,b) ->
        Integer.compare(b,a))

---

Comparison of All Approaches

Approach	Time Complexity	Space	Interview Rating
Single Traversal	O(n)	O(1)	⭐⭐⭐⭐⭐
Sorting	O(n log n)	O(1)	⭐⭐⭐
Streams	O(n log n)	O(n)	⭐⭐⭐⭐
TreeSet	O(n log n)	O(n)	⭐⭐⭐
Priority Queue	O(n log k)	O(k)	⭐⭐⭐⭐

---

Common Interview Mistakes

Mistake 1

Returning the largest value again.

Example:

[10,20,20,15]

Wrong:

20

Correct:

15

---

Mistake 2

Ignoring duplicates.

Always clarify whether the second largest must be distinct.

---

Mistake 3

Initializing values incorrectly.

Wrong:

int largest = 0;

Correct:

int largest = Integer.MIN_VALUE;

---

Mistake 4

Sorting unnecessarily.

Sorting works but is not optimal.

---

Mistake 5

Not handling arrays with fewer than two distinct elements.

Example:

[5,5,5]

There is no second largest value.

---

Edge Cases

Input	Output
[10,20,30]	20
[5,5,5]	No second largest
[-1,-5,-3]	-3
[100]	Invalid
[Integer.MAX_VALUE,Integer.MIN_VALUE]	Integer.MIN_VALUE

---

Interview Follow-up Questions

Q1. Find the third largest element.

Q2. Find the Kth largest element.

Q3. Find second largest without sorting.

Q4. Find second largest in one traversal.

Q5. What if duplicates are allowed?

Q6. How would you process numbers coming from a stream?

Q7. How would you solve this using a heap?

Q8. What is the optimal time complexity?

Q9. Can you find largest and second largest together?

Q10. How would you handle billions of numbers?

---

Related Problems

• Find Maximum Element
• Find Minimum Element
• Third Largest Number
• Kth Largest Element
• Top K Frequent Elements
• Leader Elements
• Maximum Difference
• Ranking Algorithms

---

Key Takeaways

• The optimal solution is Single Traversal O(n).
• Maintain two variables:
  • Largest
  • Second Largest
• Always clarify duplicate behavior.
• Use Integer.MIN_VALUE to handle negative numbers.
• Sorting is simple but inefficient.
• TreeSet and Priority Queue are useful alternatives for different scenarios.

---

Frequently Asked Interview Questions

Q1. What is the best approach?

Single Traversal is the best approach.

Complexity:

Time: O(n)

Space: O(1)

---

Q2. Why not sort?

Sorting does extra work:

O(n log n)

when only one scan is required.

---

Q3. How do you handle duplicates?

Use a condition:

number < largest

when updating second largest.

---

Q4. Why use Integer.MIN_VALUE?

It correctly supports arrays containing only negative numbers.

---

Q5. Which approach is useful for streaming data?

Priority Queue is useful because it can maintain the top K values while processing incoming data.

---

Interview Tip

If asked:

"Find the second largest number in an array."

Start with:

Single Traversal Approach

Explain:

1. Maintain largest.
2. Maintain secondLargest.
3. Update both during one pass.

Then discuss alternatives:

1. Single Traversal (Best)
2. Sorting
3. Java Streams
4. TreeSet
5. Priority Queue

Before coding, clarify:

• Should duplicates count?
• Is the second largest distinct?
• Can the array contain negative values?
• What should happen if no second largest exists?

A clear explanation of assumptions and trade-offs demonstrates strong algorithmic thinking.