Scribd
Upload
8 views3 pages

Finding Second Largest in Java Array

The document outlines the problem of finding the second largest distinct element in a list of integers, returning -1 if no such element exists. It presents various approaches to solve the problem, including a naive sorting method, a set-based method to handle duplicates, and an optimized single-pass approach with O(n) time complexity. Additionally, it emphasizes the importance of proper input parsing and suggests practice problems for further mastery.

Uploaded by

yasaswinisrit
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views3 pages

Finding Second Largest in Java Array

The document outlines the problem of finding the second largest distinct element in a list of integers, returning -1 if no such element exists. It presents various approaches to solve the problem, including a naive sorting method, a set-based method to handle duplicates, and an optimized single-pass approach with O(n) time complexity. Additionally, it emphasizes the importance of proper input parsing and suggests practice problems for further mastery.

Uploaded by

yasaswinisrit
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

🧠 Understanding & Solving: Second Largest Element Problem in Java

📌 Problem Statement:
You are given a list of integers. Your task is to find the second largest distinct element in the
list.
If there is no such element (e.g., all elements are equal), return -1.

🧠 Concepts You Need to Know:


1. Arrays and Loops

2. Input Handling (Scanner, splitting strings)

3. Conditionals (if, else if)

4. Edge Cases (e.g., duplicates, negative values)

Approaches to Solve:

🔸 Naive Approach: Sort the Array


1. Sort the array in descending order.
2. Traverse and find the first number less than the maximum.

Time Complexity: O(n log n)

[Link](arr);
for (int i = [Link] - 2; i >= 0; i--) {
if (arr[i] != arr[[Link] - 1]) {
return arr[i];
}
}

🔸 Using Set + Sort (Handles Duplicates)

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


for (int num : arr)
[Link](num);

Then convert set to list and return second last element.


✅ Optimized Single-Pass Approach (O(n))
1. Maintain two variables: `first` (largest), `second` (second largest).
2. Traverse array:
- if num > first → update second = first, then first = num
- else if num > second and num < first → update second

int first = Integer.MIN_VALUE;


int second = Integer.MIN_VALUE;
for (int num : arr) {
if (num > first) {
second = first;
first = num;
} else if (num > second && num < first) {
second = num;
}
}

⚠️Common Mistake: Input Parsing


If input is provided as space-separated numbers (like HackerRank):
You must read the entire line, split it, and parse each number.

Scanner sc = new Scanner([Link]);


String line = [Link]();
String[] parts = [Link]().split("\\s+");
int[] arr = new int[[Link]];
for (int i = 0; i < [Link]; i++) {
arr[i] = [Link](parts[i]);
}

🔑 What to Learn to Master These Problems:


• Arrays & Loops

• Sorting & Sets

• Edge Case Handling

• Dry Running Logic


🧪 Practice Problems:
1. Find 2nd Largest (HackerRank)

2. Kth Largest Element (Leetcode Medium)

3. Remove Duplicates (GeeksForGeeks)

You might also like