Find the Second Smallest Element in an Array in C

To find the second smallest element in an array in C, we can iterate through the array and keep track of both the smallest and second smallest values. This ensures that we efficiently determine the second smallest element in a single pass or with minimal additional operations.

Examples to Find the Second Smallest Element

1. Using a Single Pass with Two Variables to Find the Second Smallest Element

In this example, we iterate through the array once, maintaining two variables: smallest and second_smallest. We update these variables as we find smaller values.

main.c

</>
Copy
#include <stdio.h>
#include <limits.h>

int main() {
    int arr[] = {12, 3, 5, 2, 15, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    int smallest = INT_MAX, second_smallest = INT_MAX;

    // Find second smallest element
    for (int i = 0; i < size; i++) {
        if (arr[i] < smallest) {
            second_smallest = smallest;
            smallest = arr[i];
        } else if (arr[i] > smallest && arr[i] < second_smallest) {
            second_smallest = arr[i];
        }
    }

    printf("Second smallest element: %d\n", second_smallest);
    return 0;
}

Explanation:

  1. We initialize two variables: smallest and second_smallest with INT_MAX (a very large value).
  2. We iterate through the array using a for loop.
  3. If an element is smaller than smallest, we update second_smallest with the old value of smallest and then update smallest.
  4. If an element is greater than smallest but smaller than second_smallest, we update second_smallest.
  5. At the end, second_smallest holds the second smallest element.

Output:

Second smallest element: 3

2. Sorting the Array First to Find the Second Smallest Element

In this example, we first sort the array in ascending order and then find the second smallest element by checking the second unique element.

main.c

</>
Copy
#include <stdio.h>

void sortArray(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {8, 1, 4, 1, 6, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    // Sort the array
    sortArray(arr, size);

    // Find the second smallest unique element
    int smallest = arr[0], second_smallest = -1;
    for (int i = 1; i < size; i++) {
        if (arr[i] > smallest) {
            second_smallest = arr[i];
            break;
        }
    }

    printf("Second smallest element: %d\n", second_smallest);
    return 0;
}

Explanation:

  1. We define a function sortArray() that sorts the array using Bubble Sort.
  2. In main(), we call sortArray() to sort the array in ascending order.
  3. After sorting, the smallest element is at arr[0].
  4. We iterate through the sorted array to find the first element larger than smallest, which is the second smallest.
  5. We print the second smallest element.

Output:

Second smallest element: 4

Conclusion

We explored two different approaches to finding the second smallest element in an array:

  1. Using a Single Pass: Efficiently finds the second smallest element in one iteration.
  2. Sorting the Array First: Uses sorting to simplify finding the second smallest unique element.

The first approach is more efficient with a time complexity of O(n), whereas the second approach has a time complexity of O(n log n) due to sorting.