DP & Two pointers

[JinJinQuant]

Difficulty	Category	Problem	Number
Easy	Two Pointers	Merge Sorted Array	1
Easy	Two Pointers	Remove Duplicates from Sorted Array	1
Medium	Two Pointers	3Sum	1
Medium	Two Pointers	Longest Palindromic Substring	1
Easy	Two Pointers	Move Zeroes	1
Medium	Two Pointers	Container With Most Water	1
Hard	Two Pointers	Trapping Rain Water	1
Medium	Two Pointers	Interval List Intersections	2
Easy	Two Pointers	Count Pairs Whose Sum is Less than Target	2
Medium	Two Pointers	Number of Substrings Containing All Three Characters	2
Easy	Two Pointers	Sort Array By Parity	3
Easy	Two Pointers	Squares of a Sorted Array	3
Medium	Two Pointers	Remove Duplicates from Sorted Array II	3
Easy	Dynamic Programming	(**) Best Time to Buy and Sell Stock	1
Easy	Dynamic Programming	Fibonacci Number	1
Medium	Dynamic Programming	Maximum Subarray	1
Medium	Dynamic Programming	Best Time to Buy and Sell Stock II	1
Easy	Dynamic Programming	Min Cost Climbing Stairs	1
Medium	Dynamic Programming	Maximum Subarray Sum with One Deletion	2
Hard	Dynamic Programming	Best Time to Buy and Sell Stock III	2
Medium	Dynamic Programming	Coin Change	2
Medium	Dynamic Programming	Jump Game	2
Medium	Dynamic Programming	House Robber	2
Medium	Dynamic Programming	Longest Common Subsequence	2
Medium	Dynamic Programming	Unique Paths	2
Medium	Dynamic Programming	Maximum Product Subarray	2
Medium	Dynamic Programming	Longest Arithmetic Subsequence of Given Difference	2
Medium	Dynamic Programming	Coin Change II	2
Medium	Dynamic Programming	Jump Game II	2
Medium	Dynamic Programming	Partition Equal Subset Sum	2
Medium	Dynamic Programming	House Robber II	2
Medium	Dynamic Programming	Minimum Path Sum	2
Medium	Dynamic Programming	Integer Break	2
Medium	Dynamic Programming	Maximum Profit From Trading Stocks	2
Hard	Dynamic Programming	Super Egg Drop	3
Medium	Dynamic Programming	Best Time to Buy and Sell Stock with Transaction Fee	3

[JinJinQuant]

Two pointers algorithm

1. Use two pointers to find the target value by pointing to different elements in a one-dimensional array

2. A brute-force solution with O(n^2) time-complexity can always be optimized to O(n) performance

3. Try the two pointers approach when you want to process elements in a continuous interval or figure out something in a sorted array

4. Two pointers move in the same direction

5. Two pointers move in opposite directions from both ends

6. One pointer moves in one direction only while the other pointer moves in both directions

examples

1. Given an array with N integers, find the number of cases that consecutive numbers sum up to M

[JinJinQuant]

88. Merge Sorted Array

1. Start from the end

   class Solution:
   def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
       """
       Do not return anything, modify nums1 in-place instead.
       """
       p1 = m-1
       p2 = n-1
   
       for p in range(n+m-1, -1, -1):
           if p2 < 0:
               break
           if p1 >= 0 and nums1[p1] > nums2[p2]:
               nums1[p] = nums1[p1]
               p1 -= 1
           else:
               nums1[p] = nums2[p2]
               p2 -= 1

2. Start from the beginning

[JinJinQuant]

26. Remove Duplicates from Sorted Array

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                nums[j] = nums[i]
                j += 1
        return j

[JinJinQuant]

15. 3Sum

It is necessary to review Two Sum

1. Two pointers (O(n))

   
   class Solution:
   def threeSum(self, nums: List[int]) -> List[List[int]]:
       ans = []
       nums.sort()
   
       for i in range(len(nums)):
           if nums[i] > 0:
               break
           if i == 0 or nums[i-1] != nums[i]:
               self.twoSum(nums, i, ans)
       return ans
   
   def twoSum(self, nums, i, ans):
       pl, ph = i+1, len(nums)-1
       while pl < ph:
           s = nums[i] + nums[pl] + nums[ph]
           if s < 0: # -nums[i] > nums[p1] + nums[ph] -> need to increase
               pl += 1
           elif s > 0:
               ph -= 1
           else:
               ans.append([nums[i], nums[pl], nums[ph]])
               pl += 1
               ph -= 1
               while pl < ph and nums[pl] == nums[pl-1]:
                   pl += 1

[JinJinQuant]

121. Best Time to Buy and Sell Stock

'''
Kadane's Algorithm
Kadane's Algorithm is a dynamic programming technique used to find the maximum subarray sum in an array of numbers. The algorithm maintains two variables: max_current represents the maximum sum ending at the current position, and max_global represents the maximum subarray sum encountered so far. At each iteration, it updates max_current to include the current element or start a new subarray if the current element is larger than the accumulated sum. The max_global is updated if max_current surpasses its value.
'''
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = prices[0]
        profit = 0

        for i in range(1, len(prices)):
            if prices[i] < buy:
                buy = prices[i]
            elif prices[i] - buy > profit:
                profit = prices[i] - buy

        return profit

[JinJinQuant]

Saving the answers from the previous stages in a previous step and using them in the current step seems to be key to solve DP problems.

[JinJinQuant]

509. Fibonacci Number

1. DP

   class Solution:
   def fib(self, n: int) -> int:
       if n == 0: return 0
       if n == 1: return 1
       num1, num2 = 0, 1
       for i in range(n-1):
           temp = num2
           num2 = num1 + num2
           num1 = temp
       return num2

