Find the second largest and second smallest element in an array using C

Find the second largest and second smallest element in an array using C programming language.

Code:

#include <stdio.h>

void findSecondLargestAndSmallest(int arr[], int size, int *secondLargest, int *secondSmallest) {
if (size < 2) {
printf("Array size should be at least 2.\n");
return;
}

*secondLargest = *secondSmallest = arr[0];
int largest = arr[0], smallest = arr[0];

for (int i = 1; i < size; i++) {
if (arr[i] > largest) {
*secondLargest = largest;
largest = arr[i];
} else if (arr[i] > *secondLargest && arr[i] != largest) {
*secondLargest = arr[i];
}

if (arr[i] < smallest) {
*secondSmallest = smallest;
smallest = arr[i];
} else if (arr[i] < *secondSmallest && arr[i] != smallest) {
*secondSmallest = arr[i];
}
}
}

int main() {
int arr[] = {10, 5, 8, 3, 9, 4, 12, 7};
int size = sizeof(arr) / sizeof(arr[0]);

int secondLargest, secondSmallest;
findSecondLargestAndSmallest(arr, size, &secondLargest, &secondSmallest);

printf("Second Largest: %d\n", secondLargest);
printf("Second Smallest: %d\n", secondSmallest);

return 0;
}

Replace the arr array with your own set of numbers as needed. The findSecondLargestAndSmallest function takes an array, its size, and pointers to variables where it stores the second largest and second smallest elements. The main function demonstrates how to use this function and prints the results.

 

Explanation:

#include <stdio.h>

This line includes a standard library called stdio.h which provides functions for input and output, like printing text on the screen.

void findSecondLargestAndSmallest(int arr[], int size, int *secondLargest, int *secondSmallest) {

Here, we're defining a function named findSecondLargestAndSmallest. This function takes four inputs: an array arr containing numbers, an integer size indicating how many numbers are in the array, and two pointers named secondLargest and secondSmallest. Pointers are like references that allow us to change the values of variables outside the function.

if (size < 2) {
printf("Array size should be at least 2.\n");
return;
}

This checks if the size of the array is less than 2. If it is, the function prints a message saying that the array should have at least 2 elements, and then exits the function using return.

*secondLargest = *secondSmallest = arr[0];
int largest = arr[0], smallest = arr[0];

Here, we're initializing variables secondLargest and secondSmallest to the first element of the array arr. We're also creating two more variables, largest and smallest, which are also initialized to the first element of the array.

for (int i = 1; i < size; i++) {

This line starts a loop that will iterate over the array starting from the second element (index 1) and going up to the last element.

if (arr[i] > largest) {
*secondLargest = largest;
largest = arr[i];
} else if (arr[i] > *secondLargest && arr[i] != largest) {
*secondLargest = arr[i];
}

Inside the loop, we're checking if the current element arr[i] is greater than the current largest element largest. If it is, we're moving the value of largest to secondLargest and updating largest with the current element's value.

if (arr[i] < smallest) {
*secondSmallest = smallest;
smallest = arr[i];
} else if (arr[i] < *secondSmallest && arr[i] != smallest) {
*secondSmallest = arr[i];
}

Similarly, we're checking if the current element arr[i] is smaller than the current smallest element smallest. If it is, we're moving the value of smallest to secondSmallest and updating smallest with the current element's value.

}

This closes the loop.

}

This ends the findSecondLargestAndSmallest function.

int main() {

This is the beginning of the main function, which is the entry point of our program.

int arr[] = {10, 5, 8, 3, 9, 4, 12, 7};
int size = sizeof(arr) / sizeof(arr[0]);

Here, we're creating an array arr with some numbers and calculating the size of the array using the sizeof operator. This helps us determine how many elements are in the array.

int secondLargest, secondSmallest;
findSecondLargestAndSmallest(arr, size, &secondLargest, &secondSmallest);

We're declaring two variables, secondLargest and secondSmallest, and then we're calling the findSecondLargestAndSmallest function to find those values in the arr array.

printf("Second Largest: %d\n", secondLargest);
printf("Second Smallest: %d\n", secondSmallest);

Finally, we're printing out the second largest and second smallest values that were found using the function.

return 0;
}

