What is wrong and why time limit exceeds , it will run in O(n) time

#1

Scanner sc=new Scanner(System.in);

	Stack<Integer> st=new Stack<>();
	
	int n=sc.nextInt();
	int arr[]=new int[n];
	int ans[]=new int[n];
	
	for(int i=0 ; i<n ; i++)
		arr[i]=sc.nextInt();
	
	st.push(0);
	boolean check=true;
	for(int i=1 ; i<2*n-1 ; i++)
	{
		if(i>n-1)
		{
			i=i%n;
			check=false;
		}
		
		if(arr[i]>arr[st.peek()])
		{
			while(!st.isEmpty() && arr[i]>arr[st.peek()] && i!=st.peek())
			{

// System.out.println(arr[st.peek()] + " --> " + arr[i]);

// int j=binaryS(arr[st.peek()] , 0 , n , arr);
// ans[j]=arr[i];

				ans[st.peek()]=arr[i];
				st.pop();
			}
			
			if(!st.isEmpty() && i>=st.peek() && !check)
				break;
			
			if(check)
				st.push(i);
		}
		else if(arr[i]<arr[st.peek()])
		{
			if(check)
				st.push(i);
			if(check==false && i>=st.peek()-1)
				break;
		}
		
	}
	
	
	while(!st.isEmpty())
	{

// System.out.println(arr[st.peek()] + " --> " + "-1 ");

// int j=binaryS(arr[st.peek()] , 0 , n , arr);
// ans[j]=-1;

		ans[st.peek()]=-1;
		st.pop();
	}
	
	for(int i:ans)
		System.out.println(i);
#2

@Himanshu-Jhawar-2273952536067590,

Can you please explain your approach?

Approach:
This approach makes use of a stack. This stack stores the indices of the appropriate elements from nums array. The top of the stack refers to the index of the Next Greater Element found so far. We store the indices instead of the elements since there could be duplicates in the nums array. The description of the method will make the above statement clearer.

We start traversing the numsnums array from right towards the left. For an element nums[i] encountered, we pop all the elements stack[top] from the stack such that nums[stack[top]] ≤ nums[i]. We continue the popping till we encounter a stack[top] satisfying nums[stack[top]]>nums[i]. Now, it is obvious that the current stack[top] only can act as the Next Greater Element for nums[i](right now, considering only the elements lying to the right of nums[i]).

If no element remains on the top of the stack, it means no larger element than nums[i] exists to its right. Along with this, we also push the index of the element just encountered(nums[i]), i.e. ii over the top of the stack, so thatnums[i](or stack[topstack[top) now acts as the Next Greater Element for the elements lying to its left.

We go through two such passes over the complete nums array. This is done so as to complete a circular traversal over the nums array. The first pass could make some wrong entries in the res array since it considers only the elements lying to the right of nums[i], without a circular traversal. But, these entries are corrected in the second pass.

Example 1:
4 3 2 1
Expected Output:
-1 4 4 4

#3

can you give code of this

what i have done is instead of printing greater element while iterating , i store the ans in an array of ans at the index of the element , which means for any element greater value will be stored at the same index as of the element

#4

@Himanshu-Jhawar-2273952536067590,

I would suggest that you try and code this on your own. You can post your code here on this thread incase you have any doubts.

#5

my this code is working , just the thing is it gives TLE error , though it runs on O(N) only

#6

@Himanshu-Jhawar-2273952536067590,
Your code is going in an infinite loop if all the elements are same.

Input:
5
1 1 1 1 1

For the above input your code goes into an infinite loop, hence the TLE

#7

though this code is accepted , but this is not readable , can you help me write readable code for this

import java.util.*;
public class Main {
public static void main(String args[]) {

	Scanner sc=new Scanner(System.in);
	
	Stack<Integer> st=new Stack<>();
	
	int n=sc.nextInt();
	// array to take elements
	int arr[]=new int[n];
	
	// array to store ans 
	int ans[]=new int[n];
	
	for(int i=0 ; i<n ; i++)
		arr[i]=sc.nextInt();
	
	// push first element index
	st.push(0);
	
	// to make circular array condition possible
	boolean check=true;
	
	// entering loop
	for(int i=1 ; i<=n ; i++)
	{
		
		// condition for making circular array
		if(i>n-1)
		{
			i=i%n;
			check=false;
		}
		
		
		// if element is bigger than st.peek() , then save results for stored
		// elements on stack in the ans array and pop them and then push  
		// the current element , i.e , i'th element
		if(arr[i]>arr[st.peek()])
		{
			
			// storee result in answer array
			while(!st.isEmpty() && arr[i]>arr[st.peek()] && i!=st.peek())
			{	
				// st.peek() is index of the element for which 
				// result will be stored
				ans[st.peek()]=arr[i];
				st.pop();
			}
			
			// if element after iteration passes the current 
			// index , i.e , the current index is st.peek() 
			if(!st.isEmpty() && i>=st.peek() && !check)
				break;
			
			// push the current element in stack
			if(check)
				st.push(i);
		}
		
		// if next element is smaller or equal store in stack
		else if(arr[i]<=arr[st.peek()])
		{
			// to check that element which we are storing
			// should not be stored again
			if(check)
				st.push(i);
			
			// if element after iteration passes the current 
			// index , i.e , the current index is st.peek() 
			if(check==false && i>=st.peek()-1)
				break;
		}
		
	}
	
	
	// assigning -1 to those present in stack
	while(!st.isEmpty())
	{	
		ans[st.peek()]=-1;
		st.pop();
	}
	
	
	
	// printing result
	for(int i:ans)
		System.out.print(i+" ");

}

}

#8

@Himanshu-Jhawar-2273952536067590,
https://ide.codingblocks.com/s/257870 you can refer to this code function. The input array is the array which we take as input

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.