Java Program To Find Second Smallest Element In An Array

Finding specific elements within an array is a common task in programming. While identifying the smallest or largest element is straightforward, locating the *second* smallest requires a slightly more refined approach.

In this article, you will learn how to efficiently find the second smallest element in a Java array using various methods, catering to different performance considerations and array characteristics.

Problem Statement

The challenge is to identify the second smallest distinct numerical value within a given array of integers. This problem often arises when filtering data, ranking items, or performing statistical analysis where extreme outliers (the absolute minimum) need to be considered separately or ignored. For instance, in a list of product prices, finding the second lowest price could reveal a competitive offering that isn't the absolute cheapest.

Consider an array like [5, 2, 8, 1, 9, 3]. The smallest element is 1, and the second smallest is 2. If the array is [7, 7, 3, 3, 5], the smallest distinct element is 3, and the second smallest distinct element is 5. Special attention must be paid to arrays with duplicate values and edge cases like arrays with fewer than two elements.

Example

Given an array [12, 5, 2, 10, 8, 2, 1] as input, the program should identify 2 as the second smallest element.

Background & Knowledge Prerequisites

To effectively 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 over array elements.
• Conditional Statements: if-else structures for logic.
• java.util.Arrays class: Basic methods like sort() (for one of the approaches).
• Integer.MAX_VALUE: A constant representing the maximum possible value for an int, useful for initializing variables that will hold minimums.

Use Cases or Case Studies

Finding the second smallest element has several practical applications across different domains:

• Financial Analysis: Identifying the second-lowest stock price over a period to understand market trends or find competitive entry points after filtering out potential data errors or extreme dips.
• Performance Benchmarking: In a series of test runs for an application's response time, finding the second fastest time can give a more robust performance metric by ignoring the absolute best (which might be an anomaly).
• Data Validation: When processing sensor data, the second smallest reading might indicate a more typical minimum value if the absolute smallest is suspected to be an erroneous zero reading.
• Competitive Programming: A classic problem used to test logical thinking, array manipulation skills, and efficiency in algorithms.
• Educational Ranking: In a small class, finding the second-lowest score can help identify students who might need targeted intervention, just above the lowest performer.

Solution Approaches

Here, we explore three distinct approaches to find the second smallest element, each with its trade-offs in terms of simplicity and efficiency.

Approach 1: Sorting the Array

This is the most intuitive method. By sorting the array, the smallest element will be at index 0, and the second smallest (if distinct) will be at index 1.

• Summary: Sorts the array in ascending order and then picks the element at the second position (index 1), after handling duplicates.

// FindSecondSmallest_Sorting
import java.util.Arrays;

public class Main {
    public static int findSecondSmallestUsingSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            System.out.println("Array must contain at least two elements.");
            return -1; // Indicate error or invalid input
        }

        // Step 1: Sort the array
        Arrays.sort(arr);

        // Step 2: Iterate to find the second distinct smallest element
        // The smallest element is at arr[0].
        // We look for the first element greater than arr[0].
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[0]) {
                return arr[i]; // This is the second smallest distinct element
            }
        }
        
        // If all elements are the same (e.g., [5, 5, 5]),
        // there is no distinct second smallest element.
        System.out.println("No distinct second smallest element found.");
        return -1;
    }

    public static void main(String[] args) {
        int[] arr1 = {12, 5, 2, 10, 8, 2, 1};
        System.out.println("Original array: " + Arrays.toString(arr1));
        System.out.println("Second smallest element (Sorting): " + findSecondSmallestUsingSort(arr1)); // Output: 5

        int[] arr2 = {7, 7, 3, 3, 5};
        System.out.println("Original array: " + Arrays.toString(arr2));
        System.out.println("Second smallest element (Sorting): " + findSecondSmallestUsingSort(arr2)); // Output: 5

        int[] arr3 = {10, 10, 10, 10};
        System.out.println("Original array: " + Arrays.toString(arr3));
        System.out.println("Second smallest element (Sorting): " + findSecondSmallestUsingSort(arr3)); // Output: -1

        int[] arr4 = {5};
        System.out.println("Original array: " + Arrays.toString(arr4));
        System.out.println("Second smallest element (Sorting): " + findSecondSmallestUsingSort(arr4)); // Output: -1
    }
}

Run

• Sample Output:

  Original array: [12, 5, 2, 10, 8, 2, 1]
  Second smallest element (Sorting): 5
  Original array: [7, 7, 3, 3, 5]
  Second smallest element (Sorting): 5
  Original array: [10, 10, 10, 10]
  No distinct second smallest element found.
  Second smallest element (Sorting): -1
  Original array: [5]
  Array must contain at least two elements.
  Second smallest element (Sorting): -1

