Home > Software design >  The Second-largest Unique element in an Array
The Second-largest Unique element in an Array

Time:06-10

I am trying to find the second-largest number in an array. Can someone please tell me what condition I am missing?

I am sure there are many solutions available on the internet, but I would like to know what condition I might be missing in my code? (No Sorting)

class Solution {
    int print2largest(int numbers[], int n) {
        if(n <= 1)
            return -1;
            
        int firstLargeNo = -1, secondLargeNo = -1;

        if(numbers[0] > numbers[1]) {
            firstLargeNo = numbers[0];
            secondLargeNo = numbers[1];
        }
        else {
            firstLargeNo = numbers[1];
            secondLargeNo = numbers[0];
        }
        
        for(int i = 2; i < numbers.length; i  ) {
            if(numbers[i] > firstLargeNo) {
                secondLargeNo = firstLargeNo;
                firstLargeNo = numbers[i];
            }
            else if(firstLargeNo == secondLargeNo || numbers[i] > secondLargeNo)
                secondLargeNo = numbers[i];
        }
        
        if(firstLargeNo == secondLargeNo)
            return -1;
        
        return secondLargeNo;
    }
}

Failing Test Case File (Google Drive): test case

Correct output: 999

CodePudding user response:

It seems like you are looking the second-largest unique number in the array.

The first case when you can get firstLargeNo == secondLargeNo is at the moment of initialization, which can lead to an incorrect result if secondLargeNo will not get a chance to be reassigned (it would be the case when two largest values would be located at the very beginning of the array, e.g. {8, 8, 3, 1, 5}).

If two first elements of the array are equal, condition numbers[0] > numbers[1] would be evaluated to false and the block of code after else will be executed:

else {
    firstLargeNo = numbers[1];
    secondLargeNo = numbers[0]; // when numbers[1] == numbers[0], secondLargeNo become equal to firstLargeNo instead of being assign to -1
}

We can change the initialization of these variables like this:

int firstLargeNo = Math.max(numbers[0], numbers[1]);
int secondLargeNo = 
    numbers[0] == numbers[1] ? -1 : Math.min(numbers[0], numbers[1]);

Another mistake is rooted in the else if condition inside the loop. Checking firstLargeNo == secondLargeNo in not correct, instead we need to check whether next element numbers[i] is equal to firstLargeNo (and if it is the case we should skip this element).

The rest of the code can be written like this:

for(int i = 2; i < numbers.length; i  ) {
    if(numbers[i] > firstLargeNo) {
        secondLargeNo = firstLargeNo;
        firstLargeNo = numbers[i];
    }
    else if (numbers[i] != firstLargeNo && numbers[i] > secondLargeNo) {
        secondLargeNo = numbers[i];
    }
}
return secondLargeNo;

A link to Online Demo

CodePudding user response:

why are you starting i=2? because the array isn't sorting. initial values firstLargeNo=number[0] and secondLargeNo=number[0]; so get i=1;

CodePudding user response:

I propose this solution:

class Solution {
int print2largest(int numbers[], int n) {
    if(n <= 1)
        return -1;

    int secondLargeNo = -1, largest = numbers[0];

    for(int num : numbers) {
        if(num > largest) {
            secondLargeNo = largest;
            largest = num;
        }
    }

    return secondLargeNo;
}
}

It returns the second largest number in the array if it exists, otherwise it returns -1.

CodePudding user response:

public static int secondLargest(int [] src) {
    Integer highest = Integer.MIN_VALUE;
    Integer second = Integer.MIN_VALUE;

    for (int i : src) {
        if (i > highest) {
            second = highest;
            highest = i;
            continue;
        }

        if (i > second) {
            second = i;
        }
    }

    return second;
}
  • Related