Misc. Leetcode

March 02, 2021

Leetcode problems using non-tradtional algorithms.

53. Maximum Subarray (Kadane’s Algorithm)

I: nums = [-2,1,-3,4,-1,2,1,-5,4]
O: 6

• We initialize a best and a curr variable
  • best tracks our max subarray sum (the goal)
    • we set it to something BIG negative number (-inf) as a base to account for an array of all negative numbers
  • curr is our running total we’re checking again our best number
• Next, we iterate over the array and set:
  • curr equal to the max of the current number n we’re assessing of the curr plus n
    • we’re deciding between whether we’re going to extend our window or starting a new window at this current index
      • said another way, if curr plus the next n is greater than said n itself we extended
      • if not, that n is our new starting point
  • then we’ll look at the curr sum that comes out of that assessment and compare it against our running best, the max between those two is returned
• once we’ve iterated through the entire array, we return the last best

def maxSubArray(self, nums: List[int]) -> int:
  best = float('-inf')
  curr = 0

  for n in nums:
    curr = max(n,curr+n)
    best = max(best,curr)
  return best

268. Missing Number

I: nums = [3,0,1]
O: 2

• Create a dictionary to store every item in our given nums array
  • we’ll set the key/value pairs to the same passed number
• Next we’ll iterate of the length of the nums array
  • we add 1 because we’re including that last i as well
    • “it’s inclusive of 0 to n”
• In each loop, we check if each i is contained within our dictionary (d)
  • if so, we continue
  • if not, that’s our missing number and we return it

def missingNumber(self, nums: List[int]) -> int:
  d = {i:i for i in nums}

  for i in range(len(nums)+1):
    if i in d:
      continue
    else:
      return i

Version 2 - Gauss’s Sum (constant space)

I: nums = [3,0,1]
O: 2

• We will assess two variables:
  • exp: is our expected sum of all the numbers in that range, we’ll use the Gauss’s Sum
    • this will give us the sum of all the consecutive numbers in that array’s length
  • act: is the actual sum of our nums array
• Take the difference between our exepected sum and our actual sum to give us the difference
  • that difference IS the n we’re missing

def missingNumber(self, nums: List[int]) -> int:
  n = len(nums)
  exp = int(n * (n+1) / 2)
  act = sum(nums)

  return (exp-act)

Written by Christian Turner
Follow me on Twitter

• ← Trees
• Strings →