1. Min Max Stacks Construction
Python
# Feel free to add new properties and methods to the class.
class MinMaxStack:
def __init__(self):
self.minMaxStack = [] # to hold min, max value at any given value in the stack
self.stack = [] ## hold an empty list
## O(1) time | O(1) space
## peak is used to return the value of the end of the list or the array
def peek(self):
return self.stack[len(self.stack) - 1]
## grab the last element of an array
## ** if you use a linked list, you can just need to grap the tail of the linked list
## O(1) time | O(1) space
## pop a value of the stack
def pop(self):
self.minMaxStack.pop()
return self.stack.pop()
## ** if we're dealing with the linked list, we just need to remove the tail of the link list
## O(1) time | O(N) space
def push(self, number):
'''
First, we want to update the min and max of the minMaxStack
'''
newMinMax = {"min": number, "max": number}
## if minMaxStack is not empty
if len(self.minMaxStack):
lastMinMax = self.minMaxStack[len(self.minMaxStack) - 1] # lastMinMax{"min":x, "max":y}
newMinMax["min"] = min(lastMinMax["min"], number)
newMinMax["max"] = max(lastMinMax["max"], number)
self.minMaxStack.append(newMinMax)
self.stack.append(number)
## O(1) time | O(N) space
def getMin(self):
# Write your code here.
return self.minMaxStack[len(self.minMaxStack) - 1]["min"]
## O(1) time | O(N) space
def getMax(self):
# Write your code here.
return self.minMaxStack[len(self.minMaxStack) - 1]["max"]
stack = MinMaxStack()
print("push 5 into the array")
stack.push(5)
print(stack.getMin())
print(stack.getMax())
print(stack.peek())
print("push 7 into the array")
stack.push(7)
print(stack.getMin())
print(stack.getMax())
print(stack.peek())
print("push 2 into the array")
stack.push(2)
print(stack.getMin())
print(stack.getMax())
print(stack.peek())
'''
Correct output:
push 5 into the array
5
5
5
push 7 into the array
5
7
7
push 2 into the array
2
7
2
'''
2. Balanced_Brackets
Python
def balancedBrackets(string):
# if the length of the string is odd, then returns Flase
openingBrackets = "{(["
closingBrackets = "})]"
matchingBrackets = {"}": "{", ")": "(", "]": "["}
balanced_stack = []
for char in string:
if char in openingBrackets:
balanced_stack.append(char)
elif char in closingBrackets:
if len(balanced_stack) == 0:
return False
if balanced_stack[-1] == matchingBrackets[char]:
balanced_stack.pop()
else:
return False
else:
continue
return len(balanced_stack) == 0
print(balancedBrackets("([])(){}(())()()"))
## True
print(balancedBrackets("{}gawgw()"))
## True
print(balancedBrackets("()[]{}{"))
## False
print(balancedBrackets(")[]}"))
## False
3. Sunset View
Python
## the firsr method is to go from the sun.
## if the sun in the right, which means EAST, we go from right to left
## if the sun in the left, which means WEST, we go from left to right
## O(N) time | 0(N) Space because we may store all the buildings
def sunsetViews(buildings, direction):
# Write your code here.
maxbuilding = []
if direction == "EAST":
for buildingidx in range(len(buildings)-1, -1, -1):
print(buildingidx,len(buildings), maxbuilding)
if buildingidx == len(buildings)-1:
maxbuilding.append(buildingidx)
continue
if buildings[maxbuilding[-1]] < buildings[buildingidx]:
maxbuilding.append(buildingidx)
elif direction == "WEST":
for buildingidx in range(len(buildings)):
print(buildingidx,len(buildings), maxbuilding)
if buildingidx == 0:
maxbuilding.append(buildingidx)
continue
if buildings[maxbuilding[-1]] < buildings[buildingidx]:
maxbuilding.append(buildingidx)
return sorted(maxbuilding)
## -----------------------------------------------------------------
# O(N) time | O(N) space
# using Stack
def sunsetViews(buildings, direction):
candidateBuildingStack = []
startIdx = 0 if direction == "EAST" else len(buildings) -1
step = 1 if direction == "EAST" else -1
idx = startIdx
while idx >= 0 and idx < len(buildings):
buildingHeight = buildings[idx]
while len(candidateBuildingStack) > 0 and buildingHeight >= buildings[candidateBuildingStack[-1]]:
candidateBuildingStack.pop()
candidateBuildingStack.append(idx)
idx += step
if direction == "WEST":
return candidateBuildingStack[::-1]
return candidateBuildingStack
buildings = [3,5,4,4,3,1,3,2]
direction = "EAST"
print(sunsetViews(buildings, direction))
# {"buildings": [3, 5, 4, 4, 3, 1, 3, 2], "direction": "EAST"}
# [1, 3, 6, 7]
# {"buildings": [3, 5, 4, 4, 3, 1, 3, 2], "direction": "WEST"}
# [0, 1]
4. Shorten Path
Python
# O[N] time | O(N) space
def shortenPath(path):
startsWithSlash = path[0] == "/"
tokens = filter(isImportantToken,path.split("/"))
stack = []
if startsWithSlash:
stack.append("")
for token in tokens:
if token == "..":
if len(stack) == 0 or stack[-1] == "..": # this point is important: stack[-1] == ".."
stack.append(token)
elif stack[-1] != "":
stack.pop()
else:
stack.append(token)
if len(stack) == 1 and stack[0] == "": # if were dealing with a root path
return "/"
return "/".join(stack)
def isImportantToken(token):
return len(token) > 0 and token != "."