• Stepwise Explanation:

1. Input Validation: Checks if the array is null or has fewer than two elements, returning -1 if invalid.
2. Sort: The Arrays.sort(arr) method sorts the array elements in ascending order.
3. Find Second Smallest: It then iterates from the second element (arr[1]). The first element encountered that is *greater* than arr[0] is the second smallest distinct element.
4. Handle All Same Elements: If the loop completes without finding an element greater than arr[0], it means all elements are identical, and there's no distinct second smallest.

Approach 2: Two-Pass Iteration

This method avoids sorting the entire array, which can be more efficient for very large arrays where sorting might be overkill. It involves two separate passes through the array.

• Summary: First, it finds the smallest element. Then, in a second pass, it finds the smallest element among those that are greater than the first smallest.

// FindSecondSmallest_TwoPass
public class Main {
    public static int findSecondSmallestTwoPass(int[] arr) {
        if (arr == null || arr.length < 2) {
            System.out.println("Array must contain at least two elements.");
            return -1;
        }

        // Step 1: Find the smallest element
        int smallest = Integer.MAX_VALUE;
        for (int num : arr) {
            if (num < smallest) {
                smallest = num;
            }
        }

        // Step 2: Find the second smallest element
        // Initialize secondSmallest to MAX_VALUE to ensure any valid number will be smaller
        int secondSmallest = Integer.MAX_VALUE;
        for (int num : arr) {
            // If the current number is smaller than secondSmallest
            // AND it's not equal to the smallest element found in Step 1
            if (num < secondSmallest && num != smallest) {
                secondSmallest = num;
            }
        }

        // If secondSmallest is still Integer.MAX_VALUE, it means either
        // all elements are the same as 'smallest', or there was no distinct second smallest.
        if (secondSmallest == Integer.MAX_VALUE) {
            System.out.println("No distinct second smallest element found.");
            return -1;
        }

        return secondSmallest;
    }

    public static void main(String[] args) {
        int[] arr1 = {12, 5, 2, 10, 8, 2, 1};
        System.out.println("Original array: " + java.util.Arrays.toString(arr1));
        System.out.println("Second smallest element (Two Pass): " + findSecondSmallestTwoPass(arr1)); // Output: 5

        int[] arr2 = {7, 7, 3, 3, 5};
        System.out.println("Original array: " + java.util.Arrays.toString(arr2));
        System.out.println("Second smallest element (Two Pass): " + findSecondSmallestTwoPass(arr2)); // Output: 5

        int[] arr3 = {10, 10, 10, 10};
        System.out.println("Original array: " + java.util.Arrays.toString(arr3));
        System.out.println("Second smallest element (Two Pass): " + findSecondSmallestTwoPass(arr3)); // Output: -1

        int[] arr4 = {5};
        System.out.println("Original array: " + java.util.Arrays.toString(arr4));
        System.out.println("Second smallest element (Two Pass): " + findSecondSmallestTwoPass(arr4)); // Output: -1
    }
}

Run

• Sample Output:

  Original array: [12, 5, 2, 10, 8, 2, 1]
  Second smallest element (Two Pass): 5
  Original array: [7, 7, 3, 3, 5]
  Second smallest element (Two Pass): 5
  Original array: [10, 10, 10, 10]
  No distinct second smallest element found.
  Second smallest element (Two Pass): -1
  Original array: [5]
  Array must contain at least two elements.
  Second smallest element (Two Pass): -1

• Stepwise Explanation:

1. Input Validation: Similar to Approach 1, handles invalid array inputs.
2. First Pass (Find Smallest): Initializes smallest to Integer.MAX_VALUE and iterates through the array to find the absolute minimum value.
3. Second Pass (Find Second Smallest): Initializes secondSmallest to Integer.MAX_VALUE. It iterates through the array again. For each number, it checks if it's smaller than the current secondSmallest AND if it's *not equal* to the smallest found in the first pass. This ensures we get a distinct second smallest value.
4. Return Value: If secondSmallest remains Integer.MAX_VALUE, it implies no distinct second smallest element was found (e.g., all elements are the same).

Approach 3: Single-Pass Iteration

This is the most optimized approach for this problem, performing the task in a single traversal of the array.

• Summary: Initializes smallest and secondSmallest variables and updates them dynamically in a single loop as it iterates through the array.

