c++arraystime-complexityminimum

finding the second minimum


I want to find the second minimum in a array list.Here's my code.Is there a better way to do it?

int main(){
    int a[5]={7,5,45,89,12};
    int smallest=a[0];
    int index;
    for(int i=0;i<5;i++){
        if(a[i]<smallest){
            smallest=a[i];
            index=i;
        }
    }

    smallest=a[0];
    for(int i=0;i<5;i++){
        cout<<i;
        if((a[i]<smallest )&& (i!=index)){
            smallest=a[i];
        }
    }
    cout<<"second smallest value is: "<<smallest;  

This code runs in O(n) time? For the first loop it takes n steps, and for the other for loop also it takes n steps.Therefore altogether it takes O(n) time complexity .
Is this right?Can someone correct me if I am wrong please


Solution

  • Yes, it is O(n) but there's really no need to run through the list twice.

    You can do it once by storing both the smallest and second smallest values.

    For example, consider the following pseudo-code:

    smallest = a[0]
    second = a[1]
    if second < smallest:
        swap second with smallest
    for each index 2 thru a.size - 1 inclusive:
        if a[index] < smallest:
            second = smallest
            smallest = a[index]
        else:
            if a[index] < second:
                second = a[index]
    

    This is also O(n) but it only goes through the list once, rather than twice. At the end, second holds the second highest value.

    Just keep in mind that the second highest value in the list {1, 1, 2} is 1. If you want to treat duplicates differently to that, it's a slight modification.


    Implementing that in Python with a sample as a proof of concept, shows the result:

    a = [1,45,2,96,4,35]
    smallest = a[0]
    second = a[1]
    if second < smallest:
        smallest, second = second, smallest
    for index in range (2, len(a)):
        if a[index] < smallest:
            second = smallest
            smallest = a[index]
        else:
            if a[index] < second:
                second = a[index]
    print smallest
    print second
    

    The output of that is:

    1
    2
    

    as the smallest and second smallest numbers.