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.
I followed the pseudo-algorithm exactly.
Is this correct intuition...?
-> For e.g. A=[4,5,3,7] yields => (i,top): (5,4);(3,5);(3,4);(7,3), which are the only contiguous pairs of two smallest elements. Note, for example, (4,7) is impossible, because that includes all of A => (3,4). [see below] New smaller elements pop out earlier (contiguously) elements, such as 3 popping 5 and 4.
-> Loop through A linearly.
-> When to push and pop to the stack? Push to the stack each new element in A, i, and if i is smaller than stack top, keep popping until all bigger earlier values popped (or stack empty) before adding i. This way any new smaller element pops all previous bigger elements, and the stack keeps pushing new elements when empty - always having a new pair (at least one element in non-empty stack and new element i).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
AND xor OR
You are viewing a single comment's thread. Return to all comments →
This is correct, here's a Python implementation:
I followed the pseudo-algorithm exactly. Is this correct intuition...?
-> For e.g. A=[4,5,3,7] yields => (i,top): (5,4);(3,5);(3,4);(7,3), which are the only contiguous pairs of two smallest elements. Note, for example, (4,7) is impossible, because that includes all of A => (3,4). [see below] New smaller elements pop out earlier (contiguously) elements, such as 3 popping 5 and 4.
-> Loop through A linearly.
-> When to push and pop to the stack? Push to the stack each new element in A, i, and if i is smaller than stack top, keep popping until all bigger earlier values popped (or stack empty) before adding i. This way any new smaller element pops all previous bigger elements, and the stack keeps pushing new elements when empty - always having a new pair (at least one element in non-empty stack and new element i).