// FindSecondSmallest_SinglePass
public class Main {
    public static int findSecondSmallestSinglePass(int[] arr) {
        if (arr == null || arr.length < 2) {
            System.out.println("Array must contain at least two elements.");
            return -1;
        }

        // Step 1: Initialize smallest and secondSmallest
        // We can't use arr[0] and arr[1] directly due to potential duplicates or order.
        // Initialize with MAX_VALUE to ensure any array element will be smaller.
        int smallest = Integer.MAX_VALUE;
        int secondSmallest = Integer.MAX_VALUE;

        // Step 2: Iterate through the array once
        for (int num : arr) {
            if (num < smallest) {
                // If current number is smaller than smallest,
                // the old smallest becomes the new secondSmallest,
                // and the current number becomes the new smallest.
                secondSmallest = smallest;
                smallest = num;
            } else if (num < secondSmallest && num != smallest) {
                // If current number is smaller than secondSmallest
                // but not equal to smallest, then it's the new secondSmallest.
                secondSmallest = num;
            }
        }

        // Step 3: Check if a distinct second smallest was found
        if (secondSmallest == Integer.MAX_VALUE) {
            System.out.println("No distinct second smallest element found.");
            return -1;
        }

        return secondSmallest;
    }

    public static void main(String[] args) {
        int[] arr1 = {12, 5, 2, 10, 8, 2, 1};
        System.out.println("Original array: " + java.util.Arrays.toString(arr1));
        System.out.println("Second smallest element (Single Pass): " + findSecondSmallestSinglePass(arr1)); // Output: 5

        int[] arr2 = {7, 7, 3, 3, 5};
        System.out.println("Original array: " + java.util.Arrays.toString(arr2));
        System.out.println("Second smallest element (Single Pass): " + findSecondSmallestSinglePass(arr2)); // Output: 5

        int[] arr3 = {10, 10, 10, 10};
        System.out.println("Original array: " + java.util.Arrays.toString(arr3));
        System.out.println("Second smallest element (Single Pass): " + findSecondSmallestSinglePass(arr3)); // Output: -1

        int[] arr4 = {5};
        System.out.println("Original array: " + java.util.Arrays.toString(arr4));
        System.out.println("Second smallest element (Single Pass): " + findSecondSmallestSinglePass(arr4)); // Output: -1
    }
}

Run

• Sample Output:

  Original array: [12, 5, 2, 10, 8, 2, 1]
  Second smallest element (Single Pass): 5
  Original array: [7, 7, 3, 3, 5]
  Second smallest element (Single Pass): 5
  Original array: [10, 10, 10, 10]
  No distinct second smallest element found.
  Second smallest element (Single Pass): -1
  Original array: [5]
  Array must contain at least two elements.
  Second smallest element (Single Pass): -1

• Stepwise Explanation:

1. Input Validation: Ensures the array is valid for processing.
2. Initialization: smallest and secondSmallest are both initialized to Integer.MAX_VALUE. This is a common technique to ensure that the first few elements of the array will correctly update these values.
3. Single Pass Logic:

• If num is less than smallest: This means we found a new absolute smallest. The old smallest value now becomes the secondSmallest, and num becomes the new smallest.
• Else if num is less than secondSmallest AND num is *not equal* to smallest: This means num is not the absolute smallest, but it is smaller than our current secondSmallest. So, num becomes the new secondSmallest. The num != smallest check is crucial to handle duplicate smallest values correctly.

1. Result Check: After the loop, if secondSmallest is still Integer.MAX_VALUE, it signifies that no distinct second smallest element was found (e.g., the array contains only one distinct value or all values are the same).

Conclusion

Finding the second smallest element in an array is a fundamental problem that highlights different algorithmic strategies. While sorting offers a straightforward solution, the single-pass iteration method provides a more efficient approach, especially for large datasets, by minimizing the number of array traversals. Each method effectively handles duplicate elements and edge cases such as arrays with insufficient elements.

Summary

• Problem: Identify the second smallest distinct element in an integer array.
• Edge Cases: Handle arrays with fewer than two elements or arrays where all elements are identical.
• Approach 1 (Sorting):
• Sorts the array using Arrays.sort().
• Iterates from the second element to find the first distinct value greater than the smallest.
• Complexity: O(N log N) due to sorting.
• Approach 2 (Two-Pass Iteration):
• First pass finds the absolute smallest element.
• Second pass finds the smallest element greater than the absolute smallest.
• Complexity: O(N) because of two linear passes.
• Approach 3 (Single-Pass Iteration):
• Initializes smallest and secondSmallest to Integer.MAX_VALUE.
• Traverses the array once, updating smallest and secondSmallest based on comparison logic.
• Efficiently handles distinct values and duplicates.
• Complexity: O(N) due to a single linear pass, making it the most optimal for time complexity among these methods.