array / string

Question 1

merge strings alternately

two pointer approach
theory

Answer 1

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.

Question 2

merge strings alternately

two pointer approach
code

Answer 2

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)

Question 3

merge strings alternately
approach overview

Answer 3

two approaches:
1) two pointers
2) one pointer

Question 4

reverse words in a string
approach overview

Answer 4

1) built in split and reverse
2) reverse the whole string and then reverse each word
3) deque of words

Question 5

reverse words in a string

built in split and reverse code

Answer 5

class Solution:
def reverseWords(self, s: str) -> str:
return “ “.join(reversed(s.split()))

Question 6

reverse words in a string

reverse string then each word

Answer 6

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)

Question 7

reverse words in a string

deque of words

Answer 7

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)

Question 8

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].

Answer 8

1) left and right product lists
2) using constant space

Question 9

product of array except self

code for left and right product lists

Answer 9

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 answer

Question 10

product of array except self

describe algorithm for left and right

Answer 10

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].

Question 11

product of array except self

o(1) space approach

Answer 11

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]

Question 12

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.

Answer 12

1) linear scan (only listed approach)

Question 13

increasing triplet subsequence algorithm

Answer 13

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.

Question 14

increasing triplet subsequence code solution

Answer 14

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 False

Question 15

kids with candies

Answer 15

def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
return [True if (c + extraCandies) >= max(candies) else False for c in candies]

Question 16

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.

Answer 16

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 False

Question 17

greatest common divisor of strings
theory

Answer 17

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.

Question 18

greatest common divisor of strings
code

Answer 18

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]

Question 19

reverse vowels of a string
theory

Answer 19

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.

Question 20

reverse vowels of a string
code

Answer 20

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)

Question 21

string compression
theory

Answer 21

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.

Question 22

string compression
code