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
Medium
Companies: Many
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
Medium
Companies: Google and many similar.
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- Valid Palindrome II
Companies: facebook 2024
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Example 1:
Input: s = “aba”
Output: true
Example 2:
Input: s = “abca”
Output: true
Explanation: You could delete the character ‘c’.
Example 3:
Input: s = “abc”
Output: false
Constraints:
1 <= s.length <= 105 s consists of lowercase English letters.
O(n), O(n) Follow up: do it in O(1) space
https://leetcode.com/problems/valid-palindrome-ii/description/
If char l and r are not equal, remove l and check if its palindrome or remove r and check if its palindrome
class Solution:
def validPalindrome(self, s: str) -> bool:
p = 1
l = 0
r = len(s)-1
while l < r:
if s[l] != s[r]:
s1 = s[:l] + s[l+1:]
s2 = s[:r] + s[r+1:]
return s1[::-1] == s1 or s2[::-1] == s2
else:
l += 1
r -= 1
return True
Backtracking
def validPalindrome(self, s: str) -> bool:
def verify(s, left, right, deleted):
while left < right:
if s[left] != s[right]:
if deleted:
return False
else:
return verify(s, left+1, right, True) or verify(s, left, right-1, True)
else:
left += 1
right -= 1
return True
return verify(s, 0, len(s)-1, False)
O(1) solution
~~~
class Solution(object):
def validPalindrome(self, s):
“””
:type s: str
:rtype: bool
“””
i, j = 0, len(s)-1
check_a, check_b = True, True
while i < j:
if s[i] != s[j]:
ib, jb = i,j
while(i+1<j):
if s[i+1] != s[j]:
check_a = False
break
i+=1
j-=1
while(ib < jb-1):
if s[ib] != s[jb-1]:
check_b = False
ib+=1
jb-=1
return check_a or check_b
else:
i+=1
j-=1
return True
~~~
10 Minutes target
O(n), O(n) Because we store s1 and s2
- Palindromic Substrings
Solved
Medium
Topics
Companies
Hint
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: s = “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Constraints:
1 <= s.length <= 1000 s consists of lowercase English letters.
O(n^2), O(n) Space - O(1) if you can.
https://leetcode.com/problems/palindromic-substrings/description/
Expand from center approach: if s[i:j+1] is palindrome we can keep expanding window till we fail this check.
~~~
class Solution(object):
def countSubstrings(self, s):
“””
:type s: str
:rtype: int
“””
n = len(s)
palins = 0
def palin(i,j):
palins = 0
while (i >= 0 and j <= len(s) - 1) and s[i] == s[j]:
i -= 1
j += 1
palins += 1
return palins
for start in range(n):
# odd
odd = palin(start, start)
palins += odd
even = palin(start, start+1)
palins += even
return palins ~~~
- Longest Palindromic Substring
Medium
Companies: Multiple in 2024
Given a string s, return the longest
palindromic
substring
in s.
Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output: “bb”
Constraints:
1 <= s.length <= 1000 s consist of only digits and English letters.
O(n^2), O(n)/O(1) space
https://leetcode.com/problems/longest-palindromic-substring/description/
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
mlen = 1
mi,mj = 0,0
def findPalindrome(l,r, bl, br, s):
i,j = l,r
while i > bl and j < br and s[i] == s[j]:
i-=1
j+=1
return i+1,j-1
for idx in range(n):
# check odd palindromes
oi, oj = findPalindrome(idx, idx, -1, n, s)
# even
ei, ej = findPalindrome(idx, idx+1, -1, n, s)
olen = (oj-oi+1)
elen = (ej-ei+1)
if olen > mlen:
mi, mj = oi, oj
mlen = olen
if elen > mlen:
mi,mj = ei,ej
mlen = elen
return s[mi:mj+1]- Shortest Palindrome
Hard
Companies: MS, Amazon, TikTok
You are given a string s. You can convert s to a
palindrome
by adding characters in front of it.
Return the shortest palindrome you can find by performing this transformation.
Example 1:
Input: s = “aacecaaa”
Output: “aaacecaaa”
Example 2:
Input: s = “abcd”
Output: “dcbabcd”
Constraints:
0 <= s.length <= 5 * 104 s consists of lowercase English letters only.
O(n^2) acceptable. O(n) space
https://leetcode.com/problems/shortest-palindrome/description/
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# Key here is to know that to find the longest palindrome starting at 0
# in the original string, and prepend reverse of the remaining string.
# because as we know if s[i] == s[j] then its a palindrome if s[i+1][j-1] is also a palindrome
# we find the highest j with i == 0 to make the middle string a palindrome and then fix the rest.
# Here we compare the reverse string with the forward string to find the longest suffix in
# reverse that is equal to prefix in original string.
#KMP can be used but it's over complicated for interview setting.
# https://leetcode.com/problems/shortest-palindrome/solutions/60099/ac-in-288-ms-simple-brute-force
rev = s[::-1]
# +1 to cover cases where string empty.
for i in range(len(rev)+1):
# if this suffix is eq prefix
if s.startswith(rev[i:]):
return rev[:i] + s
KMP O(n), O(n)
Explanation
class Solution:
def shortestPalindrome(self, s: str) -> str:
rev = s[::-1]
n = len(s)
s_new = s + "#" + rev
nsnew = len(s_new)
dp = [0] * len(s_new)
for i in range(1, nsnew):
t = dp[i-1]
while s_new[t] != s_new[i] and t > 0:
t = dp[t-1]
if s_new[t] == s_new[i]:
t += 1
dp[i] = t
return rev[:n-dp[-1]] + s
- Add Strings
Solved
Easy
Topics
Companies
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
Example 1:
Input: num1 = “11”, num2 = “123”
Output: “134”
Example 2:
Input: num1 = “456”, num2 = “77”
Output: “533”
Example 3:
Input: num1 = “0”, num2 = “0”
Output: “0”
Constraints:
1 <= num1.length, num2.length <= 104
num1 and num2 consist of only digits.
num1 and num2 don’t have any leading zeros except for the zero itself.
https://leetcode.com/problems/add-strings/description/
from collections import deque
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
i = len(num1) - 1
j = len(num2) - 1
base = ord('0')
carry = 0
res = deque()
def getDigit(c):
return ord(c) - ord('0')
while i >= 0 or j >= 0:
c1 = 0 if i < 0 else getDigit(num1[i])
c2 = 0 if j < 0 else getDigit(num2[j])
addn = c1 + c2 + carry
digit = chr(addn%10 + ord('0'))
carry = addn//10
res.appendleft(digit)
i-=1
j-=1
if carry:
res.appendleft(chr(carry + ord('0')))
return "".join(res)- Max Consecutive Ones III
Solved
Medium
Topics
Companies
Hint
Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Constraints:
1 <= nums.length <= 105
nums[i] is either 0 or 1.
0 <= k <= nums.length
https://leetcode.com/problems/max-consecutive-ones-iii/description/
Expand window till it’s valid, when it’s not, just increment left by one, and keep doing it till the end.
We do not need to shrink window completely because once we have the largest window we can maintain it’s size.
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = 0
zeros = 0
for i,c in enumerate(nums):
zeros += (1-c)
if zeros > k:
zeros -= (1-nums[left])
left += 1
return i-left + 1
