Two Pointers
•
Two pointers involve two integer variables that both move along an iterable
→i and j, left and right ; represents an index of the array or string
•
often used for problems like searching, sorting, finding pairs that statisfy a condition
•
runs in and uses only space
Implementing two pointers
1.
Start one pointer at the first index0 and the other pointer at the last index input.length -1
2.
Use a while loop until the pointers are equal to each other
3.
At each iteration of the loop, move the pointers toward each other.
•
increment the first pointer toward the second pointer ;left++
•
decrement the second pointer toward the first pointer ; right—
•
do both left++ and right—
def two_sum_sorted(arr, target):
left = 0
right = len(arr)-1
while left<right :
current_sum == arr[left] + arr[right]
if current_sum == target:
return (left, right)
elif current_sum < target:
left+= 1
else:
right -= 1
return None
'''Example usage '''
arr = [1, 2, 3, 4, 6]
target = 6
print(two_sum_sorted(arr, target)) # Output: (0, 3)
Python
복사
Example 1 : Palindrome
•
Given a string s, return true if it’s a palindrome, false other wise
def palindrome(string):
left = 0
right = len(string)-1
while left<right :
if string[left] != string[right] :
return False
left+=1
right+=1
return True
Python
복사
Example 2: Two Sum
•
Given a sorted array of unique integers and a target integer, return true if there exists a pair of numbers that sum to target
def two_sum_target(nums, target):
left = 0
right = len(nums)-1
while left < right:
c_sum = nums[left] + nums[right]
if c_sum <target :
left +=1
elif c_sum > target :
right-=1
elif c_sum == target:
return True
return False
Python
복사
•
Since the array is sorted, we can used two pointers to solve to improve to an O(n) time complexity
→ moving the right pointer permanently decreases the value of the pointer and moving the left pointer permanently increases the value of the pointer
•
3 possibilities
◦
current sum == target
→ Return True
◦
current sum smaller than target
→ have to make it bigger ; moving the left pointer ; left+=1
◦
current sum bigger than target
→ have to make it smaller; moving the right pointer left; right-= 1
Other way to use Two Pointers
•
two pointers can be used on the problem with two iterables in the input(Two Arrays)
•
Until all elements have been checked, we can moving along both inputs simultaneously by using two pointers
Implementation
1.
Create two pointers, one for each iterable
→ each pointer starts at the first index of each iterable
2.
Use a while loop until one of the pointers reaches the end of its iterable
3.
At each iteration of the loop, move the pointers forward.
→ Increment either one othe pointers or both of the pointers.
4.
While loop stops when one of the pointers reaches the end
→ the other pointer might not have reached the end of its iterable when the loop finishes.
→ or sometimes we need to iterate through all elements
def two_arrays(arr1, arr2):
i = j = 0
while i < len(arr1) and j< len(arr2):
# Do some logic here depending on the problem
1. i += 1
2. j += 1
3. i += 1; j += 1
# Step 4: make sure both iterables are exhausted
while i < len(arr1):
i += 1
while j < len(arr2):
j += 1
Python
복사
•
this method has time complexity of , where n = len(arr1), m = len(arr2)
Example 3 : combine 2 arrays
•
Given two sorted integer arrays arr1 and arr2, return a new array that combines both of them and is also sorted
def two_array(arr1, arr2):
i = j = 0
ans = []
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
ans.append(arr1[i])
i += 1
else:
ans.append(arr1[i])
j += 1
while i < len(arr1):
ans.append(arr1[i])
i += 1
while j < len(arr2):
ans.append(arr2[j])
j += 1
return ans
Python
복사
•
since we have to combine the arrays in to one, total length can be represented as n = len(arr1) + len(arr2)
→ time complexity appears to be
•
by comparing two pointers for each array, we can sort out smallest element from each array.
Example 4: Subsequence of a string
•
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
def sub_string (s:str ,t:str) -> bool:
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i+=1
j += 1
return i == len(s)
Python
복사
•
to check if characters of s appears in the same order in t, we can use s[i] == t[j], using 2 pointers
◦
we can move on the the next on by incrementing i
•
We should increment j at each iteration no matter what.
def sub_string (s:str ,t:str) -> bool:
i = 0
for char in t: # Iterate through each character in t
if i < len(s) and s[i] == char: # Check if the character matches
i += 1
if i == len(s): # All characters of s are found in t
return True
return i == len(s) # Return True if all characters in s are matched
Python
복사
