Finding the second largest element in array without sorting

Question

I know about the single traversal method initialising two variables to INT_MIN. But my question is why do we initialise two variables to INT_MIN and also what is the purpose of INT_MIN here?

Why can't we initialise two variables to its first element like I have done in the code below? Because when I hand-checked the code manually, I found nothing wrong. So why doesn't the code run properly?

#include <stdio.h>

int main(void) {
    int x[10];
    int i, n;
    int first = x[0];
    int second = x[0];

    printf("Input the size of array :");
    scanf("%d", &n);

    printf("Input %d elements in the array :\n", n);
    for (i = 0; i < n; i++) {
        printf("x[%d]: ", i);
        scanf("%d", &x[i]);
    }

    for (i = 0; i < n; ++i) {
        if (first < x[i]) {
            second = first;
            first = x[i];
        } else
        if (x[i] > second && x[i] != first) {
            second = x[i];
        }
    }

    if (second == first)
        printf("There is no second largest element\n");
    else
        printf("\nThe Second largest element in the array is: %d", second);

    return 0;
}

Answer 1

There are several problems in your code:

• the array x is defined with a length of 10, but uninitialized when you set first and second to the value of its first element.
• you do not test the return value of scanf(), leading to undefined behavior in case of input failure.
• you do not test of n is in less or equal to 10 before reading values into x.
• you need to special case n <= 0 as no values will be read into x.

Here is a modified version:

#include <stdio.h>

int main(void) {
    int x[10];
    int i, n, first, second;

    printf("Input the size of array :");
    if (scanf("%d", &n) != 1 || n < 0 || n > 10) {
        printf("invalid input\n");
        return 1;
    }

    if (n <= 0) {
        first = second = 0;
    } else {    
        printf("Input %d elements in the array:\n", n);
        for (i = 0; i < n; i++) {
            printf("x[%d]: ", i);
            if (scanf("%d", &x[i]) != 1) {
                printf("invalid input\n");
                return 1;
            }
        }
        first = second = x[0];
        for (i = 1; i < n; ++i) {
            if (first < x[i]) {
                second = first;
                first = x[i];
            } else
            if (x[i] > second && x[i] != first) {
                second = x[i];
            }
        }
    }

    if (second == first)
        printf("There is no second largest element\n");
    else
        printf("\nThe Second largest element in the array is: %d\n", second);

    return 0;
}

Regarding an alternative implementation where first and second are initialized to INT_MIN and the loop starts at i = 0, the trick is INT_MIN is the smallest possible int value, so first will compare <= to all values of the array and therefore will not shadow a smaller value. It is also a good default return value for a function that finds the maximum value in an array when passed an empty array.

For your case study, the INT_MIN approach is does not work and the algorithm would fail on an array with a single repeated value: at the end of the scan, first would be set to that value and second would still be INT_MIN.

• testing first == second would yield a second largest value equal to INT_MIN, which is incorrect.
• testing second == INT_MIN to determine if all values are identical would be incorrect too as an array with values { 1, INT_MIN } would indeed have a second largest value equal to INT_MIN.

Your approach works correctly and the alternative would need to be written differently, with an extra variable. Indeed the solution presented in this article is incorrect, and so is this one, this one, this one and countless more random code across the Internet.

Answer 2

I've added some comments where I saw some problems. Hopefully I caught all the problems. Code below.

#include <stdio.h>

int main(void) {
    // int x[10]; I moved this to under where you ask the user for the array size.
    int i, n;
    // int first=x[0]; This should be written after the user has inputted their numbers. Because what is in x[0]? user hasn't entered anything yet
    // int second=x[0]; Same reason as ^

    printf("Input the size of array :");
    scanf("%d",&n);
    int x[n]; // This should be here because you asked the user what the size of the array is.

    printf("Input %d elements in the array :\n",n);
       for(i=0; i<n; i++)
        {
          printf("x[%d]: ", i);
          scanf("%d", &x[i]);
        }
    // You should put your first and second int's here
    int first=x[0]; 
    int second=x[0];

    for (i=0; i<n ; ++i)
     {
        if (first<x[i])
        {
            second = first;
            first = x[i];
        }

        else if (x[i] > second && x[i] != first)
         {
            second = x[i];
         }
    }

    if (second == first)
        printf("There is no second largest element\n");
    else
        printf("\nThe Second largest element in the array is: %d", second);


    return 0;
}