2. Characteristic function

   class Solution:
   def fib(self, n: int) -> int:
       return int(5**(-0.5) * (((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n))

[JinJinQuant]

88. Merge Sorted Array

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i = m - 1
        j = n - 1
        k = m + n - 1

        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

[JinJinQuant]

26. Remove Duplicates from Sorted Array

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums) 

        p1 = 0

        for p2 in range(1, len(nums)):
            if nums[p2] > nums[p2 - 1]:
                p1 += 1
                nums[p1] = nums[p2]

        return p1 + 1

[JinJinQuant]

15. 3Sum

• Keep in mind handing duplicates using while loops

  
  class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
      def twoSum(nums, target):
          ans = []
          p1 = 0
          p2 = len(nums) - 1
  
          while p1 < p2:
              sum_ = nums[p1] + nums[p2]
              if sum_ < target:
                  p1 += 1
              elif sum_ > target:
                  p2 -= 1
              else:
                  ans.append([nums[p1], nums[p2]])
                  p1 += 1
                  p2 -= 1
                  while p1 < p2 and nums[p1] == nums[p1 - 1]:
                      p1 += 1
                  while p1 < p2 and nums[p2] == nums[p2 + 1]:
                      p2 -= 1
  
          return ans
  
      nums.sort()
      ans = []
  
      for i in range(len(nums)):
          if i > 0 and nums[i] == nums[i - 1]:
              continue
          pairs = twoSum(nums[i+1:], -nums[i])
          for pair in pairs:
              ans.append([nums[i]] + pair)
  
      return ans

[JinJinQuant]

5. Longest Palindromic Substring

1. Two Pointers

   class Solution:
   def longestPalindrome(self, s: str) -> str:
       if len(s) <= 1:
           return s
   
       def centerExpand(s, pl, pr):
           while pl >= 0 and pr < len(s):
               if s[pl] != s[pr]:
                   break
               pl -= 1
               pr += 1
           return s[pl + 1:pr]
   
       maxStr = s[0]
       for i in range(len(s)):
           oddStr = centerExpand(s, i, i)
           evenStr = centerExpand(s, i, i+1)
   
           if len(oddStr) > len(maxStr):
               maxStr = oddStr
           if len(evenStr) > len(maxStr):
               maxStr = evenStr
   
       return maxStr

2. Dynamic Programming (*)

i) s[start] == s[end] ii) s[start+1 : end-1] is also a palindrome (s[j+1][i-1] == True)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s

        Max_Len=1
        Max_Str=s[0]
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = True
            for j in range(i):
                if s[j] == s[i] and (i-j <= 2 or dp[j+1][i-1]):
                    dp[j][i] = True
                    if i-j+1 > Max_Len:
                        Max_Len = i-j+1
                        Max_Str = s[j:i+1]
        return Max_Str

[JinJinQuant]

283. Move Zeroes

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        p1 = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[p1] = nums[i]
                p1 += 1

        if p1 <= len(nums):
            for i in range(p1, len(nums)):
                nums[i] = 0

[JinJinQuant]

11. Container With Most Water

class Solution:
    def maxArea(self, height: List[int]) -> int:
        p1 = 0
        p2 = len(height) - 1
        maxA = 0

        while p1 < p2:
            maxA = max(maxA, (p2-p1) * min(height[p1], height[p2]))
            if height[p1] < height[p2]:
                p1 += 1
            else:
                p2 -= 1

        return maxA

[JinJinQuant]

42. Trapping Rain Water

• need to find a more efficient way (lower than O(n^2)) later

  1. Brute-Force

     class Solution:
     def trap(self, height: List[int]) -> int:
     n = len(height)
     maxHeight = max(height)
     waterTrapped = 0
     
     for level in range(maxHeight):
         layer = [1 if h - level > 0 else 0 for h in height]
         # find zeros between non zero points
         if sum(layer) <= 1:
             waterLayer = 0
         else:
             left = 0
             while layer[left] == 0:
                 left += 1
             right = len(layer) - 1
             while layer[right] == 0:
                 right -= 1
     
             waterLayer = right - left + 1 - sum(layer)
     
         waterTrapped += waterLayer
     
     return waterTrapped

[JinJinQuant]

986. Interval List Intersections

• come up with the concept of Inf and Sup when we find an overlapped interval

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        p1 = 0
        p2 = 0
        ans = []

        while p1 < len(firstList) and p2 < len(secondList):
            low = max(firstList[p1][0], secondList[p2][0])
            high = min(firstList[p1][1], secondList[p2][1])

            if low <= high:
                ans.append([low, high])

            if firstList[p1][1] < secondList[p2][1]:
                p1 += 1
            else:
                p2 += 1

        return ans

[JinJinQuant]

2824. Count Pairs Whose Sum is Less than Target

[JinJinQuant]

1358. Number of Substrings Containing All Three Characters

[JinJinQuant]

905. Sort Array By Parity

[JinJinQuant]

977. Squares of a Sorted Array

[JinJinQuant]

80. Remove Duplicates from Sorted Array II

[JinJinQuant]

121. Best Time to Buy and Sell Stock

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buyingPrice = prices[0]
        profit = 0

        for i in range(1, len(prices)):
            if prices[i] < buyingPrice:
                buyingPrice = prices[i]
            if prices[i] - buyingPrice > profit:
                profit = prices[i] - buyingPrice

    return profit

[JinJinQuant]

53. Maximum Subarray

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = float('-inf')
        currentSum = 0

        for num in nums:
            currentSum += num
            if currentSum > maxSum:
                maxSum = currentSum
            if currentSum < 0:
                currentSum = 0

        return maxSum