[Java/Python3] The Kth Greater Element Solution | Linked List
Intuition\n\nFirst, try to solve it with monotonic stack.\nBut for this time, we can\'t directly pop the top element from the stack while encountering a greater
## Intuition\n\nFirst, try to solve it with monotonic stack.\nBut for this time, we can\'t directly pop the top element from the stack while encountering a greater element. Instead, we need to keep a state: **how many greater elements does the top element in the stack encounter?**\n\nThere are two cases:\n1. ``nums[i] <= the top element in the stack``: Push ``[i(index), nums[i](value), 0(count)]`` to the stack.\n2. ``nums[i] > the top element in the stack``:\n\t(1) Increment ``count`` of the element by 1.\n\t(2) If there are 2 next greater elements(``count==2``), then pop it from the stack and set the second greater element(``nums[i]``) for it.\n\tOtherwise, continue to check the next element in the stack until we encounter an element greater than or equal to ``nums[i]``(case 1).\n\t\nYou may ask where to push ``[i(index), nums[i](value), 0(count)]`` for the case 2.\nBecause we want the stack to be a **non-increasing** array, add the item ``[i(index), nums[i](value), 0(count)]`` to the right position in the stack. The time complexity of inserting an item into an array is ``O(n)`` and that\'s inefficient. So, we can try a **linked list** instead.\n\n## Implementation\n\n**Java**\n```\npublic class ListNode {\n    int idx;\n    int val;\n    int count;\n    ListNode next;\n    ListNode() {}\n    ListNode(int idx, int val, int count, ListNode next) {\n        this.idx = idx;\n        this.val = val;\n        this.count = count;\n        this.next = next;\n    }\n}\n\nclass Solution {\n    public int[] secondGreaterElement(int[] nums) {\n        int[] result = new int[nums.length];\n        Arrays.fill(result, -1);\n        ListNode head = new ListNode();\n        ListNode prev, cur;\n        for (int i = 0; i < nums.length; ++i) {\n            prev = head;\n            cur = head.next;\n            while (cur != null && nums[i] > cur.val) {\n                ++cur.count;\n                if (cur.count == 2) {\n                    result[cur.idx] = nums[i]; // set second greater element nums[i] for cur.idx\n                    prev.next = cur.next; // remove cur from the linked list\n                } else {\n                    prev = cur;\n                }\n                cur = cur.next;\n            }\n            prev.next = new ListNode(i, nums[i], 0, cur); // insert cur to the linked list\n        }\n        return result;\n    }\n}\n```\n\n**Python3**\n```\nclass ListNode:\n    def __init__(self, idx=-1, val=-1, count=0, next=None):\n        self.idx = idx\n        self.val = val\n        self.count = count\n        self.next = next\n\nclass Solution:\n    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n        result = [-1] * len(nums)\n        head = ListNode()\n        for i, num in enumerate(nums):\n            prev, cur = head, head.next\n            while cur and num > cur.val:\n                cur.count += 1\n                if cur.count == 2:\n                    result[cur.idx] = num # set second greater element nums[i] for cur.idx\n                    prev.next = cur.next # remove cur from the linked list\n                else:\n                    prev = cur\n                cur = cur.next\n            prev.next = ListNode(i, num, 0, cur) # insert cur to the linked list\n        return result\n```\n\n**Complexity Analysis**\nNote: ``n`` is the length of the input array ``nums``.\n\n* Time complexity: ``O(n)``. **Each node is processed at most twice** because when ``count == 2``, that node will be removed from the linked list. So, the overall complexity is ``O(2n)``. That is, ``O(n)``.\n* Space complexity: ``O(n)``. If ``nums`` is a decreasing array, then the linked list will contain ``n`` nodes.\n\n---\n\n## Bonus\n\nWe can do a little modification to make a generalized solution: **the Kth Greater Element Solution** from the above implementation.\n\n**The Kth Greater Element Solution**\n```\nclass ListNode:\n    def __init__(self, idx=-1, val=-1, count=0, next=None):\n        self.idx = idx\n        self.val = val\n        self.count = count\n        self.next = next\n\nclass Solution:\n    def kthGreaterElement(self, nums: List[int], k: int) -> List[int]:\n        result = [-1] * len(nums)\n        head = ListNode()\n        for i, num in enumerate(nums):\n            prev, cur = head, head.next\n            while cur and num > cur.val:\n                cur.count += 1\n                if cur.count == k:\n                    result[cur.idx] = num # set the kth greater element nums[i] for cur.idx\n                    prev.next = cur.next # remove cur from the linked list\n                else:\n                    prev = cur\n                cur = cur.next\n            prev.next = ListNode(i, num, 0, cur) # insert cur to the linked list\n        return result\n```\n\n**Complexity Analysis**\nNote: ``n`` is the length of the input array ``nums``.\n\n* Time complexity: ``O(kn)``. **Each node is processed at most k times** because when ``count == k``, that node will be removed from the linked list. So, the overall complexity is ``O(kn)``.\n* Space complexity: ``O(n)``.
['Linked List', 'Python', 'Java']