Second Smallest And Second Largest Element In An Array In Java

Finding specific elements within a dataset is a common task in programming. In this article, you will learn how to efficiently determine the second smallest and second largest elements present in an array using various Java programming techniques.

Problem Statement

Given an unsorted array of integers, the challenge is to identify the second smallest and second largest values. This problem often arises in scenarios requiring percentile analysis, outlier detection, or ranking, where the absolute minimum or maximum might not provide sufficient insight. For instance, in performance metrics, sometimes the top or bottom performer is an anomaly, and the "next best" or "next worst" provides a more stable metric.

Example

Consider an array [10, 5, 20, 15, 25]. The smallest element is 5. The second smallest element is 10. The largest element is 25. The second largest element is 20.

Background & Knowledge Prerequisites

To understand the solutions presented, a basic understanding of the following Java concepts is beneficial:

• Arrays: How to declare, initialize, and access elements.
• Loops: for loops for iterating through arrays.
• Conditional Statements: if and else if for comparisons.
• Sorting Algorithms: Basic concept of how sorting works, especially for the first approach.
• Data Structures: Basic understanding of collections (though not strictly required for all approaches).

Use Cases or Case Studies

Identifying the second smallest or second largest element has several practical applications:

1. Performance Analysis: In a system monitoring application, you might want to find the server with the second-highest CPU utilization to identify potential bottlenecks before they reach critical levels.
2. Tournament Rankings: Determining the silver medalist (second highest score) in a competition where ties need careful handling.
3. Financial Data Analysis: When analyzing stock prices, finding the second lowest or second highest price over a period can help in trend analysis, filtering out extreme outliers.
4. Quality Control: In manufacturing, identifying product batches with the second smallest or second largest defect rate can indicate a specific process issue that isn't the absolute worst but still needs attention.
5. Student Grading: Finding the second-highest score in a class to award a special mention, distinct from the top scorer.

Solution Approaches

Approach 1: Sorting the Array

This is the most straightforward method. By sorting the array, the second smallest element will be at index 1 (assuming 0-based indexing) and the second largest will be at array.length - 2, after handling potential duplicates.

// FindSecondSmallestAndLargest_Sorting
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 5, 20, 15, 25, 5}; // Example array with duplicates

        // Step 1: Handle edge cases for arrays with less than 2 elements
        if (arr.length < 2) {
            System.out.println("Array must contain at least two elements.");
            return;
        }

        // Step 2: Sort the array in ascending order
        Arrays.sort(arr);

        // Step 3: Find the second smallest element
        // Iterate to find the first element different from the smallest
        int smallest = arr[0];
        int secondSmallest = Integer.MAX_VALUE; // Initialize with max value
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > smallest) {
                secondSmallest = arr[i];
                break; // Found the second distinct smallest
            }
        }

        // Step 4: Find the second largest element
        // Iterate backwards to find the first element different from the largest
        int largest = arr[arr.length - 1];
        int secondLargest = Integer.MIN_VALUE; // Initialize with min value
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] < largest) {
                secondLargest = arr[i];
                break; // Found the second distinct largest
            }
        }

        // Step 5: Print the results, checking if distinct elements were found
        if (secondSmallest == Integer.MAX_VALUE) {
            System.out.println("No distinct second smallest element found.");
        } else {
            System.out.println("Second Smallest: " + secondSmallest);
        }

        if (secondLargest == Integer.MIN_VALUE) {
            System.out.println("No distinct second largest element found.");
        } else {
            System.out.println("Second Largest: " + secondLargest);
        }
    }
}

Run

Sample Output:

Second Smallest: 10
Second Largest: 20

Explanation:

1. The Arrays.sort() method sorts the input array in place, arranging elements from smallest to largest.
2. After sorting, the absolute smallest element is at arr[0]. We then iterate from the second element (arr[1]) to find the first element that is strictly greater than arr[0], which will be our distinct second smallest.
3. Similarly, the absolute largest element is at arr[arr.length - 1]. We iterate backward from arr[arr.length - 2] to find the first element strictly smaller than arr[arr.length - 1], giving us the distinct second largest.
4. Edge cases for arrays with fewer than two elements or arrays where all elements are the same (e.g., [5, 5, 5]) are considered by initializing secondSmallest and secondLargest to Integer.MAX_VALUE and Integer.MIN_VALUE respectively, and printing appropriate messages if no distinct second element is found.

Approach 2: Two-Pass Iteration

This approach involves iterating through the array twice. In the first pass, we find the absolute smallest/largest element. In the second pass, we find the second smallest/largest element while ensuring it's not the same as the first smallest/largest.

