Dealing with SORTED arrays or Linked Lists and need to find set of elements that fulfill certain constraints.

Pair with Target Sum

def pair_with_targetsum(arr, target_sum):
  
  leftPointer = 0
  rightPointer = len(arr) - 1

  while leftPointer < rightPointer:
    currSum = arr[leftPointer] + arr[rightPointer]
    if currSum is target_sum:
      return [leftPointer, rightPointer]
    if currSum < target_sum:
      leftPointer += 1
    elif currSum > target_sum:
      rightPointer -= 1
      
  return [-1, -1]

Remove Duplicates from Sorted Array in Place

Use a left pointer to point to the position for the non duplicate number. The right pointer just loops from 1 to len(arr)

def remove_duplicates(arr):

  nextNum = 1

  for i in range(1, len(arr)):

    if arr[nextNum - 1] is not arr[i]:
      arr[nextNum] = arr[i]
      nextNum += 1

  return nextNum

Squaring a Sorted Array

Since the largest square can be on the left (negative) or right, we use two pointers starting from each end. While left < right, we compare the squares and put the larger one in the largest index in the output array.

def make_squares(arr):

  squares = [0 for _ in range(len(arr))]
  left, right = 0, len(arr) - 1
  squareIdx = len(arr) - 1

  while left < right:
    leftSquare = arr[left] * arr[left]
    rightSquare = arr[right] * arr[right]

    if leftSquare > rightSquare:
      squares[squareIdx] = leftSquare
      left += 1
    else:
      squares[squareIdx] = rightSquare
      right -= 1
      
    squareIdx -= 1
  
  return squares

Triplet Sum to Zero

First must sort the array. The outer loop loops from index 0 to len(arr). At each index, we make -1 * arr[i] the target, and essentially do two sum on the rest of the array to the right of i. They key here is to avoid dumplicates by skipping i if arr[i] == arr[i-1], or l if a[l] == arr[l-1] after we found a match and increment l.

def search_triplets(arr):
  triplets = []
  arr.sort()
  n = len(arr)


  for i in range(n):
    # This number is same as previous. Skip
    if i > 0 and arr[i] == arr[i-1]:
      continue
    
    target = -1 * arr[i]
    l = i + 1
    r = n - 1
    while l < r:

      if arr[l] + arr[r] == target:
        triplets.append([arr[i], arr[l], arr[r]])
        l += 1
        while l < r and arr[l] == arr[l-1]:
          l += 1
      elif arr[l] + arr[r] < target:
        l += 1
      else:
        r -= 1

  return triplets

Triplet Sum Close to Target

Similar to above, where outer loop from index 0 to len(array) - 1. The only idfference is we keep track of the current smallest diff and the current sum corresponding to the smallest diff. That way, if we get a triplet with the same smallest diff, we check to see if the sum is smaller.

import math

def triplet_sum_close_to_target(arr, target_sum):
  n = len(arr)
  runningSum = math.inf
  runningDiff = math.inf
  arr.sort()

  for i in range(n):
    if i > 0 and arr[i] is arr[i-1]:
      continue
    
    l = i + 1
    r = n - 1
    while l < r:
      curSum = arr[i] + arr[l] + arr[r]
      diff = abs(target_sum - curSum)

      if diff is runningDiff and curSum < runningSum:
        runningSum = curSum
      elif diff < runningDiff:
        runningSum = curSum
        runningDiff = diff
      
      if curSum <= target_sum:
        l += 1
      else:
        r -= 1


  return runningSum

Triplet with Smaller Sum

Similar to above. This time, once we get a sum less than target, we add r - l to target, since right can point to any number between itself and left to still get a sum smaller than target

def triplet_with_smaller_sum(arr, target):
  count = 0

  n = len(arr)
  arr.sort()

  for i in range(n):

    if i > 0 and arr[i] is arr[i-1]:
      continue

    l = i + 1
    r = n - 1

    while l < r:
      curSum = arr[i] + arr[l] + arr[r]

      if curSum < target:
        count += r - l
        l += 1
        while arr[l] is arr[l - 1]:
          l += 1
      else:
        r -= 1
      
  return count

