StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2>O(N) Algorithm</h2> <ol> <li>Initialize output array to all -1s.</li> <li>Create an empty stack of indexes of items we have visited in the input array but don't yet know the answer for in the output array.</li> <li>Iterate over each element in the input array: <ol> <li>Is it smaller than the item indexed by the top of the stack? <ol> <li>Yes. It is the first such element to be so. Fill in the corresponding element in our output array, remove the item from the stack, and try again until the stack is empty or the answer is no.</li> <li>No. Continue to 3.2.</li> </ol></li> <li>Add this index to the stack. Continue iteration from 3.</li> </ol></li> </ol> <h2>Python implementation</h2> <pre><code>def find_next_smaller_elements(xs): ys=[-1 for x in xs] stack=[] for i,x in enumerate(xs): while len(stack)>0 and x<xs[stack[-1]]: ys[stack.pop()]=x stack.append(i) return ys >>> find_next_smaller_elements([4,2,1,5,3]) [2, 1, -1, 3, -1] >>> find_next_smaller_elements([1,2,3,4,5]) [-1, -1, -1, -1, -1] >>> find_next_smaller_elements([5,4,3,2,1]) [4, 3, 2, 1, -1] >>> find_next_smaller_elements([1,3,5,4,2]) [-1, 2, 4, 2, -1] >>> find_next_smaller_elements([6,4,2]) [4, 2, -1] </code></pre> <h2>Explanation</h2> <h3>How it works</h3> <p>This works because whenever we add an item to the stack, we know its value is greater or equal to every element in the stack already. When we visit an element in the array, we know that if it's lower than <em>any</em> item in the stack, it must be lower than the <em>last</em> item in the stack, because the last item must be the largest. So we don't need to do any kind of search on the stack, we can just consider the last item.</p> <p>Note: You can skip the initialization step so long as you add a final step to empty the stack and use each remaining index to set the corresponding output array element to -1. It's just easier in Python to initialize it to -1s when creating it.</p> <h3>Time complexity</h3> <p>This is O(N). The main loop clearly visits each index once. Each index is added to the stack exactly once and removed at most once.</p> <h2>Solving as an interview question</h2> <p>This kind of question can be pretty intimidating in an interview, but I'd like to point out that (hopefully) an interviewer isn't going to expect the solution to spring from your mind fully-formed. Talk them through your thought process. Mine went something like this:</p> <ul> <li>Is there some relationship between the positions of numbers and their next smaller number in the array? Does knowing some of them constrain what the others might possibly be?</li> <li>If I were in front of a whiteboard I would probably sketch out the example array and draw lines between the elements. I might also draw them as a 2D bar graph - horizontal axis being position in input array and vertical axis being value.</li> <li>I had a hunch this would show a pattern, but no paper to hand. I think the diagram would make it obvious. Thinking about it carefully, I could see that the lines would not overlap arbitrarily, but would only nest.</li> <li>Around this point, it occurred to me that this is incredibly similar to the algorithm Python uses internally to transform indentation into INDENT and DEDENT virtual tokens, which I'd read about before. See "How does the compiler parse the indentation?" on this page: <a href="http://www.secnetix.de/olli/Python/block_indentation.hawk">http://www.secnetix.de/olli/Python/block_indentation.hawk</a> However, it wasn't until I actually worked out an algorithm that I followed up on this thought and determined that it was in fact the same, so I don't think it helped too much. Still, if you can see a similarity to some other problem you know, it's probably a good idea to mention it, and say how it's similar and how it's different.</li> <li>From here the general shape of the stack-based algorithm became apparent, but I still needed to think about it a bit more to be sure it would work okay for those elements that have no subsequent smaller element.</li> </ul> <p>Even if you don't come up with a working algorithm, try to let your interviewer see what you're thinking about. Often it is the thought process more than the answer that they're interested in. For a tough problem, failing to find the best solution but showing insight into the problem can be better than knowing a canned answer but not being able to give it much analysis.</p>

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