CS1020 Swing Monkey Lab4 Ex2

Link to the question – Swing Monkey Lab 4 Ex 2

import java.util.*;

class Swing
{

	public static void main(String [] args)
	{
		Scanner sc = new Scanner (System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for(int i = 0; i < N; i++)
		{
			arr[i] = sc.nextInt();
		}
		System.out.println(solve(arr));
	}
	
	public static int solve(int[] list)
	{
		Stack<Integer> stack = new Stack<Integer>();
		int input = 0;
		int numPairs =0;
		for(int i = 0; i < list.length; i++)
		{
			input = list[i];
			//add to stack if it is empty
			if(stack.isEmpty())
			{
				stack.push(input);
			}
			else if(!stack.isEmpty())
			{
				//pop all top element if it is smaller than the input
				while(!stack.isEmpty() && input > stack.peek())
				{
					stack.pop();
					numPairs++;
				}
				//add the input because the stack is empty
				if(stack.isEmpty())
				{
					stack.push(input);
				}
				else if(!stack.isEmpty() && input < stack.peek())	//all the other cases
				{
					stack.push(input);
					numPairs++;
				}
				else if(input == stack.peek())	//not pushed because they are same. just increment the count
				{
					numPairs++;
				}
			}
		}
		return numPairs;
	}
}
Advertisements
This entry was posted in NUS, SoC and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s