'Finding the second largest element in array without sorting
I know about the single traversal method initialising two variables to INT_MIN. But my question is why do we initialise two variables to INT_MIN and also what is the purpose of INT_MIN here?
Why can't we initialise two variables to its first element like I have done in the code below? Because when I hand-checked the code manually, I found nothing wrong. So why doesn't the code run properly?
#include <stdio.h>
int main(void) {
int x[10];
int i, n;
int first = x[0];
int second = x[0];
printf("Input the size of array :");
scanf("%d", &n);
printf("Input %d elements in the array :\n", n);
for (i = 0; i < n; i++) {
printf("x[%d]: ", i);
scanf("%d", &x[i]);
}
for (i = 0; i < n; ++i) {
if (first < x[i]) {
second = first;
first = x[i];
} else
if (x[i] > second && x[i] != first) {
second = x[i];
}
}
if (second == first)
printf("There is no second largest element\n");
else
printf("\nThe Second largest element in the array is: %d", second);
return 0;
}
Solution 1:[1]
There are several problems in your code:
- the array
xis defined with a length of10, but uninitialized when you setfirstandsecondto the value of its first element. - you do not test the return value of
scanf(), leading to undefined behavior in case of input failure. - you do not test of
nis in less or equal to10before reading values intox. - you need to special case
n <= 0as no values will be read intox.
Here is a modified version:
#include <stdio.h>
int main(void) {
int x[10];
int i, n, first, second;
printf("Input the size of array :");
if (scanf("%d", &n) != 1 || n < 0 || n > 10) {
printf("invalid input\n");
return 1;
}
if (n <= 0) {
first = second = 0;
} else {
printf("Input %d elements in the array:\n", n);
for (i = 0; i < n; i++) {
printf("x[%d]: ", i);
if (scanf("%d", &x[i]) != 1) {
printf("invalid input\n");
return 1;
}
}
first = second = x[0];
for (i = 1; i < n; ++i) {
if (first < x[i]) {
second = first;
first = x[i];
} else
if (x[i] > second && x[i] != first) {
second = x[i];
}
}
}
if (second == first)
printf("There is no second largest element\n");
else
printf("\nThe Second largest element in the array is: %d\n", second);
return 0;
}
Regarding an alternative implementation where first and second are initialized to INT_MIN and the loop starts at i = 0, the trick is INT_MIN is the smallest possible int value, so first will compare <= to all values of the array and therefore will not shadow a smaller value. It is also a good default return value for a function that finds the maximum value in an array when passed an empty array.
For your case study, the INT_MIN approach is does not work and the algorithm would fail on an array with a single repeated value: at the end of the scan, first would be set to that value and second would still be INT_MIN.
- testing
first == secondwould yield a second largest value equal toINT_MIN, which is incorrect. - testing
second == INT_MINto determine if all values are identical would be incorrect too as an array with values{ 1, INT_MIN }would indeed have a second largest value equal toINT_MIN.
Your approach works correctly and the alternative would need to be written differently, with an extra variable. Indeed the solution presented in this article is incorrect, and so is this one, this one, this one and countless more random code across the Internet.
Solution 2:[2]
I've added some comments where I saw some problems. Hopefully I caught all the problems. Code below.
#include <stdio.h>
int main(void) {
// int x[10]; I moved this to under where you ask the user for the array size.
int i, n;
// int first=x[0]; This should be written after the user has inputted their numbers. Because what is in x[0]? user hasn't entered anything yet
// int second=x[0]; Same reason as ^
printf("Input the size of array :");
scanf("%d",&n);
int x[n]; // This should be here because you asked the user what the size of the array is.
printf("Input %d elements in the array :\n",n);
for(i=0; i<n; i++)
{
printf("x[%d]: ", i);
scanf("%d", &x[i]);
}
// You should put your first and second int's here
int first=x[0];
int second=x[0];
for (i=0; i<n ; ++i)
{
if (first<x[i])
{
second = first;
first = x[i];
}
else if (x[i] > second && x[i] != first)
{
second = x[i];
}
}
if (second == first)
printf("There is no second largest element\n");
else
printf("\nThe Second largest element in the array is: %d", second);
return 0;
}
Solution 3:[3]
int first=x[0];
int second=x[0];
x isn't initialized yet.
Solution 4:[4]
Prints -1 if no second largest element is found.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int findNotSame(long long int a[],long int n)
{
long long int temp = a[0];
int flag = 0;
long int i;
for(i=0;i<n;i++)
{
if(a[i]!=temp)
return 1;
}
return 0;
}
long long int findMax(long long int a[],long int n)
{
long int i;
long long int max = a[0];
for(i=0;i<n;i++)
{
if(a[i]>max)
max = a[i];
}
return max;
}
int main() {
long int i,j,n;
scanf("%ld",&n);
long long int a[n];
if(n<2) //There cannot be scond largest if there;s only one(or less) element.
{
printf("-1");
return 0;
}
for(i=0;i<n;i++) //Read elements.
scanf("%lld",&a[i]);
if (!findNotSame(a,n)) //Check if all the elements in array are same if so, then -1.
{
printf("-1");
return 0;
}
long long int max = findMax(a,n); //Find maximum element(first).
long long int max2 = -999999999999999; //Initialize another max which will be the second maximum.
for(i=0;i<n;i++) //Find the second max. element.
{
if(a[i]>max2 && a[i] != max)
max2 = a[i];
}
if(max == max2) //Incase if second max(largest) is same as maximum
max2 = -1;
printf("%lld",max2);
return 0;
}
Solution 5:[5]
import ast
input_str = input()
input_list = ast.literal_eval(input_str)
if len(input_list)<2:
print("not present")
else:
i=input_list[0]
j=i
for index_val in input_list[1:]:
if i<index_val:
j=i
i=index_val
elif index_val>j and index_val!=i:
j=index_val
elif i==j and index_val<j:j=index_val
if i==j:
print("not present")
else:
print(j)
Solution 6:[6]
This works,
val arr=Array(4,1,2,4,5,5,7,18,10,5,7)
var firstAndSecondIndex:(Int,Int)=null
for(indexVal <- 2 to (arr.size -1))
firstAndSecondIndex match {
case null =>
println("0,0")
firstAndSecondIndex=(0,1)
case value =>
value match {
case value if arr(indexVal) == arr(value._1) || arr(indexVal) == arr(value._2) =>
println("equals")
case value if arr(indexVal) > arr(value._1) =>
println("1,0")
value match {
case value if arr(indexVal) > arr(value._2) && arr(value._1) > arr(value._2) =>
firstAndSecondIndex=(indexVal,value._1)
case value if arr(indexVal) > arr(value._2) && arr(value._1) < arr(value._2) =>
firstAndSecondIndex=(indexVal,value._2)
case value if arr(indexVal) < arr(value._2) =>
firstAndSecondIndex=(indexVal,value._2)
}
case value if arr(indexVal) < arr(value._1) =>
println("1,1")
value match {
case value if arr(indexVal) > arr(value._2) =>
firstAndSecondIndex=(indexVal,value._1)
case value if arr(indexVal) < arr(value._2) =>
println("not greater")
}
}
}
val secondLargest= arr(firstAndSecondIndex._1) < arr(firstAndSecondIndex._2) match {case true => arr(firstAndSecondIndex._1) case false => arr(firstAndSecondIndex._2)}
Solution 7:[7]
int arr[] = {56, 41, 19, 33, 13, 23, 25};
int max = 1;
int secondMax = 0;
for (int i = 0; i < arr.length; i++) {
int getValue = arr[i];
if (max == 1) {
max = getValue;
secondMax = arr[1];
} else {
if (max < getValue) {
secondMax = max;
max = getValue;
} else if (secondMax < getValue) {
secondMax = getValue;
} else {
// Nothing Do
}
}
}
System.out.println("" + secondMax);
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | Aniket |
| Solution 3 | John Kugelman |
| Solution 4 | Ganesh Jadhav |
| Solution 5 | nemish zalavadiya neel |
| Solution 6 | Raptor0009 |
| Solution 7 | Madhan G.S |