Third largest area without sorting

Question

I am taking an introductory class to programming and am trying to find the third largest area in an array of circles and then return the index of where this circle can be found without sorting, but ran into some troubles.

Input

Circle [0] 157/50
Circle [1] 314/25
Circle [2] 1413/50 
Circle [3] 1256/25 
Circle [4] 152/7

Expected Output

2

Actual Output

4

Correct me if I am wrong, but I think I assigned the wrong values to largest, secondlargest, and thirdlargest? Why is it returning 4? Here's what I have so far, thank you for the help. ^_^

int getThirdLargestArea(Circle** arr, int size) {
    Circle largest = *arr[0];
    Circle secondlargest = *arr[size - 1];
    Circle thirdlargest = secondlargest;

    int index = 0;

    for (int i = 1; i < size; i++) {
        if (largest.getArea() > arr[i]->getArea()) {
            thirdlargest = secondlargest;
            secondlargest = largest;
            largest = *arr[i];
            index = i;
        }

        else if (secondlargest.getArea() > arr[i]->getArea()) {
            thirdlargest = secondlargest;
            secondlargest = *arr[i];
            index = i;

        }

        else if (thirdlargest.getArea() > arr[i]->getArea()) {
            thirdlargest = *arr[i];
            index = i;
        }
    }

    return index;
}

Answer 1

First of all, you should replace > with < in three places in your code. For example, here: if (largest.getArea() > arr[i]->getArea()) you should enter if block if the ith element has greater area than your current largest area. Moreover, you should remember the first, second and third circles indices instead of circles themselves. You always update index with value of i but it is only correct in the last else block. If you remembered indices instead of circles, you would return thirdLargestIdx instead.

You should also be careful with your initial values of largest, secondlargest and thirdlargest variables. You shouldn't assume any particular order of sizes of circles you chose.

Just for completness, there is O(n) algorithm for finding kth largest element in array: https://en.wikipedia.org/wiki/Median_of_medians

Answer 2

These initializations are incorrect:

Circle largest = *arr[0];
Circle secondlargest = *arr[size - 1];
Circle thirdlargest = secondlargest;

They assume a few generally incorrect conditions: that the first element is larger than the last (true in your test case, false in general), and that there is an additional element equal to the last element (very unreasonable).

You should initialize your largest, secondlargest and thirdlargest to the first 3 elements, properly sorted:

largest_idx = 0;
secondlargest_idx = 1;
thirdlargest_idx = 2;

// bubble-sort of an array of 3 elements:
// swap 0 <-> 1 if needed
// swap 1 <-> 2 if needed
// swap 0 <-> 1 if needed
if (arr[largest_idx]->getArea() < arr[secondlargest_idx]->getArea())
    std::swap(largest_idx, secondlargest_idx);
if (arr[secondlargest_idx]->getArea() < arr[thirdlargest_idx]->getArea())
    std::swap(secondlargest_idx, thirdlargest_idx);
if (arr[largest_idx]->getArea() < arr[secondlargest_idx]->getArea())
    std::swap(largest_idx, secondlargest_idx);

Here I am using indices instead of objects because your function has to calculate an index, not return the object.

Then start examining the elements from the fourth one (the first one that was not examined yet):

for (int i = 3; i < size; i++) {
    ...
}

It's incorrect to examine an object twice, because e.g. the second largest element, repeated twice, can make you forget the third largest element.