Second Smallest And Second Largest Element In An Array In C

Finding the second smallest and second largest elements in an array is a common problem in programming that tests your understanding of array manipulation and sorting algorithms. In this article, you will learn how to efficiently identify these specific elements within a C array.

Problem Statement

Identifying the second smallest and second largest elements in an array is crucial for tasks like outlier detection, ranking, or understanding data distribution beyond just the absolute minimum and maximum. For instance, in performance analysis, you might want to exclude the best and worst performers to get a more typical range. The challenge lies in doing this efficiently, especially with large datasets, and correctly handling edge cases like duplicate values or small array sizes.

Example

Consider an array of integers: [12, 34, 1, 56, 16, 70, 9]

• Expected Second Smallest Element: 9
• Expected Second Largest Element: 56

Background & Knowledge Prerequisites

To follow along with the solutions, a basic understanding of C programming concepts is essential:

• Arrays: Declaring, initializing, and accessing elements.
• Loops: for loops for iterating through arrays.
• Conditional Statements: if-else statements for comparison logic.
• Functions: Defining and calling functions (optional, but good practice for modularity).
• Header Files: Including standard libraries like stdio.h for input/output and limits.h for INT_MAX/INT_MIN.

Use Cases or Case Studies

This problem has practical applications across various domains:

• Statistical Analysis: In some statistical methods, the highest and lowest values might be considered outliers and removed. Finding the second highest/lowest helps establish a trimmed range for analysis.
• Performance Benchmarking: When evaluating the performance of multiple systems or algorithms, excluding the absolute best and worst results can provide a more stable and representative average or range.
• Ranking Systems: In competitive scenarios, if there's a tie for first place, identifying the "second" best helps in further differentiation or prize distribution.
• Sensor Data Filtering: Removing extreme readings (noise) from sensor data often involves discarding the highest and lowest values, making the second highest/lowest relevant for the effective data range.
• Financial Data Analysis: Identifying the second highest or lowest stock price within a period can be part of strategies that look for consistent, but not necessarily peak, performance or dips.

Solution Approaches

There are several ways to tackle this problem, ranging from simple but less efficient to more optimized methods.

Approach 1: Sorting the Array

This is the most intuitive method. Sort the array, and then the second smallest and second largest elements will be at specific indices (assuming the array has at least 3 elements).

• One-line summary: Sort the array in ascending order and pick elements from the second and second-to-last positions.

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

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

