C code find distinct third maximum. The code is working properly for another test case but for the test case below it gives a mistake

Question

I cannot understand where is the problem occurring here. Input is [1, 2]. Output must be 2, but my code gives 1.

Problem description: Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

int thirdMax(int *nums, int numsSize) {
    int i, j, k, temp;
    for (i = 0; i < numsSize; i++) {
        for (j = i + 1; j < numsSize; j++) {
            if (nums[j] < nums[i]) {
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
    }

    for (i = 0; i < numsSize; ++i) {
        while (j = i + 1 && j < numsSize) {
            if (nums[i] = nums[j]) {
                for (k = j; k < numsSize - 1; ++k)
                    nums[k] = nums[k + 1];
                --numsSize;
            } else
                ++j;
        }
    }

    if (numsSize >= 3)
        return nums[numsSize - 3];
    else
        return nums[0];
}

Answer 1

So, to solve the problem you sort the vector, remove duplicates, then return the third maximum if it exists.

There are two mistakes in the duplicate removal:

while(j=i+1 && j<numsSize)

which doesn't do what you think. And it's hard to guess what you were thinking. But an assignment there smells of mistake. As the following one:

if(nums[i]=nums[j])

... no, here you really wanted to compare. So you can fix that with:

    for (i = 0; i < numsSize; ++i) {
        j = i + 1;
        while (j < numsSize) {
            if (nums[i] == nums[j]) {
                for (k = j; k < numsSize - 1; ++k) {
                    nums[k] = nums[k + 1];
                }
                --numsSize;
            }
            else {
                ++j;
            }
        }
    }

Another mistake is in the closing section:

if(numsSize>=3)
    return nums[numsSize-3];
else
    return nums[0];
}

What if you have two distinct values? You should return the second one. So this is how it could work (assuming a non empty vector, i.e. numsSize>0):

    if (numsSize >= 3) {
        return nums[numsSize - 3];
    }
    else if (numsSize == 2) {
        return nums[1];
    }
    else {
        return nums[0];
    }

Additional thoughts

The gods of computational complexity are screaming here. Sorting (with O(n^2) operations), then removing duplicates with an O(n^2) approach is really a waste! Take advantage of the fact that equal values will be adjacent. Then I'd suggest to make that nums const, and not modify it at all.

Here is a O(n) version of the function. I'm pretty sure this can be written better, but this is what I came up with.

int thirdMax(int *nums, int numsSize)
{
    int maxs[3] = { 0 }; // this is just to silence some warnings
    int valid[3] = { 0 };
    for (int i = 0; i < numsSize; ++i) {
        if (valid[0]) {
            if (maxs[0] < nums[i]) {
                if (valid[1]) {
                    if (maxs[1] < nums[i]) {
                        if (valid[2]) { 
                            if (maxs[2] < nums[i]) { // new max: kick out 0 and move 1 and 2 down
                                maxs[0] = maxs[1];
                                maxs[1] = maxs[2];
                                maxs[2] = nums[i];
                            }
                            else if (maxs[2] > nums[i]) { // between 1 and 2: kick out 0 and move 1 down
                                maxs[0] = maxs[1];
                                maxs[1] = nums[i];
                            }
                        }
                        else { // new unseen value (three values now)
                            valid[2] = 1;
                            maxs[2] = nums[i];
                        }
                    }
                    else if (maxs[1] > nums[i]) { // between 0 and 1
                        if (valid[2]) { // kick out 0
                            maxs[0] = nums[i];
                        }
                        else { // put this in between
                            valid[2] = 1;
                            maxs[2] = maxs[1];
                            maxs[1] = nums[i];
                        }
                    }
                }
                else { // new unseen value (two values now)
                    valid[1] = 1;
                    maxs[1] = nums[i];
                }
            }
        }
        else { // no values up to now
            valid[0] = 1;
            maxs[0] = nums[i];
        }
    }
    if (!valid[2] && valid[1]) {
        return maxs[1];
    }
    return maxs[0];
}

Answer 2

Here

if(nums[i]=nums[j])

your intention was to check whether nums[i] and nums[j] are equal. Instead of that you have damaged your array, as nums[i] is overriden by the value of nums[j]. However, even if you fix this issue, your code is superfluous, you do not need to sort the array, for instance. This is how you can simply achieve the same goal:

int thirdMax(int* nums, int numsSize)
{
    int index;
    //Handling small array's case
    if (numsSize <= 2) {
        int max = nums[0];
        for (index = 1; index < numsSize; index++) {
            if (nums[index] > max) max = nums[index];
        }
        return max;
    }
    //Initializing
    int first;
    int second;
    int third;
    if ((nums[0] >= nums[1]) && (nums[0] >= nums[2])) {
        first = nums[0];
        if (nums[1] >= nums[2]) {
            second = nums[1];
            third = nums[2];
        } else {
            second = nums[2];
            third = nums[1];
        }
    } else if ((nums[1] >= nums[0]) && (nums[1] >= nums[2])){
        first = nums[1];
        if (nums[0] >= nums[1]) {
            second = nums[0];
            third = nums[1];
        } else {
            second = nums[1];
            third = nums[0];
        }
    } else {
        first = nums[2];
        if (nums[0] >= nums[1]) {
            second = nums[0];
            third = nums[1];
        } else {
            second = nums[1];
            third = nums[2];
        }
    }
    //Looping
    int distinct1 = nums[0];
    int distinct2 = nums[0];
    int distinct3 = nums[0];
    for (index = 3; index < numsSize; index++) {
        if ((distinct1 == distinct2) && (nums[index] != distinct1)) {
            distinct2 = nums[index];
        } else if ((distinct1 != distinct2) && (distinct2 == distinct3) && (nums[index] != distinct1) && (nums[index] != distinct2)) {
            distinct3 = nums[index];
        }
        if (nums[index] > third) {
            third = nums[index];
            if (third > second) {
                int aux = second;
                second = third;
                third = aux;
                if (second > first) {
                    int aux = first;
                    first = second;
                    second = aux;
                }
            }
        }
    }
    return (distinct2 == distinct3) ? third : first;
}

Answer 3

As already pointed out in previous answers, there are mistakes made using assignment instead of comparison.

I would add to the previous answers, that (depending on the use case) you need not write your own sort function. There is qsort.

See: C library function to perform sort

You could do:

#include <stdlib.h>
#include <string.h>


int compare_int(const void *a, const void *b)
{
    const int _a = *((const int*)a);
    const int _b = *((const int*)b);
    return (_a > _b) - (_a < _b);
}

/* This method returns the nth largest integer in your array. */
int nthmax(const int* arr, const size_t size, const unsigned int n)
{
    if (size <= 0) return arr[0];

    int* sorted_arr = malloc(size * sizeof(*arr));
    int* sorted_set_arr = malloc(size * sizeof(*arr));
    memcpy(sorted_arr, arr, size * sizeof(*arr));
    qsort(((void*)sorted_arr), size, sizeof *arr, compare_int);

    size_t new_size = 1;
    sorted_set_arr[0] = sorted_arr[0];
    for (unsigned int i = 1; i < size; ++i)
    {
        if (sorted_set_arr[new_size - 1] != sorted_arr[i])
        {
            sorted_set_arr[new_size++] = sorted_arr[i];
        }
    }
    size_t nselect = n >= new_size ? new_size - 1 : n;
    nselect = new_size - nselect - 1;

    const int nthmaxed = sorted_set_arr[nselect];

    free(sorted_arr);
    free(sorted_set_arr);

    return nthmaxed;
}

This way, your original array remains as-is, however this method may be harder on your memory.

Also: I did not really handle empty sized arrays, so use it at your own risk.

Answer 4

Here is another alternative method that does not modify the array and operates in O(n) time. It uses 3 passes:

1. find max, the maximum of the array, assuming a length of at least 1
2. find the maximum value max2 less than max if any
3. find the maximum value max3, less than max2 if any

If the second or third passes do not find a new maximum, return max as stated in the question.

int third_max(const int *nums, int len) {
    int max = nums[0];
    for (int i = 1; i < len; i++) {
        if (max < nums[i])
            max = nums[i];
    }
    int max2 = 0, has_max2 = 0;
    for (int i = 0; i < len; i++) {
        if (nums[i] < max && (!has_max2 || max2 < nums[i]))
            max2 = nums[i];
    }
    if (!has_max2)
        return max;
    int max3 = 0, has_max3 = 0;
    for (int i = 0; i < len; i++) {
        if (nums[i] < max2 && (!has_max3 || max3 < nums[i]))
            max3 = nums[i];
    }
    if (!has_max3)
        return max;  // If the third maximum does not exist, return the maximum number
    else
        return max3; // return the third maximum
}