StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Start making a BST, starting from the array end. For each value 'v' answer would be the last node "Right" that you took on your way to inserting 'v', of which you can easily keep track of in recursive or iterative version.<br><br> <strong>UPDATE:</strong> <br></p> <p>Going by your requirements, you can approach this in a linear fashion:<br></p> <p>If every next element is smaller than the current element(e.g. 6 5 4 3 2 1) you can process this linearly without requiring any extra memory. Interesting case arises when you start getting jumbled elements(e.g. 4 2 1 5 3), in which case you need to remember their order as long as you dont' get their 'smaller counterparts'. A simple stack based approach goes like this:</p> <p>Push the first element (a[0]) in a stack.</p> <p>For each next element a[i], you peek into the stack and if value ( peek() ) is greater than the one in hand a[i], you got your next smaller number for that stack element (peek()) { and keep on popping the elements as long as peek() > a[i] }. Pop them out and print/store the corresponding value. else, simply push back your a[i] into the stack.</p> <p>In the end stack 'll contain those elements which never had a value smaller than them(to their right). You can fill in -1 for them in your outpput.</p> <p>e.g. A=[4, 2, 1, 5, 3]; </p> <pre><code>stack: 4 a[i] = 2, Pop 4, Push 2 (you got result for 4) stack: 2 a[i] = 1, Pop 2, Push 1 (you got result for 2) stack: 1 a[i] = 5 stack: 1 5 a[i] = 3, Pop 5, Push 3 (you got result for 5) stack: 1 3 1,3 don't have any counterparts for them. so store -1 for them. </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload