Q: You are given an array of integers. For each element x find a suitable y such that

1. Val(Y) < Val(x)

2. Position(Y) < Position(X)

3. Position of Y should be maximum as possible

4. If there is no such Y, set it to null

Try to achieve complexity better than O(n^2).

A: Use a doubly linked list with following insertion and maintenance rules –

1. Linked starts with null and at any point, parent node is the value of Y for operational element. The prints of Y happens at the time of element insertion.

2. For each element X, Start with the tail of the linked list.

> If its null node, add a node X as its successor.

> If linked list node element is less than X, add a new node as its successor.

> If node element is greater equals X, delete that node(including its tail) and re-do comparison with its parent.

Sample run

Say for array 7, 1, 4, 8, 5, 6, 2

Operational Element | Linked List | Operation taken | Printed Result (X, Y) |

7 | null -> 7 | Added node 7 | 7, Null |

1 | null -> 1 | Deleted node 7 and added node 1 | 1, Null |

4 | null -> 1 -> 4 | Added node 4 | 4,1 |

8 | null -> 1 -> 4 -> 8 | Added node 8 | 8,4 |

5 | null -> 1 -> 4 -> 5 | Deleted 8 and added 5 | 5,4 |

6 | null -> 1 -> 4 -> 5 -> 6 | Added Node 6 | 6,5 |

2 | null -> 1 -> 2 | Deleted 6, then 5, then 4 while traversal from tail and added 2 | 2,1 |

PS: We do complete traversal of linked list from right to left. We can have a step further by maintaining the linked list in such a manner, that we can do binary search on it (by storing position index separately). It can be more optimized by using binary search as linked list is always sorted.