2 pointers

Question 1

Remove Duplicates from Sorted Array
in-place
Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Answer 1

’’’
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
#left = 1, because 1st element is in the correct sorted place
left,right = 1,1
while right<len(nums):
if nums[right] != nums[right-1]:
nums[left] = nums[right]
left+=1
right+=1
else:
right+=1
return left
‘’’

2 pointers. Initialize left and right at 1.
if num[right] != num[right-1]; then num[left] = num[right]. Move left by 1 and right by 1
else ; then just increment left pointer

Question 2

Valid Palindrome

Example 1:

Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
Example 2:

Input: s = “race a car”
Output: false
Explanation: “raceacar” is not a palindrome.
Example 3:

Input: s = “ “
Output: true
Explanation: s is an empty string “” after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Answer 2

’’’
class Solution:
def isPalindrome(self, s: str) -> bool:
left = 0
right = len(s)-1

    while left<right:
        if not s[left].isalnum():
            while not s[left].isalnum() and left<right and left<len(s):
                left+=1
        if not s[right].isalnum() and left < right and right>-1:
            while not s[right].isalnum():
                right-=1
        if s[left].lower() == s[right].lower():
            left+=1
            right-=1
        else:
            return False
    return True '''

===========
left = , right len(s)-1. before checking s[left] and s[right] we need to make sure they are alphabet or numerical. If s[left] is not alphanum then left+=1, similarly right-=1.
** Important note during the while make sure to mention
1. left<right
2. left<len(s)
3. right > -1

Question 3

Two Sum II - Input Array Is Sorted

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Answer 3

’’’
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
left ,right = 0, len(nums)-1
while left<right and left<len(nums):
if nums[left] + nums[right] > target:
right-=1
elif nums[left] + nums[right] < target:
left+=1
else:
return [left+1,right+1]
‘’’

** left < right , no need of “=”.

Question 4

3SUM

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Answer 4

’’’
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
left = 0
visited = set() ## make sure we dont get same triplets again
op = []
for index,num in enumerate(nums):
if num in visited:
continue
else:
visited.add(num)
target = 0 - num
## 2 pointer adding up to target
left = index+1
right = len(nums)-1
while left<right and left<len(nums):
if nums[left] + nums[right] > target:
right-=1
elif nums[left] + nums[right] < target:
left+=1
else:
op.append([num,nums[left],nums[right]])
#search for more combos
left+=1
right-=1
# be cautious and check if same number are there
# same number is same combos be conted again
while left<right and nums[left] == nums[left-1]:
left+=1
return op
‘’’

1. Sort the array
2. iterate through each element, while checking it was previously visited or not
3. If not visited; then it is a 2 pointer adding to target problem , where target = 0 - num.
4. Once target found, left -> and <- right, to find more combos
5. To make sure combos dont repeat we make sure to increment left pointer as long as
   nums[left] == nums[left-1] and left<right