int main() {
    // Step 1: Define an array and its size
    int arr[] = {12, 34, 1, 56, 16, 70, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Step 2: Handle edge cases for array size
    if (n < 2) {
        printf("Array must have at least two elements.\\n");
        return 1;
    }
    if (n == 2) {
        printf("Array has only two elements. Smallest: %d, Largest: %d\\n", arr[0], arr[1]);
        printf("Second smallest: %d, Second largest: %d\\n", arr[0], arr[1]);
        return 0;
    }

    // Step 3: Sort the array
    qsort(arr, n, sizeof(int), compare);

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

    // Step 4: Extract the second smallest and second largest
    // After sorting, the second smallest is at index 1.
    // The second largest is at index n-2.
    printf("Second smallest element: %d\\n", arr[1]);
    printf("Second largest element: %d\\n", arr[n - 2]);

    return 0;
}

Run

• Sample Output:

  Original array: 12 34 1 56 16 70 9 
  Sorted array: 1 9 12 16 34 56 70 
  Second smallest element: 9
  Second largest element: 56

• Stepwise Explanation:

1. Initialize an integer array.
2. Check if the array size is less than 2. If so, there's no second smallest/largest. Handle the case for size 2 where the elements themselves are both smallest/largest and "second" smallest/largest.
3. Use qsort (from stdlib.h) to sort the array in ascending order. qsort requires a custom comparison function.
4. Once sorted, the element at index 1 is the second smallest.
5. The element at index n-2 is the second largest (where n is the array size).

Approach 2: Single Traversal (Optimal)

This method involves iterating through the array only once, keeping track of the two smallest and two largest elements found so far. This is generally more efficient for larger arrays as it avoids the O(N log N) complexity of sorting.

• One-line summary: Traverse the array once, maintaining variables for the smallest, second smallest, largest, and second largest elements.

// Find Second Smallest and Largest (Single Traversal)
#include <stdio.h>
#include <limits.h> // For INT_MAX and INT_MIN

int main() {
    // Step 1: Define an array and its size
    int arr[] = {12, 34, 1, 56, 16, 70, 9, 34}; // Added a duplicate for testing
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Step 2: Handle edge cases for array size
    if (n < 2) {
        printf("Array must have at least two elements.\\n");
        return 1;
    }

    // Step 3: Initialize variables for smallest, second smallest, largest, and second largest
    // Use INT_MAX for smallest/second smallest and INT_MIN for largest/second largest
    // to ensure any array element is smaller/larger than initial values.
    int min1 = INT_MAX, min2 = INT_MAX;
    int max1 = INT_MIN, max2 = INT_MIN;

    // Step 4: Traverse the array
    for (int i = 0; i < n; i++) {
        // Logic for smallest and second smallest
        if (arr[i] <= min1) {
            // If current element is smaller than or equal to min1, it becomes the new min1.
            // The old min1 becomes min2.
            if (arr[i] < min1) { // Only update min2 if arr[i] is strictly smaller than min1
                min2 = min1;
            }
            min1 = arr[i];
        } else if (arr[i] < min2) {
            // If current element is between min1 and min2, it becomes the new min2.
            min2 = arr[i];
        }

        // Logic for largest and second largest
        if (arr[i] >= max1) {
            // If current element is greater than or equal to max1, it becomes the new max1.
            // The old max1 becomes max2.
            if (arr[i] > max1) { // Only update max2 if arr[i] is strictly greater than max1
                max2 = max1;
            }
            max1 = arr[i];
        } else if (arr[i] > max2) {
            // If current element is between max1 and max2, it becomes the new max2.
            max2 = arr[i];
        }
    }

    // Step 5: Check if second smallest/largest were actually found (in case of all duplicates)
    if (min2 == INT_MAX || max2 == INT_MIN) {
        printf("Could not find distinct second smallest or largest element (e.g., all elements are the same or array size is too small).\\n");
        if (n >= 2 && min1 == max1) { // all elements are same
            printf("All elements are %d. Second smallest: %d, Second largest: %d\\n", min1, min1, min1);
        } else if (n == 2 && min1 != max1) { // only two distinct elements
            printf("Array has two distinct elements. Smallest: %d, Largest: %d\\n", min1, max1);
            printf("Second smallest: %d, Second largest: %d\\n", max1, min1); // The "other" element
        }
    } else {
        printf("Second smallest element: %d\\n", min2);
        printf("Second largest element: %d\\n", max2);
    }

    return 0;
}

Run

• Sample Output:

  Original array: 12 34 1 56 16 70 9 34 
  Second smallest element: 9
  Second largest element: 56

*(Note: If the array were [7, 7, 7], the output would be All elements are 7. Second smallest: 7, Second largest: 7)*

• Stepwise Explanation:

1. Initialize min1, min2 to INT_MAX and max1, max2 to INT_MIN. min1 will store the smallest, min2 the second smallest. max1 the largest, max2 the second largest.
2. Iterate through each element (arr[i]) of the array.
3. For smallest/second smallest:
   • If arr[i] is less than or equal to min1: This means arr[i] is either the new smallest or a duplicate of the current smallest. If it's strictly smaller (arr[i] < min1), the old min1 becomes min2, and arr[i] becomes min1. If arr[i] == min1, only min1 is updated, min2 remains unchanged (handling duplicates).

Else if arr[i] is less than min2 (and not equal to min1 because that case is handled above): arr[i] becomes the new min2.

1. For largest/second largest:
   • If arr[i] is greater than or equal to max1: Similar logic as for min1, but for maximums. If arr[i] > max1, the old max1 becomes max2, and arr[i] becomes max1.

Else if arr[i] is greater than max2 (and not equal to max1): arr[i] becomes the new max2.

1. After the loop, min2 and max2 hold the desired values. Additional checks are included to gracefully handle arrays where distinct second smallest/largest elements don't exist (e.g., [5,5,5], or arrays with only two elements).

Conclusion

Finding the second smallest and second largest elements in an array can be approached using sorting or a single traversal. While sorting provides a straightforward solution, the single-traversal method offers optimal time complexity (O(N)), making it more suitable for performance-critical applications or very large datasets. Choosing the right approach depends on the array size, performance requirements, and whether the simplicity of sorting outweighs the efficiency of a single pass.

Summary

• Problem: Find the second smallest and second largest elements in an array.
• Approach 1 (Sorting): Sort the array (e.g., using qsort), then access elements at index 1 (second smallest) and n-2 (second largest).
• Pros: Simple to implement and understand.
• Cons: Time complexity is O(N log N) due to sorting.
• Approach 2 (Single Traversal): Iterate through the array once, keeping track of the two smallest (min1, min2) and two largest (max1, max2) elements encountered.
• Pros: Highly efficient with O(N) time complexity.
• Cons: Requires careful handling of initialization and comparison logic.
• Edge Cases: Always consider arrays with fewer than two or three elements, and arrays containing duplicate values.