We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This problem uses a rather peculiar trick with a stack that isn't at all intuitive and you're likely not to have seen before.
Suppose you have an array A and you want to know every pair of smallest integers for each subarray (i.e. given a subarray, you want the smallest integer and the second smallest integer, where a subarray is a contiguous subset of the original array).
This can be done in linear time using a stack. Here's the pseudocode ('yield' means a pair of smallest integers for some subarray has been found):
For each int i in the array A
while stack is nonempty
yield (i, top of stack)
if i is less than the top of the stack, pop the stack
otherwise break the while loop
push i onto stack
The idea is that if you have a value b in your stack, and you encounter a value c which is smaller, then b cannot form a minimum pair with anything to the right of c. So once you yield the pair (b,c) you can safely dispose of b (you already handled possible pairs to the left).
This is the main subroutine for solving this problem, but I'll leave that to you.
AND xor OR
You are viewing a single comment's thread. Return to all comments →
This problem uses a rather peculiar trick with a stack that isn't at all intuitive and you're likely not to have seen before.
Suppose you have an array A and you want to know every pair of smallest integers for each subarray (i.e. given a subarray, you want the smallest integer and the second smallest integer, where a subarray is a contiguous subset of the original array).
This can be done in linear time using a stack. Here's the pseudocode ('yield' means a pair of smallest integers for some subarray has been found):
The idea is that if you have a value b in your stack, and you encounter a value c which is smaller, then b cannot form a minimum pair with anything to the right of c. So once you yield the pair (b,c) you can safely dispose of b (you already handled possible pairs to the left).
This is the main subroutine for solving this problem, but I'll leave that to you.