Python-time & space - O(n) New interesting solution using hashmap w/thought process & explanation
I came with a solution that is a good candidate to be considered as a new approach. At least it would definitely help train our mind to think of data structures
I came with a solution that is a good candidate to be considered as a new approach. At least it would definitely help train our mind to think of data structures in ingenious ways at least for practice and training. So here goes.\n\nMy thought process started with finding the largest element (if many, then the last such element) and its index (assume max_el_idx), because from then I can start setting the next greater element for all by iterating to the left starting with max_el_idx - 1. So for max_el_idx will have the max_val as the greater element w/o doubt. Then for any new element the options are the prev_element or any one of the prev_elements\' greater elements. For example, [.... 10, 7, 9, 11....] subarray, when 10 is reached while iterating to the left, these are the answers 7 -> 9,  9 -> 11 , 11-> NA ... So for 10 , the prev element 7 is lesser so we go through the links of 7 to see where 10 would find its greater element and it will be in 9-> 11. And we will not be going through this link again (i.e. 7 to 11 ) because the subsequent numbers if they are smaller will have 10 as answer, if not then we go to the greater element of 10 and then keep linking up from there. And overall we will not be having more than O(n) ops for the linking checks as well. So we can find the greater element for entire array in O(n) itself.\n ```\n[.... 12, 10 -> 7 -> 9 -> 11....]\n       |--->|-------->------^ (proceeds to search after 11)\n```\n\nNote: I know that if we break it down into fundamentals then it might have a resemblance to the stack strategy, but the thought process I think is a bit different.\n\nLet me know what you think..\n```\ndef nextGreaterElements(self, nums: List[int]) -> List[int]:\n    max_el_idx = max_val = -2<<31\n    for i, val in enumerate(nums):\n        if val >= max_val:\n            max_el_idx = i; max_val = val\n    ite = max_el_idx-1; prev_el = max_val\n    res =[-1 for i in range(len(nums))]\n    hm={}\n    while len(nums) + ite != max_el_idx:\n        if nums[ite] != max_val:\n            if nums[ite] < prev_el:\n                hm[nums[ite]] = res[ite] = prev_el\n            else:\n                while prev_el<=nums[ite]:\n                    prev_el = hm[prev_el]\n                hm[nums[ite]] = res[ite] = prev_el\n        prev_el = nums[ite]\n        ite-=1\n    return res\n```\nI have used hashmap to store the greater element for the prev element and that is used to chain through till the greatest element to find out where the greater element for the current element stands.\nTime complexity - O(n)\nSpace complexity - O(n) for the hashmap
['Python', 'Python3']