Find Second Smallest And Second Largest Element In An Array In C

This article will guide you through various methods to find the second smallest and second largest elements in an integer array using the C programming language. You will learn different approaches, from simple sorting to more efficient single-pass iterations, understanding their logic and implementation.

Problem Statement

Identifying the second smallest and second largest elements in an array is a common programming challenge. This involves scanning an array of numbers and determining which element ranks second when ordered, rather than just the absolute minimum or maximum. The key is to account for duplicates and edge cases, ensuring the correct distinct values are identified.

Example

Consider the integer array [12, 35, 1, 10, 34, 1].

• The smallest element is 1.
• The second smallest element is 10.
• The largest element is 35.
• The second largest element is 34.

Background & Knowledge Prerequisites

To understand this article, you should have a basic understanding of:

• C Arrays: How to declare, initialize, and access elements of an array.
• Loops (for, while): Iterating through array elements.
• Conditional Statements (if-else): Making decisions based on element values.
• Functions in C: Defining and calling functions.
• Basic sorting concepts (optional but helpful): Understanding how elements are ordered.

Use Cases or Case Studies

Finding the second smallest or largest element can be useful in several scenarios:

• Statistical Analysis: Identifying outliers or critical thresholds in datasets, where the absolute min/max might be an anomaly.
• Competitive Ranking: In a competition, determining the silver medalist's score or the second-best performance.
• Resource Allocation: When optimizing resource distribution, excluding the top/bottom performers to ensure balanced allocation.
• Data Validation: Ensuring data falls within a certain range, excluding extreme values.
• System Monitoring: Alerting if a system metric (e.g., CPU usage) exceeds a threshold that is not the absolute peak but still concerning.

Solution Approaches

Here are three distinct methods to find the second smallest and second largest elements in an array.

Approach 1: Sorting the Array

This approach involves sorting the array first and then picking the elements at the second and second-to-last positions. This is straightforward but might not be the most efficient for large arrays.

• One-line summary: Sort the array and access elements at indices 1 and n-2 after removing duplicates (or handling them carefully).

// Find Second Smallest and Largest by Sorting
#include <stdio.h>
#include <stdlib.h> // For qsort

// Comparison function for qsort (ascending order)
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

void findSecondMinMaxSorted(int arr[], int n) {
    if (n < 2) {
        printf("Array must have at least two elements.\\n");
        return;
    }

    // Sort the array in ascending order
    qsort(arr, n, sizeof(int), compare);

    int secondSmallest = -1;
    int secondLargest = -1;

    // Find second smallest (skipping duplicates of the smallest)
    int i;
    for (i = 1; i < n; i++) {
        if (arr[i] > arr[0]) { // arr[0] is the smallest
            secondSmallest = arr[i];
            break;
        }
    }

    // Find second largest (skipping duplicates of the largest)
    for (i = n - 2; i >= 0; i--) {
        if (arr[i] < arr[n - 1]) { // arr[n-1] is the largest
            secondLargest = arr[i];
            break;
        }
    }

    if (secondSmallest != -1) {
        printf("Second smallest element (sorted approach): %d\\n", secondSmallest);
    } else {
        printf("Second smallest element not found (all elements might be same).\\n");
    }

    if (secondLargest != -1) {
        printf("Second largest element (sorted approach): %d\\n", secondLargest);
    } else {
        printf("Second largest element not found (all elements might be same).\\n");
    }
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    findSecondMinMaxSorted(arr, n);

    int arr2[] = {5, 5, 5, 5};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("\\nOriginal array 2: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\\n");
    findSecondMinMaxSorted(arr2, n2);

    int arr3[] = {7};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    printf("\\nOriginal array 3: ");
    for (int i = 0; i < n3; i++) {
        printf("%d ", arr3[i]);
    }
    printf("\\n");
    findSecondMinMaxSorted(arr3, n3);

    return 0;
}

Run

• Sample Output:

Original array: 12 35 1 10 34 1 
Second smallest element (sorted approach): 10
Second largest element (sorted approach): 34

Original array 2: 5 5 5 5 
Second smallest element not found (all elements might be same).
Second largest element not found (all elements might be same).

Original array 3: 7 
Array must have at least two elements.

• Stepwise explanation:

