Second Smallest Number in Array in C/C++, Java and Python

In an earlier tutorial, we have seen how to find the smallest or largest number from the integer array. In this tutorial, we are going to find the second smallest number in an array in a single iteration.

Input:

  • integer array

Output:

  • Print second smallest integer in given array.

We can easily find the second smallest number by traversing the array twice. In first traversing, find the first smallest number. And in second traversing find the second smallest number.

Finding second smallest number in array with single iteration is bit tricky. Here is the algorithm to solve this problem.

Algorithm

  • Compare the first two elements from the array.
    • Initialize the small_first with the smallest number.
    • Initialize the small_second with the smallest number.
  • Loop over internet array from 3rd number.
    • If the current number is smaller than small_first
      • assign small_first to small_second
      • assign a current number to small_first
  • Print small_second.

If you understand the logic from above algorithm, you can solve the problem in any programming languages. Let’s implement this algorithm in different programming languages.

Note: By changing some conditional statements, you can also implement the program to find the second largest number in the given array. That is just another story. Let’s stick with original problem first.

C/C++ Program

Prerequisites:

C/C++ Code:

#include <stdio.h>
  
int main() {
    //initialize array
    int arr[7] = {34, 62, 56, 13, 7, 9, 17};
    int i=0;

    int small_first = arr[0];
    int small_second = arr[0];
 
    //initializ first and second smallest number
    if(arr[0] > arr[1]) {
        small_first = arr[1];
        small_second = arr[0];
    }
    else {
        small_first = arr[0];
        small_second = arr[1];
    }

    for(i = 2; i < 7; i++) {
 
         //compare smallest number with current number
        if(arr[i]<=small_first) {
            small_second = small_first;
            small_first = arr[i];
        }
        else if(arr[i]<small_second){
            small_second = arr[i];
        }
    }
  
    //print second smallest number from array
    printf("Second smallest number in array is %d.", small_second);
 
    return 0;
}

Output:

Second smallest number in array is 9.

Java Program

Prerequisites:

Java Code:

public class Smallest_Largest_Element_Array {  
    public static void main(String[] args) {  
   
        // initialize the array  
        int [] arr = new int [] {67, 83, 8, 71, 29, 3, 48};  
        
        int small_first = arr[0];
        int small_second = arr[0];
 
        //initializ first and second smallest number
        if(arr[0] > arr[1]) {
            small_first = arr[1];
            small_second = arr[0];
        }
        else {
            small_first = arr[0];
            small_second = arr[1];
        }
 
        //traverse all elements in the array  
        for (int i = 2; i < arr.length; i++) {  
 
             //compare smallest number with current number
            if(arr[i]<=small_first) {
                small_second = small_first;
                small_first = arr[i];
            }
            else if(arr[i]<small_second){
                small_second = arr[i];
            }
        }
 
        //print smallest number from the array
        System.out.println("Second smallest element in the array: " + small_second);

    }  
}  

Output:

Second smallest element in the array: 8

Python Program

Prerequisites:

Python Code:

#initialize the Python list
int_arr = [45, 56, 83, 4, 11, 28, 36]
 
small_first = int_arr[0]
small_second = int_arr[0]
 
#initializ first and second smallest number
if int_arr[0] > int_arr[1]:
    small_first = int_arr[1]
    small_second = int_arr[0]
else:
    small_first = int_arr[0]
    small_second = int_arr[1]
 
#loop over all the number in the list
for num in int_arr[2:]:

    #compare smallest number with current number
    if num<=small_first:
        small_second = small_first
        small_first = num
    elif num<small_second:
        small_second = num

print(f"Second smallest number in the Python list: {small_second}")

Output:

Second smallest number in the Python list: 11

Complexity

To find the second smallest number from the array, we are traversing the array only once. Each element in the array is visited once. So the time complexity of this algorithm is O(n). Here, n is the size of the array.

We are using extra space to store the first and second smallest number but it is constant (irrespective of the size of the array.)

What’s Next?

Write a program to find the second largest number in array and share with me in the comment.

Leave a Reply