This line ends the main function and indicates that the program has finished running. The value 0 is returned to indicate that the program ran successfully.

 

Algorithm:

1. Include Necessary Library

   • Include the standard input/output library (<stdio.h>) for using input and output functions.

2. Function to Find Second Largest and Smallest

   • Define a function named findSecondLargestAndSmallest that takes four arguments: an integer array arr[], an integer size representing the size of the array, and two integer pointers secondLargest and secondSmallest to store the results.

3. Check Array Size

   • Inside the function, check if the size of the array is less than 2.

   • If the size is less than 2, print a message indicating that the array should have at least 2 elements and exit the function.

4. Initialize Variables

   • Initialize two variables largest and smallest with the value of the first element in the array.

   • Initialize the pointers secondLargest and secondSmallest with the value of the first element in the array.

5. Loop through the Array

   • Start a loop from index 1 to size - 1 to iterate through the array.

   • For each element arr[i] in the array:

     • Compare arr[i] with largest:

       • If arr[i] is greater than largest, update secondLargest with the value of largest and update largest with the value of arr[i].

       • If arr[i] is not greater than largest but is greater than secondLargest and not equal to largest, update secondLargest with the value of arr[i].

     • Compare arr[i] with smallest:

       • If arr[i] is smaller than smallest, update secondSmallest with the value of smallest and update smallest with the value of arr[i].

       • If arr[i] is not smaller than smallest but is smaller than secondSmallest and not equal to smallest, update secondSmallest with the value of arr[i].

6. Return Results

   • After the loop, the secondLargest and secondSmallest pointers will contain the correct values of the second largest and second smallest elements in the array.

7. Main Function

   • Define the main function, the entry point of the program.

   • Declare an integer array arr with some numbers.

   • Calculate the size of the array using sizeof(arr) / sizeof(arr[0]).

   • Declare integer variables secondLargest and secondSmallest.

   • Call the findSecondLargestAndSmallest function with the array, size, and pointers to secondLargest and secondSmallest.

   • Print the values of secondLargest and secondSmallest using printf.

8. Program Termination

   • Return 0 from the main function to indicate successful program execution.

This algorithm explains how the code works step by step to find the second largest and second smallest elements in an array.

 

Time Complexity:

for (int i = 1; i < size; i++) {
// ...
}

The primary loop in the code iterates through the array once, starting from the second element (index 1) up to the last element (index size - 1). This loop is responsible for finding the second largest and second smallest elements. Therefore, the time complexity of the loop is O(n - 1), which simplifies to O(n), where 'n' is the size of the array.

Since the rest of the operations in the loop involve simple comparisons and assignments (constant-time operations), their contribution to the overall time complexity is negligible compared to the loop itself.

Hence, the overall time complexity of the provided code is O(n), where 'n' is the size of the array.

 

Space Complexity:

1. Input Data:

   • The input array arr takes up space proportional to the size of the array 'n'. Therefore, the space complexity for the input data is O(n).

2. Variables:

   • The variables i, largest, smallest, secondLargest, and secondSmallest are used to store indices and values during the calculations. These variables take up constant space regardless of the size of the input array. Hence, their space complexity is O(1).

3. Function Call Stack:

   • The main function calls the findSecondLargestAndSmallest function. The space used by the function call stack is determined by the depth of function calls and the variables stored in each call. In this case, the function doesn't recursively call itself, and the number of variables stored in the function call stack is constant, regardless of the input size. Therefore, the space complexity due to the function call stack is O(1).

Overall, the dominant factor in the space complexity is the input array arr, which takes O(n) space. The other variables and memory usage are constant and don't depend on the input size. Thus, the space complexity of the above code is O(n).

 

Thank You