finding the second minimum

Question

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

Answer 1

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.

Answer 2

You could use STL algorithm nth_element, the complexity is O(n):

#include <iostream>
#include <algorithm>

int main(int argc, char** argv) {
    int a[5]={7,5,45,89,12};
    std::nth_element(a, a + 1, a + 5);
    std::cout << "second smallest value is: " << a[1];
    return 0;
}

If you want to keep the array a unchanged, you could use partial_sort_copy instead.

int a[5]={7,5,45,89,12}, b[2];
std::partial_sort_copy(a, a + 5, b, b + 2);
std::cout << "second smallest value is: " << b[1];

in this case, the complexity is O(n) as well.