finding the second Max in an unsorted dynamic array

I hope you are doing well, I share with my solution of the algorithm to find the second maximum in a given unsorted array, is there a better way to do it? (I found complexity O(2n))

int PositionDuSecondMax(int *T, int n) {
    // this function look for the index of the second maximum ( the number just under the maximum ) in a given array
    // exemple : T[] = {10,100,14,49]  ---> this function returns 3
    // we have T a dynamic array and n the number of elements in T
    // the given array in unsorted
    int iMax = 0; // we suppose iMax == 0
    int iSecMax;

    // we go through the array and compare T[iMax] with the current element in the current index
    // so we can find the index of the max in the array
    for (int i = 0; i < n; i++) {
        if (T[iMax] < T[i]) {
            iMax = i;
        }
    }
    // this if statement is to max sure that iMax is different from iSecMax
    if (iMax == 0) {
        iSecMax = 1;
    } else {
        iSecMax = iMax - 1;
    }
    // we loop through the array and compare each element with T[iSecMax] , we must specify that T[iSecMax] != T[iMax]
    for (int i = 0; i < n; i++) {
        if (T[iSecMax] < T[i] && T[iSecMax] == T[iMax]) {
            iSecMax = i;
        }
    }

    return iSecMax;
}

>Solution :

Your approach has multiple problems:

• if the max is at offset 0 with a duplicate at offset 1 or if the max is at offset iMax - 1, the initial value of iSecMax is that of the maximum so you will not find the second max.
• the test T[iSecMax] == T[iMax] to avoid select a duplicate of the max value is incorrect, it should be T[i] != T[iMax].

Here is a modified version:

int PositionDuSecondMax(const int *T, int n) {
    // this function look for the index of the second maximum ( the number just under the maximum ) in a given array
    // exemple : T[] = {10,100,14,49]  ---> this function returns 3
    // we have T a dynamic array and n the number of elements in T
    // the given array in unsorted
    int iMax = 0;
    int iSecMax = -1;

    // we go through the array and compare T[iMax] with the current element in the current index
    // so we can find the index of the max in the array
    for (int i = 1; i < n; i++) {
        if (T[iMax] < T[i]) {
            iMax = i;
        }
    }
    // we loop through the array, ignoring occurrences of T[iMax] and compare each element with T[iSecMax]
    for (int i = 0; i < n; i++) {
        if (T[i] != T[iMax] && (iSecMax < 0 || (T[iSecMax] < T[i])) {
            iSecMax = i;
        }
    }
    return iSecMax;
}

Notes:

• the above function will return -1 if the array is empty or has all entries with the same value, ie: no second max value.
• the complexity is O(n). O(2n) and O(n) are the same thing: O(n) means asymptotically proportional to n. You could modify the code to perform a single scan with a more complicated test, and it would still be O(n). If the array is unsorted, all elements must be tested so O(n) is the best one can achieve.