silentknight00's blog

How to find the larger elements to the left of every element in a given array?
By silentknight00, history, 8 years ago, In English

Given an array [1,3,4,2] we should get an array [0,0,0,2]. Can someone suggest a quick method for doing this

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This is essentially the inversion problem which can be solved using segment tree or binary indexes tree in O(nlogn). ( You can search for it online)

→ Reply
»
8 years ago, hide # |
← Rev. 3  
Vote: I like it +10 Vote: I do not like it

Iterate from the left and imagine the array is the skyscrapers with height a[i]. Now we want to maintain all skyscrapers visible from i. To do so just maintain a stack. O(n).

stack<int>X;
for (int i = 0; i < n; i++)
{
	while (!X.empty() && a[X.top()] <= a[i])
	{
		X.pop();
	}
	if (X.empty())
		ans[i] = -1;
	else
		ans[i] = X.top();
	X.push(i);
}
→ Reply