We are stacking blocks to form a pyramid.  Each block has a color which is a one letter string, like `'Z'`.

For every block of color `C` we place not in the bottom row, we are placing it on top of a left block of color `A` and right block of color `B`.  We are allowed to place the block there only if `(A, B, C)` is an allowed triple.

We start with a bottom row of bottom, represented as a single string.  We also start with a list of allowed triples allowed.  Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.


Example 1:

Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
    A
   / \
  D   E
 / \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.



Example 2:

Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
Output: false
Explanation:
We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.



Note:

bottom will be a string with length in range [2, 8].
allowed will have length in range [0, 200].
Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.

Difficulty: interview

Starter code:

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        

Solutions:
import heapq
 class Solution(object):
     def pourWater(self, heights, V, K):
         """
         :type heights: List[int]
         :type V: int
         :type K: int
         :rtype: List[int]
         """
 
         heap = []
         heapq.heappush(heap, (heights[K], -1, 0))
         l, r = K - 1, K + 1
         lh, rh = [], []
 
         for i in range(V):
             while l >= 0 and heights[l] <= heights[l + 1]:
                 heapq.heappush(lh, (heights[l], -l))
                 l -= 1
 
             while r < len(heights) and heights[r] <= heights[r - 1]:
                 heapq.heappush(rh, (heights[r], r))
                 r += 1
 
             if lh and lh[0][0] < heights[K]:
                 h, i = heapq.heappop(lh)
                 heights[-i] += 1
                 heapq.heappush(lh, (h + 1, i))
                 continue
 
             if rh and rh[0][0] < heights[K]:
                 h, i = heapq.heappop(rh)
                 heights[i] += 1
                 heapq.heappush(rh, (h + 1, i))
                 continue
 
             heights[K] += 1
 
         return heights


class Solution:
     def pourWater(self, heights, V, K):
         """
         :type heights: List[int]
         :type V: int
         :type K: int
         :rtype: List[int]
         """
         
         for i in range(V):
             if not self.fallLeft(K, heights):
                 if not self.fallRight(K, heights):
                     heights[K] += 1
         
         return heights
     
     def fallLeft(self,K, heights):
         minBlock = K
         for i in range(K-1, -1, -1):
             if heights[i] < heights[minBlock]:
                 minBlock = i
             elif heights[i] > heights[minBlock]:
                 break
         if minBlock == K:
             return False
         heights[minBlock] += 1
         return True
         
     
     def fallRight(self,K, heights):
         minBlock = K
         for i in range(K+1, len(heights)):
             if heights[i] < heights[minBlock]:
                 minBlock = i
             elif heights[i] > heights[minBlock]:
                 break
         if minBlock == K:
             return False
         heights[minBlock] += 1
         return True

class Solution:
     def pourWater(self, heights, total, index):
         """
         :type heights: List[int]
         :type V: int
         :type K: int
         :rtype: List[int]
         """
         
         if not heights or total <= 0 or index < 0 or index >= len(heights):
             return heights
         
         for _ in range(total):
             left = -1
             for i in range(index-1, -1, -1):
                 if heights[i] > heights[i+1]:
                     break
                     
                 if heights[i] < heights[i+1]:
                     left = i
             
             if left != -1:
                 heights[left] += 1
                 continue
                 
             right = -1
             for j in range(index+1, len(heights)):
                 if heights[j] > heights[j-1]:
                     break
                     
                 if heights[j] < heights[j-1]:
                     right = j
                     
             if right != -1:
                 heights[right] += 1
                 continue
                 
             heights[index] += 1
             
         return heights
                     


from queue import PriorityQueue
 class Solution(object):
     def pourWater(self, heights, V, K):
         """
         :type heights: List[int]
         :type V: int
         :type K: int
         :rtype: List[int]
         """
         i = 0
         while i < V:
             l_i = K-1
             at = K
             while l_i>=0 and heights[l_i] <= heights[at]:
                 if heights[l_i] < heights[at]:
                     at = l_i
                 l_i-=1
             if at != K:
                 heights[at] +=1
                 i+=1
                 continue
             r_i = K+1
             while r_i < len(heights) and heights[r_i] <= heights[at]:
                 if heights[r_i] < heights[at]:
                     at = r_i
                 r_i+=1
             if at != K:
                 heights[at] +=1
                 i+=1
                 continue
             heights[K] += 1
             i+=1
         return heights
             
             
                 
             

class Solution:
     def pourWater(self, heights, V, K):
         """
         :type heights: List[int]
         :type V: int
         :type K: int
         :rtype: List[int]
         """
         
         for i in range(V):
             if not self.fallLeft(K, heights):
                 if not self.fallRight(K, heights):
                     heights[K] += 1
         
         return heights
     
     def fallLeft(self,K, heights):
         minBlock = K
         for i in range(K-1, -1, -1):
             if heights[i] < heights[minBlock]:
                 minBlock = i
             elif heights[i] > heights[minBlock]:
                 break
         if minBlock == K:
             return False
         heights[minBlock] += 1
         return True
         
     
     def fallRight(self,K, heights):
         minBlock = K
         for i in range(K+1, len(heights)):
             if heights[i] < heights[minBlock]:
                 minBlock = i
             elif heights[i] > heights[minBlock]:
                 break
         if minBlock == K:
             return False
         heights[minBlock] += 1
         return True