Stacks

08 Sep, 2024

1. Next Greater Element I

   iterate through nums1 to create a hashmap such that the key is the value present in nums1 and its value is the index of the value from nums1

   nums1_index = {n:i for i,n in enumerate(nums1)}
   

   one pass solution using stack iterate through nums2 and compare it to the topmost value of the stack. notice how the elements pushed into the stack are always going to be in a decreasing order this concept is called as Monotonic Decreasing Stack;

   Here's a pretty comprehensive guide on solving problems involving monotonic stacks

   because of this when we compare it to the top most element of the stack we wont just stop there. we will compare it with all the elements of the stack as long as the value being compared from nums2 is greater and the stack isnt empty.

   res = [-1] * len(nums1)
   stack = []
   for i in range(len(nums2)):
       cur = nums2[i]
       # now we check if the current value is our next biggest value
       while stack and cur > stack[-1]:
       	# this is the next biggest value 
       	val = stack.pop()
       	# now we know that cur is the next biggest element of this value
       	# so we need to get the index of this val from our hashmap and have cur inserted at that index in our output res
       	idx = nums1_index[val]
       	res[idx] = cur
       if cur in nums1_index:
       	stack.append(cur)
   return res
   

   Time Complexity : O(m + n)

   Space Complexity : O(m)

   m -> size of the first array nums1

   n -> size of the second array nums2

   ---

2. Car Fleet

   The essence of this question lies in the calculation of "car fleets" which in truly unambiguous terms translates to identifying if the given list of cars intersect i.e previous cars arrive at the destination before the latest car. Since the ordering of cars is important here it clearly indicates that we have to sort the array (based on the position) Now the next remotely tricky aspect is to find if or not they intersect. Now this can be done by finding out when the said car reaches the destination. cars = [A,B,C] (sorted based on their position) Now if B reaches the destination before C, they intersect i.e form a car fleet. Another tricky aspect is to understand how to proceed form here. We always need to consider the car taking the max time to reach the destination when two cars end up intersecting for future comparisons. This is because when these two cars intersect (read:collide), the new speed post collision is going to be the speed of the slow moving car( again we're treading on ambiguous lines here - remember i used 'slow' moving car i.e the car that takes the max time to reach the destination irrespective of the absolute speed it was moving at). Thus, cars = [A,C] Ultimately the total number of intersections would be the length of our stack i.e cars in my example above. Another key thing to remember is that it is important to traverse right to left as that would give us an understanding of what happens to the intermediate cars.

def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:

	pair = [(p,s) for p, s in zip(position, speed)] # this would create pairs of position, speed for each car
	stack = []
	for p,s in sorted(pair)[::-1]: #traversing in reverse
		time = (target - p) / s
		stack.append(time)
		if len(stack) >= 2 and stack[-1] <= stack[-2]: 
		# always need to compare two cars
		# this is the condition check to identify if the previous/earlier car i.e entry at stack[-1] reaches the destination faster than the latest car i.e the car at stack[-2] then these two cars intersect/collide
			stack.pop()
	return len(stack)	

Time Complexity : O(nlogn) -> need to sort + one pass of array

Space Complexity : O(n) -> Worst case scenario could involve storing the entire array in the stack