Commit389f215

connoralydon

committed

added solution for 496-Next-Greater-Element-I.python using both the O(n+m) and O(n*m)

1 parent82e9776 commit389f215Copy full SHA for 389f215

File tree

+37

-0

lines changed

+37

-0

lines changed

Lines changed: 37 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,37 @@`
	`1`	`+class Solution:`
	`2`	`+ def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:`
	`3`	`+`
	`4`	`+ # O (n + m)`
	`5`	`+ nums1Idx = { n:i for i, n in enumerate(nums1) }`
	`6`	`+ res = [-1] * len(nums1)`
	`7`	`+`
	`8`	`+ stack = []`
	`9`	`+ for i in range(len(nums2)):`
	`10`	`+ cur = nums2[i]`
	`11`	`+`
	`12`	`+ # while stack exists and current is greater than the top of the stack`
	`13`	`+ while stack and cur > stack[-1]:`
	`14`	`+ val = stack.pop() # take top val`
	`15`	`+ idx = nums1Idx[val]`
	`16`	`+ res[idx] = cur`
	`17`	`+`
	`18`	`+ if cur in nums1Idx:`
	`19`	`+ stack.append(cur)`
	`20`	`+`
	`21`	`+ return res`
	`22`	`+`
	`23`	`+`
	`24`	`+ # O (n * m)`
	`25`	`+ nums1Idx = { n:i for i, n in enumerate(nums1) }`
	`26`	`+ res = [-1] * len(nums1)`
	`27`	`+`
	`28`	`+ for i in range(len(nums2)):`
	`29`	`+ if nums2[i] not in nums1Idx:`
	`30`	`+ continue`
	`31`	`+ for j in range(i + 1, len(nums2)):`
	`32`	`+ if nums2[j] > nums2[i]:`
	`33`	`+ idx = nums1Idx[nums2[i]]`
	`34`	`+ res[idx] = nums2[j]`
	`35`	`+ break`
	`36`	`+`
	`37`	`+ return res`

Comments

(0)