1. Handle small arrays: Check if the array has fewer than two elements; if so, a second smallest/largest doesn't exist.
2. Sort: Use qsort from stdlib.h to sort the array in ascending order.
3. Find second smallest: Iterate from the second element (arr[1]). The first element encountered that is greater than arr[0] (the smallest) is the second smallest. This correctly handles duplicates of the smallest element.
4. Find second largest: Iterate backwards from arr[n-2]. The first element encountered that is smaller than arr[n-1] (the largest) is the second largest. This correctly handles duplicates of the largest element.
5. Output: Print the results, or a message if a distinct second smallest/largest wasn't found (e.g., all elements are the same).

Approach 2: Two-Pass Iteration

This method involves iterating through the array twice. The first pass finds the smallest and largest elements. The second pass then finds the second smallest and second largest by comparing elements against the first pass's results.

• One-line summary: Find the absolute min/max in one pass, then find the second min/max in a second pass, ensuring distinct values.

// Find Second Smallest and Largest with Two Passes
#include <stdio.h>
#include <limits.h> // For INT_MAX and INT_MIN

void findSecondMinMaxTwoPass(int arr[], int n) {
    if (n < 2) {
        printf("Array must have at least two elements.\\n");
        return;
    }

    int smallest = INT_MAX, largest = INT_MIN;
    int secondSmallest = INT_MAX, secondLargest = INT_MIN;

    // Pass 1: Find the smallest and largest elements
    for (int i = 0; i < n; i++) {
        if (arr[i] < smallest) {
            smallest = arr[i];
        }
        if (arr[i] > largest) {
            largest = arr[i];
        }
    }

    // Pass 2: Find the second smallest and second largest
    for (int i = 0; i < n; i++) {
        if (arr[i] < secondSmallest && arr[i] != smallest) {
            secondSmallest = arr[i];
        }
        if (arr[i] > secondLargest && arr[i] != largest) {
            secondLargest = arr[i];
        }
    }

    if (secondSmallest != INT_MAX) {
        printf("Second smallest element (two-pass approach): %d\\n", secondSmallest);
    } else {
        printf("Second smallest element not found (all elements might be same or array too small).\\n");
    }

    if (secondLargest != INT_MIN) {
        printf("Second largest element (two-pass approach): %d\\n", secondLargest);
    } else {
        printf("Second largest element not found (all elements might be same or array too small).\\n");
    }
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    findSecondMinMaxTwoPass(arr, n);

    int arr2[] = {5, 5, 5, 5};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("\\nOriginal array 2: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\\n");
    findSecondMinMaxTwoPass(arr2, n2);

    int arr3[] = {7};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    printf("\\nOriginal array 3: ");
    for (int i = 0; i < n3; i++) {
        printf("%d ", arr3[i]);
    }
    printf("\\n");
    findSecondMinMaxTwoPass(arr3, n3);

    return 0;
}

Run

• Sample Output:

Original array: 12 35 1 10 34 1 
Second smallest element (two-pass approach): 10
Second largest element (two-pass approach): 34

Original array 2: 5 5 5 5 
Second smallest element not found (all elements might be same or array too small).
Second largest element not found (all elements might be same or array too small).

Original array 3: 7 
Array must have at least two elements.

• Stepwise explanation:

1. Handle small arrays: Similar to the previous approach, check if the array has fewer than two elements.
2. Initialize: Set smallest to INT_MAX and largest to INT_MIN. Initialize secondSmallest and secondLargest similarly.
3. First Pass (Find min/max): Iterate through the array to find the true smallest and largest elements.
4. Second Pass (Find second min/max): Iterate through the array again.
   • If an element arr[i] is smaller than secondSmallest AND arr[i] is not equal to smallest, update secondSmallest.

1. Output: Print the results. If secondSmallest is still INT_MAX or secondLargest is still INT_MIN, it means no distinct second element was found.

Approach 3: Single-Pass Iteration (Most Efficient)

This is the most optimized method, requiring only a single pass through the array to identify all four values (smallest, second smallest, largest, second largest).

• One-line summary: Maintain four variables (smallest, secondSmallest, largest, secondLargest) and update them dynamically in a single pass.

// Find Second Smallest and Largest in Single Pass
#include <stdio.h>
#include <limits.h> // For INT_MAX and INT_MIN

