Largest Two Elements – Single Loop

Problem

Given an array of positive integers. Find the first and second largest elements in the array. You are not allowed to use more than one loop in your solution.

Solution

The solution is to use a single loop to find the first and second maximum. The current array element is compared to both first and second maximum values calculated so far then updating them accordingly. Please refer to the code below for more details. In the next post we will solve this problem using divide and conquer technique.

Code

Here is the C++ code to do that using a single loop

//Includes
#include <iostream>

//Name space
using namespace std;

//Main function
void main()
{
	//Array
	int A[10] = {1, 5, 3, 2, 4};

	//Array size
	int n = 5;

	//Initialize first and second maximum
	int max1 = -1;
	int max2 = -1;

	//Find the first and second maximum
	for (int i = 0; i < n; i++)
	{
		//if the current element is greater 
		//than the first maximum then we 
		//should update it
		if (A[i] >= max1)
		{
			max1 = A[i];
		}
		//Otherwise compare the current element 
		//with the second maximum and update it 
		//similarly
		else if (A[i] >= max2)
		{
			max2 = A[i];
		}
		//Otherwise keep the first and 
		//second maximum intact
		else
		{
			//Nothing
		}
	}

	//Print out
	cout << "max1 = " << max1 << endl;
	cout << "max2 = " << max2 << endl;
}
Tags:
One Comment

Leave a Reply