Solutions

Powers - Binary Exponentiation

Explanation: https://www.youtube.com/watch?v=L-Wzglnm4dM

def myPow(self, x: float, n: int) -> float:
  if n < 0:
    x = 1/x
    n = abs(n)

  result = 1
  while n > 0:
    if n % 2 == 1:
      result *= x
    x *= x
    n //= 2
  return result > self.myPow(2.0, 10)
> 1024.0
> self.myPow(2.0, -2)
> 0.25

Count Palindroms in string

def countSubstrings(self, s: str) -> int:
  def expand(left: int, right: int) -> int:
    count = 0
    while left >= 0 and right < len(s) and s[left] == s[right]:
      # count the palindrome and expand outward
      count += 1
      left -= 1
      right += 1
    return count

  palindromes = 0
  for i in range(len(s)):
    # the idea is to expand around the 'center' of the string, but the center could be 1 or 2 letters
  # e.g., babab and cbbd, hence the (i, i) and (i, i + 1)
    palindromes += expand(i, i)
    palindromes += expand(i, i + 1)
  return palindromes

Validate Binary Search Tree

Recursive

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def validate(node, low=-math.inf, high=math.inf):
          # Empty trees are valid BSTs
          if not node:
            return True

          # The current nodes val must be between the high and low to be valid
          if node.val <= low or node.val >= high:
            return False

          # The left and right subtrees must also be valid
          return (validate(node.left, low, node.val) and validate(node.right, node.val, high))

        return validate(root)

Arrays

Slinding Window

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    used = {}
    max_len = start = 0
    for i, c in enumerate(s):
      if c in used and start <= used[c]:
        start = used[c] + 1
      else:
        max_len = max(max_len, i - start + 1)
      used[c] = i

    return max_len

3 Sum Solution

def threeSum(self, nums: List[int]) -> List[List[int]]:

    res = set()

    #1. Split nums into three lists: negative numbers, positive numbers, and zeros
    n, p, z = [], [], []
    for num in nums:
        if num > 0:
            p.append(num)
        elif num < 0: 
            n.append(num)
        else:
            z.append(num)

    #2. Create a separate set for negatives and positives for O(1) look-up times
    N, P = set(n), set(p)

    #3. If there is at least 1 zero in the list, add all cases where -num exists in N and num exists in P
    #   i.e. (-3, 0, 3) = 0
    if z:
        for num in P:
            if -1*num in N:
                res.add((-1*num, 0, num))

    #3. If there are at least 3 zeros in the list then also include (0, 0, 0) = 0
    if len(z) >= 3:
        res.add((0,0,0))

    #4. For all pairs of negative numbers (-3, -1), check to see if their complement (4)
    #   exists in the positive number set
    for i in range(len(n)):
        for j in range(i+1,len(n)):
            target = -1*(n[i]+n[j])
            if target in P:
                res.add(tuple(sorted([n[i],n[j],target])))

    #5. For all pairs of positive numbers (1, 1), check to see if their complement (-2)
    #   exists in the negative number set
    for i in range(len(p)):
        for j in range(i+1,len(p)):
            target = -1*(p[i]+p[j])
            if target in N:
                res.add(tuple(sorted([p[i],p[j],target])))

    return res

Remove Duplicates

class Solution:
  def removeDuplicates(self, nums: List[int]) -> int:

    i = 0
    for j in range(1, len(nums)):
      if nums[i] != nums[j]:
        i += 1
        nums[i] = nums[j]

    return i+1

Multiply

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0':
            return '0'

        def decode(num):
            ans = 0
            for i in num:
                ans = ans*10 +(ord(i) - ord('0'))
            return ans

        def encode(s):
            news = ''
            while s:
                a = s % 10
                s = s // 10
                news = chr(ord('0') + a) + news
            return news

        return encode(decode(num1)*decode(num2))

Group Anagrams

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    groups = {}

    for s in strs:
      ss = tuple(sorted(s))
      if ss in groups:
        curr = groups[ss]
        curr.append(s)
        groups[ss] = curr
      else: 
        groups[ss] = [s]

    list = []
    for value in groups.values():
      list.append(value)

    return list

Trapping Rain Water

class Solution:
    def trap(self, height: List[int]) -> int:

      maxLeft = 0
      maxRight = 0
      waterLevel = []
      for h in height:
        maxLeft = max(maxLeft, h)
        waterLevel.append(maxLeft)

      for idx, h in reversed(list(enumerate(height))):
        maxRight = max(maxRight, h)
        minWater = min(waterLevel[idx], maxRight)
        waterLevel[idx] = minWater - h

      return sum(waterLevel)

Find if Path Exists in Graph

class Solution:
    def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:

      visited, queue = set(), deque()
      valid = False

      graph = defaultdict(list) 
      for edge in edges:
        src, dest = edge
        graph[src].append(dest)
        graph[dest].append(src)

      queue.append(start)

      while queue:
        vertex = queue.popleft()

        if vertex not in visited:
          visited.add(vertex)

          if vertex == end:
            valid = True
            break

          queue.extend(graph[vertex])

      return valid