K-th greater element (a streaming-like algorithm)
Intuition\n Describe your first thoughts on how to solve this problem. \n\nFinding the K-th greater element doesn\'t require looking up all of the remaining val
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nFinding the K-th greater element doesn\'t require looking up all of the remaining values. For example, if we have seen\n\n```python3\n1, 2, 3\n```\n\n, we don\'t have to continue looking for the numbers to determine the second greater element for `1`.\n\n(But we could improve the time complexity if we look up more elements, as seen in other answers).\n\nWhen a new element comes in, we want to determine if this element is greater than any element previously seen. In fact, we only care about elements that are previously seen AND **smaller** than the current element. \n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nUse a priority queue to store the elements that we haven\'t found the k-th greater element. We record the count of greater elements for every element so that we can determine the answer.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\nEach element is pushed into and popped out of the heap `k` times, respectively, so the complexity is $$O(k * NlogN)$$.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n$$O(N)$$ for storing elements that we haven\'t found the k-th greater element.\n\n# Code\n```python3 []\nclass Solution:\n    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n        ans = [-1] * len(nums)\n        pq = []\n        K = 2\n\n        for i, curr in enumerate(nums):\n            buffer = []\n            while len(pq) > 0 and pq[0][0] < curr:\n                prev, count, j = heappop(pq)\n                if count + 1 < K:\n                    buffer.append((prev, count+1, j))\n                else:\n                    ans[j] = curr\n\n            heappush(pq, (curr, 0, i))\n            for pair in buffer:\n                heappush(pq, pair)\n\n        return ans\n```
['Heap (Priority Queue)', 'Python3']