Find the Second Largest Distinct Element in an Array

When working with arrays, one common interview question is finding the second largest distinct element. Unlike just sorting the array, we want an efficient solution with O(N) time complexity and O(1) space complexity.

Let’s carefully break down the problem.

---

Problem Statement

You are given an array Arr of size N. You need to print the second largest distinct element in the array.

• If the second largest element doesn’t exist (all elements are the same), return -1.

---

Example 1

Input:

N = 6
Arr[] = {12, 35, 1, 10, 34, 1}

Output:

34

Explanation:

• Largest element = 35

• Second largest element = 34

---

Example 2

Input:

N = 3
Arr[] = {10, 5, 10}

Output:

5

Explanation:

• Largest element = 10

• Second largest distinct element = 5

---

Constraints

• 2 ≤ N ≤ 10^5

• 1 ≤ Arr[i] ≤ 10^5

---

Naive Approach (Sorting)

The simplest approach would be:

1. Sort the array in descending order.

2. Pick the first element as the largest.

3. Find the next distinct element as the second largest.

But sorting takes O(N log N), which is not optimal when N can go up to 10^5.

---

Optimal Approach (Single Pass - O(N))

We can solve this in just one pass:

1. Maintain two variables:

   • first → largest element

   • second → second largest element

2. Traverse the array:

   • If arr[i] > first: update second = first and first = arr[i].

   • Else if arr[i] > second and arr[i] != first: update second = arr[i].

3. At the end:

   • If second is still -1, return -1.

---

Implementation (Java)

class Solution {
    int print2largest(int arr[], int n) {
        int first = -1, second = -1;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] > first) {
                second = first;
                first = arr[i];
            } else if (arr[i] > second && arr[i] != first) {
                second = arr[i];
            }
        }
        
        return second;
    }
}

---

Dry Run Example

Input: Arr[] = {12, 35, 1, 10, 34, 1}

• Start: first = -1, second = -1

• 12: first = 12, second = -1

• 35: first = 35, second = 12

• 1: no update

• 10: second = 12 → stays

• 34: second = 34 (since 34 < 35 but > 12)

• 1: no update

Answer = 34 ✅

---

Key Takeaways

• Time Complexity: O(N) → Single traversal.

• Space Complexity: O(1) → Only two variables used.

• Works for large arrays efficiently.

---

Common Mistakes

1. Forgetting to check for distinctness (e.g., {10, 10, 10} should return -1).

2. Not updating the second properly when a new first is found.

3. Returning the same value as largest when all elements are equal.

---

Final Words

This is a classic array problem that helps you think about tracking multiple values in one pass without sorting. It’s a great stepping stone to more advanced interview questions where optimization matters.

👉 If you’ve understood this, try extending the idea to find the third largest distinct element in an array!

---

Would you like me to also write the Python version of this solution for your blog readers who might prefer Python over Java?