array / string Flashcards
merge strings alternately
two pointer approach
theory
Create two variables, m and n, to store the length of word1 and word2.
Create an empty string variable result to store the result of merged words.
Create two pointers, i and j to point to indices of word1 and word2. We initialize both of them to 0.
While i < m || j < n:
If i < m, it means that we have not completely traversed word1. As a result, we append word1[i] to result. We increment i to point to next index of word1.
If j < n, it means that we have not completely traversed word2. As a result, we append word2[j] to result. We increment j to point to next index of word2.
Return result.
merge strings alternately
two pointer approach
code
class Solution(object):
def mergeAlternately(self, word1, word2):
m = len(word1)
n = len(word2)
i = 0
j = 0
result = []
while i < m or j < n:
if i < m:
result += word1[i]
i += 1
if j < n:
result += word2[j]
j += 1
return "".join(result)merge strings alternately
approach overview
two approaches:
1) two pointers
2) one pointer
reverse words in a string
approach overview
1) built in split and reverse
2) reverse the whole string and then reverse each word
3) deque of words
reverse words in a string
built in split and reverse code
class Solution:
def reverseWords(self, s: str) -> str:
return “ “.join(reversed(s.split()))
reverse words in a string
reverse string then each word
class Solution:
def trim_spaces(self, s: str) -> list:
left, right = 0, len(s) - 1
# remove leading spaces
while left <= right and s[left] == " ":
left += 1
# remove trailing spaces
while left <= right and s[right] == " ":
right -= 1
# reduce multiple spaces to single one
output = []
while left <= right:
if s[left] != " ":
output.append(s[left])
elif output[-1] != " ":
output.append(s[left])
left += 1
return output
def reverse(self, l: list, left: int, right: int) -> None:
while left < right:
l[left], l[right] = l[right], l[left]
left, right = left + 1, right - 1
def reverse_each_word(self, l: list) -> None:
n = len(l)
start = end = 0
while start < n:
# go to the end of the word
while end < n and l[end] != " ":
end += 1
# reverse the word
self.reverse(l, start, end - 1)
# move to the next word
start = end + 1
end += 1
def reverseWords(self, s: str) -> str:
# converst string to char array
# and trim spaces at the same time
l = self.trim_spaces(s)
# reverse the whole string
self.reverse(l, 0, len(l) - 1)
# reverse each word
self.reverse_each_word(l)
return "".join(l)reverse words in a string
deque of words
def reverseWords(self, s: str) -> str:
left, right = 0, len(s) - 1
# remove leading spaces
while left <= right and s[left] == " ":
left += 1
# remove trailing spaces
while left <= right and s[right] == " ":
right -= 1
d, word = deque(), []
# push word by word in front of deque
while left <= right:
if s[left] == " " and word:
d.appendleft("".join(word))
word = []
elif s[left] != " ":
word.append(s[left])
left += 1
d.appendleft("".join(word))
return " ".join(d)product of array except self (approaches)
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
1) left and right product lists
2) using constant space
product of array except self
code for left and right product lists
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# The length of the input array
length = len(nums)
# The left and right arrays as described in the algorithm
L, R, answer = [0] * length, [0] * length, [0] * length
# L[i] contains the product of all the elements to the left
# Note: for the element at index '0', there are no elements to the left,
# so the L[0] would be 1
L[0] = 1
for i in range(1, length):
# L[i - 1] already contains the product of elements to the left of 'i - 1'
# Simply multiplying it with nums[i - 1] would give the product of all
# elements to the left of index 'i'
L[i] = nums[i - 1] * L[i - 1]
# R[i] contains the product of all the elements to the right
# Note: for the element at index 'length - 1', there are no elements to the right,
# so the R[length - 1] would be 1
R[length - 1] = 1
for i in reversed(range(length - 1)):
# R[i + 1] already contains the product of elements to the right of 'i + 1'
# Simply multiplying it with nums[i + 1] would give the product of all
# elements to the right of index 'i'
R[i] = nums[i + 1] * R[i + 1]
# Constructing the answer array
for i in range(length):
# For the first element, R[i] would be product except self
# For the last element of the array, product except self would be L[i]
# Else, multiple product of all elements to the left and to the right
answer[i] = L[i] * R[i]
return answerproduct of array except self
describe algorithm for left and right
Initialize two empty arrays, L and R where for a given index i, L[i] would contain the product of all the numbers to the left of i and R[i] would contain the product of all the numbers to the right of i.
We would need two different loops to fill in values for the two arrays.
For the array L, L[0] would be 1 since there are no elements to the left of the first element. For the rest of the elements, we simply use L[i]=L[i−1]∗nums[i−1].
Remember that L[i] represents product of all the elements to the left of element at index i.
For the other array, we do the same thing but in reverse i.e. we start with the initial value of 1 in R[length−1] where length is the number of elements in the array, and keep updating R[i] in reverse.
Essentially, R[i]=R[i+1]∗nums[i+1].
Remember that R[i] represents product of all the elements to the right of element at index i.
Once we have the two arrays set up properly, we simply iterate over the input array one element at a time, and for each element at index i, we find the product except self as L[i]∗R[i].
product of array except self
o(1) space approach
Initialize the empty answer array where for a given index i, answer[i] would contain the product of all the numbers to the left of i.
We construct the answer array the same way we constructed the L array in the previous approach.
These two algorithms are exactly the same except that we are trying to save up on space.
The only change in this approach is that we don’t explicitly build the R array from before. Instead, we simply use a variable to keep track of the running product of elements to the right and we keep updating the answer array by doing
answer[i]=answer[i]∗R. For a given index i, answer[i] contains the product of all the elements to the left and R would contain product of all the elements to the right. We then update R as R=R∗nums[i]
increasing triplet subsequence approaches
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.
1) linear scan (only listed approach)
increasing triplet subsequence algorithm
Algorithm:
Start with two variables, first_num and second_num, initialized to a large value.
Iterate through the array:
If the current number is smaller than first_num, update first_num.
Else, if it’s smaller than second_num but greater than first_num, update second_num.
If a number is found that’s greater than both first_num and second_num, return True.
If no such triplet is found by the end of the iteration, return False.
increasing triplet subsequence code solution
def increasingTriplet(self, nums: List[int]) -> bool:
first_num = float("inf")
second_num = float("inf")
for n in nums:
if n <= first_num:
first_num = n
elif n <= second_num:
second_num = n
else:
return True
return Falsekids with candies
def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
return [True if (c + extraCandies) >= max(candies) else False for c in candies]You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.
Given an integer array flowerbed containing 0’s and 1’s, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
# Check if no flowers need to be planted
if n == 0:
return True
# Iterate through each position in the flowerbed
for i in range(len(flowerbed)):
# Check if the current position is vacant and the adjacent positions are also vacant
if flowerbed[i] == 0 and (i == 0 or flowerbed[i-1] == 0) and (i == len(flowerbed)-1 or flowerbed[i+1] == 0):
# Plant a flower at the current position
flowerbed[i] = 1
# Decrease the number of flowers left to plant
n -= 1
# If all flowers are planted, return True
if n == 0:
return True
# Return False if it's not possible to plant all flowers
return Falsegreatest common divisor of strings
theory
Suppose there exists a divisible string base, we can write str1 and str2 in the form of multiples of base. Take the following picture as an example.
Since both strings contains multiples of the identical segment base, their concatenation must be consistent, regardless of the order (str1 + str2 = str2 + str1).
Check if the concatenations of str1 and str2 in different orders are the same.
If not, return “”.
Otherwise, get the GCD gcdLength of the two lengths of str1 and str2.
Return the prefix string with a length of gcdLength of either str1 or str2 as the answer.
greatest common divisor of strings
code
def gcdOfStrings(self, str1: str, str2: str) -> str:
# Check if they have non-zero GCD string.
if str1 + str2 != str2 + str1:
return ""
# Get the GCD of the two lengths.
max_length = gcd(len(str1), len(str2))
return str1[:max_length]reverse vowels of a string
theory
Initialize the left pointer start to 0, and the right pointer end to s.size() - 1.
Keep iterating until the left pointer catches up with the right pointer:
- Keep incrementing the left pointer start until it’s pointing to a vowel character.
- Keep decrementing the right pointer end until it’s pointing to a vowel character.
- Swap the characters at the start and end.
- Increment the start pointer and decrement the end pointer.
Return the string s.
reverse vowels of a string
code
def reverseVowels(self, s: str) -> str:
p1 = 0
p2 = len(s) - 1
s_list = list(s)
while (p1 < p2):
if s_list[p1] in "AEIOUaeiou" and s_list[p2] in "AEIOUaeiou":
s_list[p1], s_list[p2] = s_list[p2], s_list[p1]
p1 +=1
p2 -=1
if s_list[p1] not in "AEIOUaeiou":
p1 += 1
if s_list[p2] not in "AEIOUaeiou":
p2 -= 1
return "".join(s_list)string compression
theory
Declare the variables:
i – the first index of the current group
res – the length of the answer (of the compressed string). Initialize i = 0, res = 0.
While i is less than the length of chars:
Find the length of the current group of consecutive repeating characters groupLength.
Add chars[i] to the answer (chars[res++] = chars[i]).
If groupLength > 1, add the string representation of groupLength to the answer and increase res accordingly.
Increase i by groupLength and proceed to the next group.
Return res.
string compression
code
merge intervals: intuition
First, we sort the list as described. Then, we insert the first interval into our merged list and continue considering each interval in turn as follows: If the current interval begins after the previous interval ends, then they do not overlap and we can append the current interval to merged. Otherwise, they do overlap, and we merge them by updating the end of the previous interval if it is less than the end of the current interval.
A simple proof by contradiction shows that this algorithm always produces the correct answer. First, suppose that the algorithm at some point fails to merge two intervals that should be merged. This would imply that there exists some triple of indices i, j, and k in a list of intervals ints such that i<j<k and (ints[i], ints[k]) can be merged, but neither (ints[i], ints[j]) nor (ints[j], ints[k]) can be merged. From this scenario follow several inequalities:
ints[i].end<ints[j].start
ints[j].end<ints[k].start
ints[i].end≥ints[k].start
We can chain these inequalities (along with the following inequality, implied by the well-formedness of the intervals: ints[j].start≤ints[j].end) to demonstrate a contradiction:
ints[i].end<ints[j].start≤ints[j].end<ints[k].start
ints[i].end≥ints[k].start
Therefore, all mergeable intervals must occur in a contiguous run of the sorted list.
merge intervals: code
def merge(intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# if the list of merged intervals is empty or if the current
# interval does not overlap with the previous, simply append it.
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# otherwise, there is overlap, so we merge the current and previous
# intervals.
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
