Skills for tackling LeetCode problems - Two Pointers.
Problem Statement: Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.
We can start with one pointer in the beginning and another pointer at the end. During iteration, we see if the numbers pointed by two pointers add up to the target. If not, we will move either one of the two pointers in this way 1) if the sum is greater than the target, move the end pointer to the left 2) if the sum is smaller than the target, move the start pointer to the right. The time complexity is O(n).
1. Pair with Target Sum
Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.
# 1. Binary Search.
# Time complexity O(N). Space complexity O(1).
def pair_with_targetsum(arr, target_sum):
l = 0
r = len(arr) -1
while l < r:
SUM = arr[l] + arr[r]
if SUM == target_sum:
return [l, r]
if SUM > target_sum:
r -= 1
else:
l += 1
return [-1, -1]
# 2. HashTable.
# Time complexity O(N). Space complexity O(N).
def pair_with_targetsum(arr, target_sum):
nums = {}
for i, num in enumerate(arr):
if target_sum - num in nums:
return [nums[target_sum - num], i]
else:
nums[arr[i]] = i
return [-1. -1]
2. Remove Duplicates
Given an array of sorted numbers, remove all duplicates from it. You should not use any extra space; after removing the duplicates in-place return the length of the subarray that has no duplicate in it.
# Shift the elements left whenever we encounter duplicates.
# Time complexity O(N). Space complexity O(1).
def remove_duplicates(arr):
next_unique = 1
for i in range(1, len(arr)):
if arr[next_unique - 1] != arr[i]:
arr[next_unique] = arr[i]
next_unique += 1
return next_unique
Given an unsorted array of numbers and a target “key”, remove all instances of “key” in-place and return the new length of the array.
# Shift the elements left whenever we encounter duplicate of key.
# Time complexity O(N). Space complexity O(1).
def remove_element(arr, key):
next_notKey = 0
for i in range(len(arr)):
if arr[i] != key:
arr[next_notKey] = arr[i]
next_notKey += 1
return next_notKey
3. Squaring a Sorted Array
Given a sorted array, create a new array containing squares of all the numbers of the input array in the sorted order.
# One pointer squares non-negative numbers, the other pointer squares negative numbers.
# Time complexity O(N). Space complexity O(N).
def make_squares(arr):
l, r = 0, len(arr) - 1
res = []
while l <= r:
leftSquare = arr[l] * arr[l]
rightSquare = arr[r] * arr[r]
if leftSquare > rightSquare:
res.insert(0, leftSquare)
l += 1
else:
res.insert(0, rightSquare)
r -= 1
return res
4. Triplet Sum to Zero
Given an array of unsorted numbers, find all unique triplets in it that add up to zero.
# Sort the array to handle duplicates. Find Y + Z = - X.
# Time complexity O(N log N + N^2) = O(N^2). (O(N log N) for sort(), O(N^2) for searching)
# Space complexity O(N) required for sorting.
def search_triplets(arr):
arr.sort()
triplets = []
for i in range(len(arr)):
if i > 0 and arr[i] == arr[i-1]: # skip duplicate
continue
right = len(arr) - 1
target_sum = -arr[i] # - X
left = i + 1
while left < right:
current_sum = arr[left] + arr[right] # Y + Z
if current_sum == target_sum:
triplets.append([-target_sum, arr[left], arr[right]])
left += 1
right -= 1
while left < right and arr[left] == arr[left - 1]: left += 1
while left < right and arr[right] == arr[right + 1]: right -= 1
elif target_sum > current_sum:
left += 1
else:
right -= 1
return triplets
5. Triplet Sum Close to Target
Given an array of unsorted number and a target number, find a triplet in the array whose sum is as close to the target number as possible, return the sum of the triplet. If there are more than one such triplet, return teh sum of the triplet with the smallest sum.
# Time complexity O(N log N + N^2) = O(N^2) (sorting takes O(N log N), searching takes O(N^2)).
# Space complexity O(N).
import math
def triplet_sum_close_to_target(arr, target_sum):
arr.sort()
MIN_diff = math.inf
for i in range(len(arr) - 2):
left = i + 1
right = len(arr) -1
while left < right:
target_diff = target_sum - (arr[i] + arr[left] + arr[right]) # save the difference between the triplet and the target
if target_diff == 0: return target_sum # find the triplet
if abs(target_diff) < abs(MIN_diff) or (abs(target_diff) == abs(MIN_diff) and target_diff > MIN_diff):
MIN_diff = target_diff
if target_diff > 0: # target_sum is greater than sum of triplet
left += 1
else: # target_sum is smaller than sum of triplet
right -= 1
return target_sum - MIN_diff # return the sum with the smallest difference
6. Triplet with Smaller Sum
Given an array arr of unsorted numbers and a target sum, count all triplets in it such that arr[i] + arr[j] + arr[k] < target where i, j and k are three different indices. Write a functions to return the count of such triplets.
# Time complexity O(N^2) (Sorting takes O(N log N), searching takes O(N^2)).
# Space complexity O(N).
def triplet_with_smaller_sum(arr, target):
arr.sort()
count = 0
for i in range(len(arr) - 2):
left = i + 1
right = len(arr) - 1
while left < right:
if arr[left] + arr[right] < target - arr[i]:
# since arr is sorted, we can replace arr[right] with any number between right and left, so we count (right - left) number of triplets.
count += right - left
left += 1 # need a pair with a larger sum
else:
right -= 1 # need a pair with a smaller sum
return count
What if we are asking to return a list of all triplets,
# Time complexity O(N^3) (Sorting takes O(N log N), searching takes O(N^3)).
# Space complexity O(N).
def triplet_with_smaller_sum(arr, target):
arr.sort()
triplets = [] # create a list to store the answers
# count = 0
for i in range(len(arr) - 2):
left = i + 1
right = len(arr) - 1
while left < right:
if arr[left] + arr[right] < target - arr[i]:
for j in range(right, left, -1):
triplets.append([arr[i], arr[left], arr[j]])
# count += right - left
left += 1
else:
right -= 1
return triplets
7. Subarrays with Product Less than a Target
Given an array with positive numbers and a positive target number, find all of its continuous subarrays whose product is less than the target number.
# Time complexity O(N^3) (Main for-loop takes O(N), finding subarrays takes O(N^2)).
# Space complexity O(N) for tmp list.
import collections
def find_subarrays(arr, target):
result = []
product = 1
left = 0
for right in range(len(arr)):
product += arr[right]
while product >= target and left < len(arr):
product /= arr[left]
left += 1
tmp = collections.deque()
# product from left to right is less than the target
# so all subarrays from left to right are less than the target
for i in range(right, left - 1, -1):
tmp.appendleft(arr[i])
result.append(list(tmp))
return result
8. Dutch National Flag Problem
Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we cannot count 0s, 1s, and 2s to recreate the array.
# Time complexity O(N). Space complexity O(1)
def dutch_flag_sort(arr):
i = low = 0
high = len(arr) - 1
while i <= high:
if arr[i] == 0:
arr[i], arr[low] = arr[low], arr[i] # move 0s before "low" pointer
i += 1
low += 1
elif arr[i] == 1:
i += 1
else:
arr[i], arr[high] = arr[high], arr[i] # move 1s after "high" pointer
high -= 1
