Skip to main content

Random Questions

1161 Maximum level sum of a binary tree​

from collections import deque
class TreeNode:
  def __init__(self, val = 0, left = None, right = None):
    self.val = val
    self.left = left
    self.right = right

def maxLevelSum(root):
  res = [0, float('-inf')] # [level, sum]

  deck = deque([root])
  curr_level = 0

  while deck:
    level_sum = 0
    curr_level += 1
    for _ in range(len(deck)):
      curr = deck.popleft()

      if curr.left:
        deck.append(curr.left)
      if curr.right:
        deck.append(curr.right)
      
      level_sum += curr.val
    if res[1] < level_sum:
      res = [curr_level, level_sum]
  return res[0]

1975 Maximum Matrix Sum​

The key is to realize you can move any single negative signs around the matrix using the flipping method. If the total number of negatives are even, you can cancel all the negatives by moving them into pairs. If the total number of negatives are odd, you can move the signs to the smallest element and pair other elements off. In the end, we subtract 2 * smallest because there's two smallest element in the total(it was the sum of all elements).

def maxMatrixSum(matrix):
  neg_count = 0
  smallest = float('inf')
  total = 0

  for row in matrix:
    for elem in row:
      if elem < 0:
        neg_count += 1
      abs_elem = abs(elem)
      smallest = min(smallest, abs_elem)
      total += abs_elem
  
  if neg_count % 2 == 0:
    return total
  else:
    return total - 2 * smallest