CareerCup

if array has only one element than we can throw a exception or print a message saying that array has only one element

public static int FindSecondNdLarge(int[] array)
        {
            int size = array.Length;
            int[] max = new int[] { 0, 0 };
            int counter; 

            if (array[0] > array[1])
            {
                max[0] = array[0];
                max[1] = array[0];
            }
            else
            {
                max[0] = array[1];
                max[1] = array[0];
            }

            for (counter = 2; counter < size; counter++)
            {
                if (array[counter] > max[1])
                {
                    if (array[counter] > max[0])
                    {
                        max[1] = max[0];
                        max[0] = array[counter];
                    }
                    else
                    {
                        max[1] = array[counter];
                    }
                }
            }

            return max[1];

}

static int secondLargest(int *arr, int size)
{
	int secondL, largest;
	largest = arr[0];
	secondL = 0;
	for(int i=0; i < size; i++)
	{
		if(arr[i+1] > largest)
		{
			secondL = largest;
			largest = arr[i+1];			
		}
		else if(arr[i+1] > secondL)
		{
			secondL = arr[i+1];
		}
	}
	return secondL;
}

what is the action when there are duplicates? for instance what if number of elements in array is greater then 2 but all elements in the array are equal?

public class secondLargest {

public static void main(String args[])
{
int arr[] = {100,6,10,7,11,12,3,2,100,17,8,9,100,91,981,5};
int second = findSecond(arr);
System.out.println(" The second largest element in the array is - "+second);
}

//function which returns the second largest element..

public static int findSecond(int arr[])
{
int length =arr.length;
int large,slarge, flag=0;
large=arr[0];
slarge=arr[0];
for(int i=0;i<length;i++)
{
if(large<arr[i])
{
large=arr[i];
}
}
for(int i=0;i<length;i++)
{
if(large!=arr[i])
{
slarge=arr[i];
flag=1;
break;
}
    }

//to check whether the array contains only one value or not

if(flag!=1)
{
slarge=large;
return slarge;
}
for(int i=0;i<length; i++)
{ 
if((slarge<arr[i])  && (arr[i]<large))
{
slarge=arr[i];
}
}
return slarge;
}
}

We can solve this way: First create a Max-Heap with all the values (Build-Heap takes O(n) time). Then We extract max O(logn) time, and then Maximum (O(1)) is the second largest value. For one value, after extract max heap will be empty and next Maximum call will return null.

int find2ndmax(const vector<int>& ar)
{
	int max = numeric_limits<int>::min();
	int max2 = numeric_limits<int>::min();
	for (vector<int>::const_iterator ii = ar.begin(); ii != ar.end(); ii++) {
		if (*ii > max) {
			max2 = max;
			max = *ii;
		}
	}
	if (max2 == numeric_limits<int>::min()) {
		throw 1; // or return max, depends on what this function is used for
	}
	return max2;
}

public class SecondMax {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SecondMax secondMax = new SecondMax();
		int [] array = {10,4,6,4,7};
		int secondMaxValue = secondMax.getSecondMax(array);
		System.out.println("The second max number in the array  " + secondMaxValue);

	}
	private int getSecondMax(int[] array){
		int max = Integer.MIN_VALUE;
		for(int i =0; i<array.length;i++){
			if(array[i] > max)
				max = array[i];
		}
		int difference = 0;
		int secondMax =0;
		int value = Integer.MAX_VALUE;
		for(int i =0; i<array.length;i++){
			difference = max - array[i];
			if(difference < value && difference !=0){
				value = difference;
				secondMax = array[i];
			}
		}
		return secondMax;
	}

1 if 1 element, throw exception
2. if 2, return itself
3. if 3 or more, find max which takes O(n), then iterate again to find max2 with the condition max2<=max, which takes O(n)

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {100,6,10,7,11,12,3,2,100,17,8,9,100,91,981,5}; 
		int max;
		int nextMax;
		
		Arrays.sort(arr);
		
		System.out.println("First max is: "+arr[arr.length - 1]);
		
	   for(int i = arr.length - 2; i>=0 ;i--){
		   
		   nextMax = arr[i];
		   
		   if(nextMax != arr[arr.length - 1]){
			   System.out.println("Next max is: "+nextMax);
			   break;
		   
		   }
		   
	   }
		
	    

	}

- If the length of array is 1 then throw exception
- If the length of array is 2 then return the array itself
- If the length of array is greater than two then sort the array in desending order using some algorithm and then return the 1st two elements