void findSecondMinMaxSinglePass(int arr[], int n) {
    if (n < 2) {
        printf("Array must have at least two elements.\\n");
        return;
    }

    // Initialize with extreme values
    int smallest = INT_MAX, secondSmallest = INT_MAX;
    int largest = INT_MIN, secondLargest = INT_MIN;

    for (int i = 0; i < n; i++) {
        // Logic for smallest and second smallest
        if (arr[i] < smallest) {
            secondSmallest = smallest; // Current smallest becomes second smallest
            smallest = arr[i];         // Current element becomes new smallest
        } else if (arr[i] < secondSmallest && arr[i] != smallest) {
            secondSmallest = arr[i]; // Current element is between smallest and secondSmallest
        }

        // Logic for largest and second largest
        if (arr[i] > largest) {
            secondLargest = largest; // Current largest becomes second largest
            largest = arr[i];        // Current element becomes new largest
        } else if (arr[i] > secondLargest && arr[i] != largest) {
            secondLargest = arr[i]; // Current element is between largest and secondLargest
        }
    }

    if (secondSmallest != INT_MAX) {
        printf("Second smallest element (single-pass approach): %d\\n", secondSmallest);
    } else {
        printf("Second smallest element not found (all elements might be same or array too small).\\n");
    }

    if (secondLargest != INT_MIN) {
        printf("Second largest element (single-pass approach): %d\\n", secondLargest);
    } else {
        printf("Second largest element not found (all elements might be same or array too small).\\n");
    }
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    findSecondMinMaxSinglePass(arr, n);

    int arr2[] = {5, 5, 5, 5};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("\\nOriginal array 2: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\\n");
    findSecondMinMaxSinglePass(arr2, n2);
    
    int arr4[] = {10, 20, 30};
    int n4 = sizeof(arr4) / sizeof(arr4[0]);
    printf("\\nOriginal array 4: ");
    for (int i = 0; i < n4; i++) {
        printf("%d ", arr4[i]);
    }
    printf("\\n");
    findSecondMinMaxSinglePass(arr4, n4);

    int arr3[] = {7};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    printf("\\nOriginal array 3: ");
    for (int i = 0; i < n3; i++) {
        printf("%d ", arr3[i]);
    }
    printf("\\n");
    findSecondMinMaxSinglePass(arr3, n3);

    return 0;
}

Run

• Sample Output:

Original array: 12 35 1 10 34 1 
Second smallest element (single-pass approach): 10
Second largest element (single-pass approach): 34

Original array 2: 5 5 5 5 
Second smallest element not found (all elements might be same or array too small).
Second largest element not found (all elements might be same or array too small).

Original array 4: 10 20 30 
Second smallest element (single-pass approach): 20
Second largest element (single-pass approach): 20

Original array 3: 7 
Array must have at least two elements.

• Stepwise explanation:

1. Handle small arrays: Check if the array has fewer than two elements.
2. Initialize: Initialize smallest, secondSmallest to INT_MAX, and largest, secondLargest to INT_MIN. This ensures any array element will be properly compared.
3. Iterate: Loop through each element arr[i] of the array.
4. Update smallest/secondSmallest:
   • If arr[i] is smaller than smallest, it's the new smallest. The old smallest becomes secondSmallest.

1. Update largest/secondLargest:
   • If arr[i] is larger than largest, it's the new largest. The old largest becomes secondLargest.

1. Output: Print the results, or a message if secondSmallest or secondLargest still hold their initial INT_MAX/INT_MIN values, indicating no distinct second element was found.

Conclusion

Finding the second smallest and second largest elements in an array can be approached in several ways, each with its own trade-offs. While sorting provides a conceptually simple method, it is generally less efficient for large arrays due to the O(N log N) complexity of sorting algorithms. The two-pass iteration offers better efficiency at O(N), and the single-pass iteration provides the most optimal solution with O(N) time complexity and minimal constant space complexity. The choice of method often depends on the array size and performance requirements of the application.

Summary

• Problem: Find the second smallest and second largest distinct elements in an array.
• Sorting Approach:
• Sort the array (e.g., using qsort).
• Find the second smallest by iterating from arr[1] to find the first element greater than arr[0].
• Find the second largest by iterating backwards from arr[n-2] to find the first element smaller than arr[n-1].
• Complexity: O(N log N).
• Two-Pass Iteration Approach:
• Pass 1: Identify the absolute smallest and largest elements.
• Pass 2: Iterate again to find the secondSmallest (an element smaller than secondSmallest and not equal to smallest) and secondLargest (an element larger than secondLargest and not equal to largest).
• Complexity: O(N).
• Single-Pass Iteration Approach:
• Initialize smallest, secondSmallest to INT_MAX and largest, secondLargest to INT_MIN.
• Iterate once, updating all four variables based on comparisons with the current array element.
• This is the most efficient solution.
• Complexity: O(N).
• Edge Cases: Always handle arrays with fewer than two elements, or arrays where all elements are identical.
• Headers: Include for input/output and for INT_MAX/INT_MIN. For sorting, include .