Two Pointers Flashcards
- Valid Palindrome
Solved
Easy
Topics
Companies
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
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.
Constraints:
1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.
https://leetcode.com/problems/valid-palindrome/
class Solution(object):
def isPalindrome(self, s):
“””
:type s: str
:rtype: bool
“””
i, j = 0, len(s) - 1
while(i < j):
while(i < j and not s[i].isalnum()):
i+=1
while(i < j and not s[j].isalnum()):
j-=1
if(s[i].lower() != s[j].lower()):
return False
i+=1
j-=1
return True
- Two Sum II - Input Array Is Sorted
Solved
Medium
Topics
Companies
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
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].
Constraints:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
can use hashmap also but it wont use the sorted property to give o1 space
class Solution(object):
def twoSum(self, numbers, target):
“””
:type numbers: List[int]
:type target: int
:rtype: List[int]
“””
l = 0
r = len(numbers) - 1
while l < r:
s = numbers[l] + numbers[r]
if s > target:
r -= 1
elif s < target:
l += 1
else:
return [l+1, r+1]
- 3Sum
Solved
Medium
Topics
Companies
Hint
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.
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
https://leetcode.com/problems/3sum/
look at code to see how we are removing duplicates. we sort the array and then move pointer till we reach a different element. for both 2sum and 3sum methods. this is important.
class Solution(object):
def threeSum(self, nums):
“””
:type nums: List[int]
:rtype: List[List[int]]
“””
sortnum = sorted(nums)
i = 0
out = []
while i < len(sortnum) - 2:
if sortnum[i] > 0:
break
if i > 0 and sortnum[i] == sortnum[i-1]:
i+=1
else:
out = out + (self.twoSum(sortnum[i+1:], -sortnum[i]))
i+=1
return out
def twoSum(self, nums, target):
l = 0
r = len(nums) - 1
out = []
while l < r:
s = nums[l] + nums[r]
if s < target:
l+=1
elif s > target:
r-=1
else:
out.append([-1 * target, nums[l], nums[r]])
l+=1
r-=1
if l > 0 and nums[l] == nums[l-1]:
while l < r and nums[l] == nums[l-1]:
l+=1
return out
- Container With Most Water
Solved
Medium
Topics
Companies
Hint
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
https://leetcode.com/problems/container-with-most-water/
start at ends , keep track of max height indices for both left and right pointers
class Solution(object):
def maxArea(self, height):
“””
:type height: List[int]
:rtype: int
“””
r = len(height) - 1
lmax = 0
rmax = r
l = 0
maxarea = 0
while l < r:
if height[l] > height[lmax]:
lmax = l
if height[r] > height[rmax]:
rmax = r
maxarea = max(maxarea, min(height[lmax], height[rmax]) * (rmax - lmax))
if height[lmax] > height[rmax]:
r-=1
elif height[rmax] > height[lmax]:
l+=1
else:
l+=1
r-=1
return maxarea
concise way
class Solution:
def maxArea(self, height: List[int]) -> int:
l = 0
r = len(height) - 1
ret = 0
while(l < r):
area = (r - l) * min(height[l], height[r])
ret = max(ret,area)
if height[l] < height[r]:
l+=1
else:
r-=1
return ret
- Trapping Rain Water
Solved
Hard
Topics
Companies
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
https://leetcode.com/problems/trapping-rain-water/
trick is to calculate tallest wall for left and right and then calculate how much water can you store at each index given the wall sizes.
class Solution(object):
def trap(self, height):
“””
:type height: List[int]
:rtype: int
“””
l = 0
r = len(height) - 1
maxL = height[l]
maxR = height[r]
water = 0
while l < r:
if maxL < maxR:
l+=1
maxL = max(maxL, height[l])
water += (maxL - height[l])
else:
r-=1
maxR = max(maxR, height[r])
water += (maxR - height[r])
return water
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
lmax = 0
l = 0
rmax = n-1
r = n-1
ret = 0
ws = [0] * n
while l < r:
if height[l] > height[lmax]:
lmax = l
if height[r] > height[rmax]:
rmax = r
minwall = min(height[lmax], height[rmax])
ws[l] = max(0, minwall - height[l])
ws[r] = max(0, minwall - height[r])
if height[l] < height[r]:
l+=1
else:
r-=1
return sum(ws)
- Length of the Longest Valid Substring
Solved
Hard
Topics
Companies Amazon
You are given a string word and an array of strings forbidden.
A string is called valid if none of its substrings are present in forbidden.
Return the length of the longest valid substring of the string word.
A substring is a contiguous sequence of characters in a string, possibly empty.
Example 1:
Input: word = “cbaaaabc”, forbidden = [“aaa”,”cb”]
Output: 4
Explanation: There are 11 valid substrings in word: “c”, “b”, “a”, “ba”, “aa”, “bc”, “baa”, “aab”, “ab”, “abc” and “aabc”. The length of the longest valid substring is 4.
It can be shown that all other substrings contain either “aaa” or “cb” as a substring.
Example 2:
Input: word = “leetcode”, forbidden = [“de”,”le”,”e”]
Output: 4
Explanation: There are 11 valid substrings in word: “l”, “t”, “c”, “o”, “d”, “tc”, “co”, “od”, “tco”, “cod”, and “tcod”. The length of the longest valid substring is 4.
It can be shown that all other substrings contain either “de”, “le”, or “e” as a substring.
Constraints:
1 <= word.length <= 105
word consists only of lowercase English letters.
1 <= forbidden.length <= 105
1 <= forbidden[i].length <= 10
forbidden[i] consists only of lowercase English letters.
https://leetcode.com/problems/length-of-the-longest-valid-substring/description/
class Solution:
def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
f = set(forbidden)
mlen = 0
ret = 0
for fb in forbidden:
mlen = max(mlen, len(fb))
r = len(word)
for l in range(len(word)-1, -1, -1):
if r <= ret:
break
for j in range(l, min(r, l+mlen)):
if word[l:j+1] in f:
r = j
break
ret = max(ret, r - l)
return ret
