Find Last Smaller Element

Posted: August 22, 2012 in Algorithms, Directi
Tags: , ,

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.

Advertisements
Comments
  1. Harsh says:

    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)

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