Subarrays with Product Less than Target

This is actually a sliding window problem. The trick here is to avoid duplicate subarrays, we use a deque.appendleft to only add subarrays where arr[right] is the right most value.

from collections import deque

def find_subarrays(arr, target):
  result = []
  left = 0
  product = 1

  for right in range(len(arr)):
    product *= arr[right]

    while product >= target and left < right:
      product /= arr[left]
      left += 1
    
    # To avoid duplication, we will go through all subarrays where arr[right] is the
    # right-most value
    queue = deque()
    for i in range(right, left - 1, -1):
      queue.appendleft(arr[i])
      result.append(list(queue))

  return result

Dutch National Flag Problem

Have a low pointer that points to the place for the next 0, and a high pointer that points to the place for the next 2. Then loop i while i <= high, moving 0s to low pointer and moving 2s to the high pointer - and incrementing / decrementing accordingly.

def dutch_flag_sort(arr):

  n = len(arr)
  low, high = 0, n - 1
  i = 0

  while i <= high:

    if arr[i] is 0:
      arr[low], arr[i] = arr[i], arr[low]
      i += 1
      low += 1
    elif arr[i] is 2:
      arr[high], arr[i] = arr[i], arr[high]
      high -= 1
    else:
      i += 1

  return arr

Quadruple Sum to Target

Similar to Triplet Sum to Target. Only addition is we have another outer loop j before running twoSum on the remaining array.

def twoSum(arr, target, first, second, quadruplets):
  left = second + 1
  right = len(arr) - 1

  while left < right:
    curSum = arr[first] + arr[second] + arr[left] + arr[right]

    if target == curSum:
      quadruplets.append([arr[first], arr[second], arr[left], arr[right]])
      left += 1
      while left < right and arr[left] == arr[left - 1]:
        left += 1

    elif curSum < target:
      left += 1

    else:
      right -= 1

def search_quadruplets(arr, target):
  quadruplets = []
  arr.sort()

  for i in range(len(arr) - 3):

    if i > 0 and arr[i] == arr[i-1]:
      continue

    for j in range(i + 1, len(arr) - 2):

      if j > i + 1 and arr[j] == arr[j - 1]:
        continue

      twoSum(arr, target, i, j, quadruplets)


  return quadruplets

Backspace Compare

Definitely need to do this one again.

def getNextChar(str, index):
  backspaceCount = 0
  while index >= 0:
    if str[index] is '#':
      backspaceCount += 1
    elif backspaceCount > 0:
      backspaceCount -= 1
    else:
      break
    index -= 1
  return index


def backspace_compare(str1, str2):

  i1 = len(str1) - 1
  i2 = len(str2) - 1

  while i1 >= 0 or i2 >= 0:
    next1 = getNextChar(str1, i1)
    next2 = getNextChar(str2, i2)

    # Both strings finished
    if next1 < 0 and next2 < 0:
      return True
    # Only of the Strings finished
    elif next1 < 0 or next1 < 0:
      return False
    elif str1[next1] != str2[next2]:
      return False

    i1 = next1 - 1
    i2 = next2 - 1




  return True

Minimum Window Sort

import math

def shortest_window_sort(arr):

  n = len(arr)

  if n <= 1:
    return 0

  
  left = 0
  right = n - 1

  while left < n - 1 and arr[left+1] >= arr[left]:
    left += 1

  if left == n - 1:
    return 0

  while right > 0 and arr[right-1] <= arr[right]:
    right -= 1

  subarrayMax = -math.inf
  subarrayMin = math.inf

  for i in range(left, right + 1):
    subarrayMax = max(subarrayMax, arr[i])
    subarrayMin = min(subarrayMin, arr[i])

  while left > 0 and arr[left-1] > subarrayMin:
    left -= 1
  
  while right < n-1 and arr[right + 1] < subarrayMax:
    right += 1

  return right - left + 1