How To Find Third Largest And Second Smallest Element In An Array In Java

Finding specific elements like the third largest or second smallest in an array is a common task in programming, often appearing in data analysis or competitive programming. Understanding efficient methods for these operations is crucial for optimizing your Java applications.

In this article, you will learn how to efficiently find the third largest and second smallest elements within an array using Java, exploring both sorting-based and iterative approaches.

Problem Statement

Given an array of integers, the goal is to identify:

1. The third largest element.
2. The second smallest element.

This problem requires careful consideration of array size (e.g., what if the array has fewer than three elements?) and the presence of duplicate values. Efficient solutions are preferred, especially for large datasets.

Example

Consider the following integer array: int[] numbers = {10, 5, 20, 8, 15, 20, 12, 5};

• Sorted version (ascending): [5, 5, 8, 10, 12, 15, 20, 20]
• Second smallest element: 5 (at index 1)
• Third largest element: 15 (at index length - 3)

Background & Knowledge Prerequisites

To follow this tutorial, you should have a basic understanding of:

• Java Basics: Variables, loops (for loop), conditional statements (if-else).
• Arrays: Declaring, initializing, and accessing elements in Java arrays.
• java.util.Arrays class: Familiarity with utility methods like sort().
• Integer Wrapper Class: Integer.MIN_VALUE and Integer.MAX_VALUE for initialization.

No special setup or external libraries are required beyond a standard Java Development Kit (JDK) installation.

Use Cases or Case Studies

Identifying Nth largest/smallest elements has several practical applications:

• Data Analysis: Finding outliers, top performers (e.g., third highest sales), or bottom performers (e.g., second lowest error rate).
• Competitive Programming: This is a classic problem often encountered in coding challenges to test understanding of array manipulation and efficiency.
• Ranking Systems: Determining ranks in a leaderboard where only a specific range (e.g., top 3, bottom 2) is relevant.
• Resource Allocation: Identifying the second least utilized server or the third most available network port.
• Statistical Computations: As a preliminary step in calculating specific quantiles or robust statistics.

Solution Approaches

We will explore two primary approaches: one utilizing sorting and another employing an iterative method for better time complexity in specific scenarios.

Approach 1: Sorting the Array

Sorting the array is the most straightforward method. Once sorted, the elements can be accessed directly by their index.

• Summary: Sort the array in ascending order and then access the elements at the appropriate indices (1 for second smallest, length - 3 for third largest).
• Pros: Simple to understand and implement.
• Cons: Time complexity is O(N log N) due to sorting, which might not be optimal for very large arrays if only a few specific elements are needed.

// FindNthElementsUsingSorting
import java.util.Arrays;
import java.util.OptionalInt;

public class Main {
    public static void main(String[] args) {
        int[] numbers = {10, 5, 20, 8, 15, 20, 12, 5};
        System.out.println("Original array: " + Arrays.toString(numbers));

        // Step 1: Handle edge cases for array size
        if (numbers.length < 2) {
            System.out.println("Array must have at least 2 elements to find second smallest.");
            return;
        }
        if (numbers.length < 3) {
            System.out.println("Array must have at least 3 elements to find third largest.");
            return;
        }

        // Step 2: Sort the array
        Arrays.sort(numbers);
        System.out.println("Sorted array: " + Arrays.toString(numbers));

        // Step 3: Find the second smallest element
        // After sorting, the second smallest element is at index 1
        int secondSmallest = numbers[1];

        // Step 4: Find the third largest element
        // After sorting, the third largest element is at index length - 3
        int thirdLargest = numbers[numbers.length - 3];

        System.out.println("Second Smallest Element: " + secondSmallest);
        System.out.println("Third Largest Element: " + thirdLargest);
    }
}

Run

Sample Output:

Original array: [10, 5, 20, 8, 15, 20, 12, 5]
Sorted array: [5, 5, 8, 10, 12, 15, 20, 20]
Second Smallest Element: 5
Third Largest Element: 15

Stepwise Explanation:

1. Input Array: An integer array numbers is initialized.
2. Edge Case Handling: It first checks if the array has at least 2 elements for the second smallest and at least 3 elements for the third largest. If not, it prints an appropriate message and exits.
3. Sort Array: Arrays.sort(numbers) sorts the array in ascending order.
4. Find Second Smallest: The element at numbers[1] (the second element after sorting) is the second smallest.
5. Find Third Largest: The element at numbers[numbers.length - 3] (the third element from the end after sorting) is the third largest.

Approach 2: Iterating Without Sorting

This approach involves iterating through the array once or twice, maintaining track of the largest/smallest elements found so far. This can achieve O(N) time complexity, making it more efficient for very large arrays.

