Finding the second largest element in array without sorting

Question

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

You should explicitly explain what happens when the code doesn't run properly. Post your input, expected output, and the output you actually get. — Michael Burr
– Michael Burr, Commented Aug 12, 2018 at 23:01
Did you try to debug it? You should find the error very fast. — Thomas Sablik
– Thomas Sablik, Commented Aug 12, 2018 at 23:37
You need to read elements of x BEFORE assigning first = x[0] and second = x[0], not AFTER. Since elements of x are initially uninitialised, the initialisations of first and second both give undefined behaviour. — Peter
– Peter, Commented Aug 13, 2018 at 6:08

chqrlie · Accepted Answer · 2018-08-13 12:29:07Z

There are several problems in your code:

the array x is defined with a length of 10, but uninitialized when you set first and second to 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 n is in less or equal to 10 before reading values into x.
you need to special case n <= 0 as no values will be read into x.

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 == second would yield a second largest value equal to INT_MIN, which is incorrect.
testing second == INT_MIN to 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 to INT_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.

Aniket · Accepted Answer · 2018-08-13 01:33:03Z

4

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

answered Aug 13, 2018 at 1:33

Aniket

4591 gold badge3 silver badges12 bronze badges

3 Comments

izolveidon Over a year ago

Thank you for pointing it out and could you explain me the use of INT_MIN for initialising? I'm sorry I'm still new to this.

Jonathan Leffler Over a year ago

You could start the searching for loop at i = 1 since you know that x[0] == first and x[0] == second.

Jonathan Leffler Over a year ago

@debrisoroids: the reason the code uses INT_MIN is that there cannot be an integer value smaller than the minimum integer value.

John Kugelman · Accepted Answer · 2018-08-12 23:06:45Z

2

int first=x[0];
int second=x[0];

x isn't initialized yet.

answered Aug 12, 2018 at 23:06

John Kugelman

365k70 gold badges555 silver badges600 bronze badges

Comments

Shirsh Shukla · Accepted Answer · 2022-06-17 10:07:32Z

2

All solution is better, but some fail when the same items available in the array

like,

int arr[] = {56, 41, 19, 33, 13, 23, 25, 56};

56 available in two times,

so for this solution,

 int arr[] = {56, 41, 19, 33, 13, 23, 25,56};
 var max = arr[0];
 var secMax=-1;
 var size = arr.length;
   
   for(var l = 1; l < size; l++) {
     if (max < arr[l]) {
       secMax = max;
       max = arr[l];
     } else if (secMax < arr[l] && arr[l] != max) {
       secMax = arr[l];
     }
   }
   System.out.println("Second largest number :-" + secMax);

edited Jun 17, 2022 at 10:07

answered Jun 7, 2022 at 10:54

Shirsh Shukla

6,1333 gold badges38 silver badges51 bronze badges

Comments

Ganesh Jadhav · Accepted Answer · 2019-02-04 08:53:46Z

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

Rakesh Yadav · Accepted Answer · 2024-02-16 09:15:23Z

Above answers were not working when first element is largest, so we have to add 1 more additional check.

public class SecondLargestArrayWithoutSorting {
    
    public static void main(String args[]) {
        int arr[] = new int[] {10, 2, 6, 4, 5};
        //int arr[] = new int[] {1};
        int position = getSecondLargestPosition(arr);
        if(position == -1) {
            System.out.println("No Second Position");
        } else {
            System.out.println("Second Largest Value is " + arr[position]);
        }
        
    }
    
    public static int getSecondLargestPosition(int arr[]) {
        if(arr.length <= 1) {
            return -1;
        }
        
        int first = 0;
        int second = 0;     
        
        for(int i = 0; i < arr.length; i++) {
            if(arr[first] < arr[i] ) {
                second = first;
                first = i;
            } else if (arr[first] != arr[i]) {
                if(arr[second] < arr[i]) {
                    second = i;
                } else if (arr[second] == arr[first]) {
                    second = i;
                }
            }
        }
        
        return second;
    }
}

nemish zalavadiya neel · Accepted Answer · 2020-05-24 06:06:21Z

-1

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)

answered May 24, 2020 at 6:06

nemish zalavadiya neel

1661 silver badge5 bronze badges

1 Comment

nemish zalavadiya neel Over a year ago

This code uses 2 pointer technique to avoid sorting and do solving in o(n) time.

Raptor0009 · Accepted Answer · 2022-01-30 10:05:31Z

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

Madhan G.S · Accepted Answer · 2022-03-31 11:32:28Z

-1

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

answered Mar 31, 2022 at 11:32

Madhan G.S

11 silver badge3 bronze badges

2 Comments

Madhan G.S Over a year ago

This code works fine. This best method to avoid using sorting and also pre defined functions

Michael Kotzjan Over a year ago

Your answer could be improved with additional information like a small description on how this works as well as the resulting output from your code. Please edit your answer to make it truly great

Peter Mortensen · Accepted Answer · 2022-08-15 23:08:03Z

Java code to find the largest and second largest number in an array without sorting and using a single loop:

package programs;

import java.util.Scanner;

public class Demo {

    public static void main(String[] args) {
        int largest = -1;
        int secondlargest = -1;
        int numberPos = -1;
        int numberPos1 = -1;
        int[] arr = {22, 33, 9000, 70, 9000, -1, -10, -3, 22, 99, 100, 10000};
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > largest) {
                numberPos = i;
                largest = arr[i];
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (secondlargest < arr[i] && secondlargest < largest && arr[i] != largest) {
                secondlargest = arr[i];
                numberPos1 = i;
            }
        }
        System.out.println("Largest number is "+largest+" with position "+numberPos);
        System.out.println("Second largest is "+secondlargest+" with position "+numberPos1);
    }
}

Collectives™ on Stack Overflow

Finding the second largest element in array without sorting

10 Answers 10

Comments

3 Comments

Comments

Comments

Comments

Comments

1 Comment

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

10 Answers 10

Comments

3 Comments

Comments

Comments

Comments

Comments

1 Comment

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related