Find the smallest and second smallest element in an array

find smallest and second smallest number in c

We can find the smallest and second smallest element of an integers array using the c language. This question is also important and asks by the interviewer in an interview.

Let’s take an example, suppose there are an integer array iaData of 5 integers.

int iaData[5] = {3, 5, 123, 6, 1};
Here the smallest number is 1 and the second smallest number is 3.



A simple way to find the smallest and second smallest element is that sort the array in ascending order and pick its first and second elements. Its first element will be the smallest number and the second number will be the second smallest number. The time complexity of this solution is O(n log n).

// C program to find smallest and second smallest elements
#include <stdio.h>

#define SIZE_ARRAY(x) sizeof(x)/sizeof(x[0]); // Size of array


int main()
{
    int iaData[5] = {3,5,123,6,1};
    int ArraySize = SIZE_ARRAY(iaData);
    int iLoop1 =0, iLoop2 =0;

    for(iLoop1 = 0; iLoop1 < ArraySize; iLoop1++)
    {
        for(iLoop2 = iLoop1+1; iLoop2 < ArraySize ; iLoop2++)
        {
            if(iaData[iLoop1] > iaData[iLoop2])
            {
                iaData[iLoop1] ^= iaData[iLoop2];
                iaData[iLoop2] ^= iaData[iLoop1];
                iaData[iLoop1] ^= iaData[iLoop2];
            }
        }
    }

    // Sorted array
    printf("\n\nSorted Array: ");
    for(iLoop1 = 0; iLoop1 < ArraySize; iLoop1++)
        printf("%d ",iaData[iLoop1]);

    // First element of sorted array
    printf("\n\nSmallest element = %d\n",iaData[0]);

    //Second element of sorted array
    printf("\n\nSecond smallest element = %d\n\n\n",iaData[1]);

    return 0;
}

 

OutPut:

 

 

 




The above method is not better because it scans the array twice. There is also another way to find the smallest and second smallest element in a single scan of the array. The time complexity of this solution is O(n).

Here is an algorithm to find the two smallest and second smallest number in one traversal.

Algorithm to find the smallest and second smallest element:

  • Creates two-variable, In this code, I have created iFirstSmallest and iSecondSmallest.
  • Initialize both variables as INT_MAX
    iFirstSmallest = INT_MAX
    iSecondSmallest = INT_MAX
  • Loop through all the elements and perform the below task
    1). If the current element is smaller than iFirstSmallest, then update iFirstSmallest and iSecondSmallest.
    2). Else if the current element is smaller than iSecondSmallest then update iSecondSmallest.

 

#include <stdio.h>
#include <limits.h> /* For INT_MAX */


#define SIZE_ARRAY(x) sizeof(x)/sizeof(x[0]); //Element in array

void FindTwoSmallestNumber(int *piListOfData, int numbElement)
{
    int iLoop1= 0;
    int iFirstSmallest = INT_MAX;
    int iSecondSmallest = INT_MAX;

    while(iLoop1 < numbElement)
    {
        if(piListOfData[iLoop1] < iFirstSmallest)
        {
            iSecondSmallest = iFirstSmallest;
            iFirstSmallest  = piListOfData[iLoop1];

        }
        else if((piListOfData[iLoop1] < iSecondSmallest) && (piListOfData[iLoop1] !=iFirstSmallest ))
        {
            iSecondSmallest = piListOfData[iLoop1];
        }
        iLoop1++;
    }

    printf("First Smallest Numbers = %d\nSecond Smallest Number = %d\n ",iFirstSmallest,iSecondSmallest);

}


int main()
{
    int iaData[5] = {3,5,123,6,1};
    int numbElement = SIZE_ARRAY(iaData);

    FindTwoSmallestNumber(iaData,numbElement);

    return 0;
}

OutPut:

 

 

 

Recommended Articles for you:

 



Leave a Reply

Your email address will not be published. Required fields are marked *