• Summary: Initialize variables to track the first, second, and third largest elements (or first and second smallest). Iterate through the array, updating these variables as larger/smaller elements are encountered.
• Pros: Better time complexity (O(N)) compared to sorting.
• Cons: More complex logic and requires careful handling of initialization and updates, especially with duplicates.

// FindNthElementsIterative
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] numbers = {10, 5, 20, 8, 15, 20, 12, 5};
        System.out.println("Original array: " + Arrays.toString(numbers));

        // Step 1: Handle edge cases for array size
        if (numbers.length < 2) {
            System.out.println("Array must have at least 2 elements to find second smallest.");
            return;
        }
        if (numbers.length < 3) {
            System.out.println("Array must have at least 3 elements to find third largest.");
            return;
        }

        // --- Find Second Smallest Element ---
        // Initialize firstSmallest and secondSmallest to maximum possible integer value
        int firstSmallest = Integer.MAX_VALUE;
        int secondSmallest = Integer.MAX_VALUE;

        // Step 2: Iterate through the array to find the second smallest
        for (int num : numbers) {
            if (num < firstSmallest) {
                // If current number is smaller than firstSmallest, update both
                secondSmallest = firstSmallest;
                firstSmallest = num;
            } else if (num < secondSmallest && num != firstSmallest) {
                // If current number is smaller than secondSmallest but not equal to firstSmallest, update secondSmallest
                secondSmallest = num;
            }
        }

        // --- Find Third Largest Element ---
        // Initialize largest1, largest2, and largest3 to minimum possible integer value
        int largest1 = Integer.MIN_VALUE;
        int largest2 = Integer.MIN_VALUE;
        int largest3 = Integer.MIN_VALUE;

        // Step 3: Iterate through the array to find the third largest
        for (int num : numbers) {
            if (num > largest1) {
                // If current number is greater than largest1, shift all down
                largest3 = largest2;
                largest2 = largest1;
                largest1 = num;
            } else if (num > largest2 && num != largest1) {
                // If current number is greater than largest2 but not equal to largest1
                largest3 = largest2;
                largest2 = num;
            } else if (num > largest3 && num != largest2 && num != largest1) {
                // If current number is greater than largest3 but not equal to largest1 or largest2
                largest3 = num;
            }
        }

        System.out.println("Second Smallest Element: " + secondSmallest);
        System.out.println("Third Largest Element: " + largest3);
    }
}

Run

Sample Output:

Original array: [10, 5, 20, 8, 15, 20, 12, 5]
Second Smallest Element: 5
Third Largest Element: 15

Stepwise Explanation:

1. Input Array & Edge Cases: Same as Approach 1, handling arrays too small for the requested elements.
2. Find Second Smallest:

• firstSmallest and secondSmallest are initialized to Integer.MAX_VALUE.
• The loop iterates through each num in the array.
• If num is less than firstSmallest, it becomes the new firstSmallest, and the old firstSmallest becomes secondSmallest.
• If num is less than secondSmallest but *not equal to* firstSmallest (to handle duplicates correctly for distinct second smallest if needed, or simply for strict positional values), it becomes the new secondSmallest.

1. Find Third Largest:

• largest1, largest2, largest3 are initialized to Integer.MIN_VALUE.
• The loop iterates through each num in the array.
• If num is greater than largest1, it means we found a new largest. The existing largest1 moves to largest2, largest2 to largest3, and num becomes largest1.
• If num is greater than largest2 but not equal to largest1, it means num is the new second largest. The existing largest2 moves to largest3, and num becomes largest2.
• If num is greater than largest3 but not equal to largest1 or largest2, it becomes the new largest3.

Conclusion

Both sorting and iterative methods provide valid solutions for finding the third largest and second smallest elements in a Java array. The sorting approach is simpler to implement and read, making it suitable for smaller arrays or when the array needs to be sorted for other purposes. The iterative approach offers better time complexity (O(N)), making it more efficient for very large arrays where performance is critical and only a few specific elements are needed. The choice depends on the specific requirements for clarity versus performance.

Summary

• Problem: Find the third largest and second smallest elements in an array.
• Approach 1 (Sorting):
• Uses Arrays.sort() (O(N log N) time complexity).
• Access elements directly at indices 1 (second smallest) and length - 3 (third largest).
• Simple and easy to understand.
• Approach 2 (Iterative):
• Uses a single pass through the array (O(N) time complexity).
• Maintains variables for firstSmallest, secondSmallest, largest1, largest2, largest3.
• More efficient for large arrays but requires more careful logic.
• Edge Cases: Always check for array lengths (e.g., must have at least 2 elements for second smallest, 3 for third largest).
• Duplicates: Both methods correctly handle duplicate values by finding the elements based on their *position* if sorted, or by carefully updating tracked values in the iterative approach.