// FindSecondSmallestAndLargest_TwoPass
public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 5, 20, 15, 25, 5}; // Example array

        // Step 1: Handle edge cases
        if (arr.length < 2) {
            System.out.println("Array must contain at least two elements.");
            return;
        }

        // --- Find Second Smallest ---
        // Step 2: Initialize smallest and secondSmallest
        int smallest = Integer.MAX_VALUE;
        int secondSmallest = Integer.MAX_VALUE;

        // Step 3: First pass to find the absolute smallest
        for (int num : arr) {
            if (num < smallest) {
                smallest = num;
            }
        }

        // Step 4: Second pass to find the second smallest
        // Ensure it's not the same as the smallest
        for (int num : arr) {
            if (num < secondSmallest && num != smallest) {
                secondSmallest = num;
            }
        }

        // --- Find Second Largest ---
        // Step 5: Initialize largest and secondLargest
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;

        // Step 6: First pass to find the absolute largest
        for (int num : arr) {
            if (num > largest) {
                largest = num;
            }
        }

        // Step 7: Second pass to find the second largest
        // Ensure it's not the same as the largest
        for (int num : arr) {
            if (num > secondLargest && num != largest) {
                secondLargest = num;
            }
        }

        // Step 8: Print the results
        if (secondSmallest == Integer.MAX_VALUE) {
            System.out.println("No distinct second smallest element found.");
        } else {
            System.out.println("Second Smallest: " + secondSmallest);
        }

        if (secondLargest == Integer.MIN_VALUE) {
            System.out.println("No distinct second largest element found.");
        } else {
            System.out.println("Second Largest: " + secondLargest);
        }
    }
}

Run

Sample Output:

Second Smallest: 10
Second Largest: 20

Explanation:

1. We initialize smallest and secondSmallest to Integer.MAX_VALUE, and largest and secondLargest to Integer.MIN_VALUE. This ensures that any element in the array will be smaller than MAX_VALUE and larger than MIN_VALUE.
2. For the second smallest: The first loop finds the absolute smallest element. The second loop then finds the smallest element among the remaining values, specifically ensuring it's not equal to the absolute smallest.
3. For the second largest: Similarly, the first loop finds the absolute largest element. The second loop then finds the largest element among the remaining values, ensuring it's not equal to the absolute largest.
4. Edge cases are handled by checking if secondSmallest or secondLargest remain their initial MAX_VALUE or MIN_VALUE, respectively, indicating no distinct second element was found.

Approach 3: Single-Pass Iteration

This is the most efficient approach, requiring only a single pass through the array to find both the smallest/largest and second smallest/largest elements simultaneously.

// FindSecondSmallestAndLargest_SinglePass
public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 5, 20, 15, 25, 5}; // Example array

        // Step 1: Handle edge cases
        if (arr.length < 2) {
            System.out.println("Array must contain at least two elements.");
            return;
        }

        // Step 2: Initialize variables for smallest and largest elements
        int smallest = Integer.MAX_VALUE;
        int secondSmallest = Integer.MAX_VALUE;
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;

        // Step 3: Iterate through the array once
        for (int num : arr) {
            // Logic for smallest and second smallest
            if (num < smallest) {
                secondSmallest = smallest; // Current smallest becomes second smallest
                smallest = num;            // Current num becomes new smallest
            } else if (num < secondSmallest && num != smallest) {
                secondSmallest = num;      // Update second smallest if num is between smallest and secondSmallest
            }

            // Logic for largest and second largest
            if (num > largest) {
                secondLargest = largest;   // Current largest becomes second largest
                largest = num;             // Current num becomes new largest
            } else if (num > secondLargest && num != largest) {
                secondLargest = num;       // Update second largest if num is between largest and secondLargest
            }
        }

        // Step 4: Print the results
        if (secondSmallest == Integer.MAX_VALUE) {
            System.out.println("No distinct second smallest element found.");
        } else {
            System.out.println("Second Smallest: " + secondSmallest);
        }

        if (secondLargest == Integer.MIN_VALUE) {
            System.out.println("No distinct second largest element found.");
        } else {
            System.out.println("Second Largest: " + secondLargest);
        }
    }
}

Run

Sample Output:

Second Smallest: 10
Second Largest: 20

Explanation:

1. We initialize smallest, secondSmallest, largest, and secondLargest to their respective MAX_VALUE or MIN_VALUE to ensure initial values are correctly overridden by any array element.
2. As we iterate through the array:

• If the current number (num) is smaller than smallest, it means we found a new absolute smallest. The old smallest value is promoted to secondSmallest, and num becomes the new smallest.
• If num is not the absolute smallest but is smaller than secondSmallest (and distinct from smallest), then num becomes the new secondSmallest.
• The same logic is applied symmetrically for largest and secondLargest.

1. After the single pass, smallest, secondSmallest, largest, and secondLargest will hold their correct values.
2. Edge cases are handled similarly to the two-pass approach.

Conclusion

Finding the second smallest and second largest elements in an array can be achieved using various methods, each with its own trade-offs. While sorting offers simplicity, single-pass iteration provides optimal time complexity, making it suitable for larger datasets. The choice of approach depends on factors like array size, performance requirements, and readability preferences.

Summary

• Sorting: Easiest to implement using Arrays.sort(). Time complexity is typically O(N log N) for sorting, plus O(N) for finding distinct second elements, making it less efficient for very large arrays.
• Two-Pass Iteration: Requires two separate passes through the array. Time complexity is O(N) for finding both elements, as each element is processed a constant number of times.
• Single-Pass Iteration: Most efficient with O(N) time complexity. It processes each element only once to track both the largest/smallest and second largest/smallest values simultaneously.
• Edge Cases: Always consider arrays with fewer than two elements and arrays containing duplicate values when designing the solution logic.
• Initialization: Use Integer.MAX_VALUE and Integer.MIN_VALUE for robust initial variable assignment to handle any range of integer values in the array.