CareerCup

We can use a stack

Prev_Smaller_Element[0] = Null
stack.push(arr[0])

for i = 1 to N - 1
	if(stack.top() < arr[i])
		Prev_Smaller_Element[i] = stack.top()
	else
		while(stack.top >= arr[i] && !stack.empty())
			stack.pop()
		
		if(!stack.empty())
			Prev_Smaller_Element[i] = stack.top()
		else
			Prev_Smaller_Element[i] = Null

	stack.push(arr[i])

Complexity :- O(N)

1. Use augmented BST where each node will contain two extra fields, one keeping track of the index of the element, another keeping track of the largest index of element less than this node's element.
Making clarifications, while inserting a value in BST, if it is less than root node, update the second field only if it is larger than the field stored there. If the field value is not set, then store this index.
2. Insert the elements into BST, if we use self balancing BST, the running time complexity is O(nlogn).
3. For each element in the array, search it in BST & print its corresponding field .

Let me know if i am missing anything.

start from back looking for X.
After hitting X look for Y which is the less than X.. once you hit such number .. return it
or else move till the start of the array and return null if there is no number < X

var array = [ ..... ];

function gohil90Question ( pos, arr ) {
  var val = arr[ pos ];

  while( pos-- )
    if( arr[ pos ] < val )
        return pos;

  return NULL;
}

1. Build a minleft[] which contains the element less than arr[i] from 0 to i-1 ,else -1.
2. Build a maxright[] which contains the element greater than arr[i] from i+1 to N-1 ,else -1.
3. run a loop from 0 to N-1,stat cheching the elements of minleft[] & maxright[].
if(minleft[i]<maxright[j]) j++ update maxdiff(j-i)
else i++

Assumption : there are no duplicate in input array

public class Prog1 {

	public static void main(String[] args) {

		int arr[] = {1,3,5,6,2,11,4} ;
		int value = 2 ;

		System.out.println("Soln "+solve(arr,value));

	}

	public static int solve(int []arr,int value) {

		int closer = -1 ;
		int i = 0 ;

		while(i<arr.length && arr[i]!=value) {

			if(arr[i] < value && arr[i] > closer )
				closer = arr[i] ;
			
			++i ;
		}

		return closer ;
	} 

}

Maintain a parallel sorted array of same size in following manner.

Maintain a tail pointer. At any point, the active array is between starting element and the element at the tail.

Insertion rules
1. For a new number x do binary search in the array and position the element against the next larger element. If there is no such element, add the element in the last.
2. Print element and its predecessor and move tail pointer to this index.

Example :
Given list
7, 1, 6, 5, 8, 3, 2, 9

Element   Array      Action           Tail             Printed
7              7            Inserted 7      index1         7, null
1              1            Replaced 7    index1         1, null
6              1,6         Inserted 6      index2          6,1
5              1,5         Replaced 6    index2          5,1
8              1,5,8      Inserted 8      index3          8,5
3              1,3         Replaced 5    index2          3,1
2              1,2         Replaced 3    index2          2,1
9              1,2,9      Inserted 9      index3          9,2

Since, we are using binary search for detecting the right location of element in the sorted array, operation wouldn't cost more than logK (Where k is avg. no. of elements in the array). K will be less than n .

Use of tail index saves us from shifting operations in array. So, no added time for it.

Complexity is O(nlogK)

Here is c++ code which works perfectly in n*log(n) order, although you might make the tree a balenced tree, which is not a big deal

#include <iostream>
using std::cout;
using std::endl;

struct node
{
  int key_value;
  int less_index;
  node *left;
  node *right;
};

class btree
{
    public:
        btree();
        ~btree();
        int insert(int key, int index);
        void destroy_tree();
    private:
        void destroy_tree(node *leaf);
        node *root;
};

void nsquare_y_founder(int *A, int size_A)
{
	for(int i=0; i<size_A; ++i)
	{
		int j=i-1;
		for( ; j>-1 && A[j] >= A[i]; --j);
		if(j==-1)
			cout<<"For the value x = "<<A[i]<< " its y value is 0"<<endl;
		else
			cout<<"For the value x = "<<A[i]<< " its y value is "<<A[j]<<endl;
	}
}

void nlogn_y_founder(int *A, int size_A)
{
	btree mytree;
	for(int i=0; i<size_A; ++i)
	{
		int j=mytree.insert(A[i],i);
		if(j==-1)
			cout<<"For the value x = "<<A[i]<< " its y value is 0"<<endl;
		else
			cout<<"For the value x = "<<A[i]<< " its y value is "<<A[j]<<endl;
	}
}

int main() {
	int A[]={12,25,13,44,11,42,15,20,54,17};
	cout<<"Here is the n^2 algorithm output: "<<endl;
	nsquare_y_founder(A, 10);
	cout<<"Here is the nlog(n) algorithm output: "<<endl;
	nlogn_y_founder(A, 10);

	return 0;
}

