Finding the second Max in an unsorted dynamic array-CodePudding

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;
}

CodePudding user response：

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 returns the index of the second maximum (the number just under the maximum) in a given array
    // example: T[] = {10,100,14,49}  --> this function returns 3
    // arguments: T points to an unsorted array of int,
    //            n is the number of elements in T.
    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.
If the array was sorted, finding the second max would be O(1) on average (if the second to last element differs from the last), with a worst case of O(log n) (using binary search when the max has duplicates).

CodePudding user response：

If you want to find second largest element in one traverse, you can follow below approach.

if (arrSize < 2)
{
    printf(" Invalid Input ");
    return;
}

first = second = INT_MIN;
for (i = 0; i < arrSize; i  )
{
    /* If current element is greater than first
       then update both first and second */
    if (arr[i] > first)
    {
        second = first;
        first = arr[i];
    }

    /* If arr[i] is in between first and
       second then update second  */
    else if (arr[i] > second && arr[i] != first)
        second = arr[i];
}

if (second == INT_MIN) printf("There is no second largest element\n");
else printf("The second largest element is %d\n", second);

CodePudding user response：

The best approach is to visit each element of an array to find the second highest number in array with duplicates. The time complexity of this approach is O(n).

Algorithm :

i) Declare two variables max and second max and initialize them with integer minimum possible value.

ii) Traverse an array and compare each element of an array with the value assigned to max variable. If current element is greater than the value assigned at max variable. Then do two things –

a) In second max variable, assign the value present at max variable.

b) In max variable, assign the current index value.

iii) We have to do one more comparison that if current index value is less than max and greater than the value assigned at second max. Then, assign current index value at second max variable.

After complete iteration print the second max element of an array.

int secondLargest(int arr[], int len) {
    //Initialize
    int max = INT_MIN;
    int second_max = INT_MIN;

    for(int i = 0; i < len; i  ) {
        if(arr[i] > max) {
            second_max = max;
            max = arr[i];
        }

        if(max > arr[i] && arr[i] > second_max) {
            second_max=arr[i];
        }
    }
    
    return second_max;
}

int main(void) {
    int arr[] = {70, 4, 8, 10, 14, 9, 7, 6, 5, 3, 2};
    int len   = 11;
    printf("Second highest element is %d\n",secondLargest(arr,len));
    return 0;
}

CodePudding user response：

You can sort the array with an algorithm like merge sort or quicksort(with complexity theta(log n)) and you have the second maximum in the position array length-2. After you can find the original index of the number in the original array.