int btree::insert(int key, int index)
{
	int index_of_y = -1;
	if(root!=0)
	{
		node *current = root;
		bool flag = true;
		while(flag)
		{
			if(key< current->key_value)
			{
				current->less_index = index; //updating less_index
				if(current->left!=0)
					current = current->left;
				else
				{
					current->left=new node;
					current->left->key_value=key;
					current->left->less_index = index;
					current->left->left=0;    //Sets the left child of the child node to 0
					current->left->right=0;   //Sets the right child of the child node to 0
					flag = false;
				}
			}
			else if(key>=current->key_value)
			{
				index_of_y = (index_of_y > current->less_index ? index_of_y : current->less_index); //updateing index_of_y
				current->less_index = index_of_y; //updating less_index for the current node
				if(current->right!=0)
					current = current->right;
				else
				{
					current->right=new node;
					current->right->key_value=key;
					current->right->left=0;  //Sets the left child of the child node to 0
					current->right->less_index = index;
					current->right->right=0; //Sets the right child of the child node to 0
					flag = false;
				}
			}
		}
	}
	else
	{
		root=new node;
		root->key_value=key;
		root->left=0;
		root->right=0;
		root->less_index = index;
	}
	return(index_of_y);
}

btree::btree()
{
  root=0;
}
btree::~btree()
{
  destroy_tree(root);
}

void btree::destroy_tree(node *leaf)
{
  if(leaf!=0)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
  }
}

working c code
{{
//Time Complexity- O(nlogn)
#include<stdio.h>
int main()
{
int i,j,k,l,m,n,flag,arr[1000],max,tree[1000][4],temp,ans[1000];
scanf("%d",&n);
for(i=0;i<=n;i++)
{
for(j=0;j<4;j++)
{
tree[i][j]=-1;
}
}
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
tree[i][0]=arr[i];
tree[i][3]=i;
}


tree[1][0]=arr[1];

i=2;max=-1;
while(i<=n)
{max=-1;
temp=1;flag=0;
while(!flag)
{
if(tree[i][0]<tree[temp][0])
{
tree[temp][3]=i;
if(tree[temp][1]==-1)
{tree[temp][1]=i;flag=1;}
else
temp=tree[temp][1];
}
else if(tree[i][0]>tree[temp][0])
{
if(tree[temp][3]>max)
max=tree[temp][3];
if(tree[temp][2]==-1)
{tree[temp][2]=i;flag=1;}
else
temp=tree[temp][2];
}

}
ans[i]=max;
i++;

}
ans[1]=-1;
for(i=1;i<=n;i++)
printf("%d ",ans[i]);



return 0;




}

}}

# your code goes here

a=[int(x) for x in raw_input().split(' ')]

l=[None]
s=[a[0]]
for i in range(1,len(a)):

	while len(s)>0 and s[len(s)-1]>=a[i]:
		s.pop()
	if len(s)>0:
		l.append(s[len(s)-1])
	else:
		l.append(None);
		
	s.append(a[i])
print l

we just save the local min and max

#include <iostream>
using namespace std;
int v[]={5,4,7,9,1,15}; // initial array
int n=6; //v.length
int r[100]; // response arrray
// r will have 0 if there are no numbers to make the conditions true and 1 if there are
int main()
{
	int min=v[0];  // save the minimum so far
	int max=v[0];
	for (int i=1; i<n; i++ )
	{
		if (v[i]<min ) min=v[i];  // has no smaller intem before him
		else
		{
			r[i]=max;  // has item and therefore r=1			
			if ( v[i]>max ) max=v[i];
		}
	}
	for ( int i=0; i<n; i++)
		cout<<v[i]<<" ";
	cout<<endl;
	for ( int i=0; i<n; i++) 
		cout<<r[i]<<" ";
	cout<<endl;
	return 1;
}

// values : array of integers
// precedents : array of indices, where indices are in accordance with the problem statement rules
void SmallerPrecedent(int[] values, int[] precedents)
{
int i;

if (values.Length == 0)
return;

precedents = new int[values.Length);
precedents[0] = Int32.MinValue;

for (i = 1 ; i < values.Length ; i++)
{
if ((values[i] >= values[i - 1]))
precedents[i] = precedents[i - 1];

precedents[i] = FindDecreasingValuePrecedent(values, precedents, i);
}

}

int FindDecreasingValuePrecedents(int[] values, int[] precedents, int position)
{
int i;

Debug.Assert(position > 0);

for (i = position - 1 ; i >= 0 ; )
{
int precedent = precedents[i];

if (precedent == Int32.MinValue)
return (precedent);

if (values[precedent] <= values[position])
return (predecent);

i = precedent;
}

return (Int32.MinValue);
}

Dynamic programming