2 Heads for 2 Arrays

3 while’s

88. Merge Sorted Array (Easy)

Solution

Typically, we can see 3 while loops in these type of problems.

Since we shouldn’t initialize a new array, instead manipulate the first array itself nums1. We can not overwrite answer on nums1 , but the last n elements in nums1 would be free. So let us start filling elements from maximum to minimum, by filling from right to left.

Each of the two pointers start from end of the arrays: a from end on nums1 (i.e. m - 1) and b from end of nums2 (i.e. n - 1).

Have another pointer to insert the answer at each iteration into nums1, named it as insert_here.

First While Loop

  • Loop until both are valid index

  • Compare between two pointers for 2 different array and put the maximum element of them at the answer (in-place on nums1 with pointer insert_here)

  • When any of the pointer from 2 arrays, reach the initial end, terminate the first loop.

Second While Loop

  • If the second arrays pointer b reached -1, then insert the remaining elements from nums1 as it is into nums1. _Essentially, this while loop is not required and is redundant, but just for the sake of template, its been written._

Third While Loop

  • If the first arrays pointer a reached -1, then insert the remaining elements from nums2 as it is into nums1.

Analysis

Time Complexity: O(M+N)

where:

  • M is the length of the first array

  • N is the length of second array

Space Complexity: O(1)

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    a, b = m - 1, n - 1
    insert_here = m + n - 1
    while a >= 0 and b >= 0:
        if nums1[a] >= nums2[b]:
            nums1[insert_here] = nums1[a]
            a -= 1
        else:
            nums1[insert_here] = nums2[b]
            b -= 1
        insert_here -= 1
    while a >= 0:
        nums1[insert_here] = nums1[a]
        a -= 1
        insert_here -= 1
    while b >= 0:
        nums1[insert_here] = nums2[b]
        b -= 1
        insert_here -= 1

1768. Merge Strings Alternately (Easy)

Solution

Each of the two pointers start from end of the arrays: a from end on word1 (i.e. m - 1) and b from end of word2 (i.e. n - 1).

First While Loop

  • Loop until both are valid index

  • Append the element from word1 initially and from word2.

  • When any of the pointer from 2 arrays, reach the end, terminate the first loop.

Second While Loop

  • If the second arrays pointer b reached n, then insert the remaining elements from word1 as it is into ans.

Third While Loop

  • If the first arrays pointer a reached m, then insert the remaining elements from word2 as it is into ans.

Analysis

Time Complexity: O(M+N)

where:

  • M is the length of the first array

  • N is the length of second array

Space Complexity: O(1)

Assuming the space required for the answer ans is not auxiliary space.

def mergeAlternately(self, word1: str, word2: str) -> str:
    m, n = len(word1), len(word2)
    a = b = 0
    ans = []
    while a < m and b < n:
        ans.append(word1[a])
        ans.append(word2[b])
        a += 1
        b += 1
    while a < m:
        ans.append(word1[a])
        a += 1
    while b < n:
        ans.append(word2[b])
        b += 1
    return "".join(ans)

165. Compare Version Numbers (Medium)

Solution

Both pointers a and b starts from 0.

First While Loop

  • Loop until both are valid index

  • Have two other while loops to extract numbers between "." (dots).

  • After having numbers between dots on both strings, no compare these numbers.

Second While Loop

  • If the second arrays pointer b reached n, Check if there any non zero numbers, if true, which means version1 is greater.

Third While Loop

  • If the first arrays pointer a reached m, Check if there any non zero numbers, if true, which means version2 is greater.

Analysis

Time Complexity: O(max(M,N))

where:

  • M is the length of the first string

  • N is the length of second string

Space Complexity: O(1)

def compareVersion(self, version1: str, version2: str) -> int:
    m, n = map(len, (version1, version2))
    a = b = 0
    while a < m and b < n:
        v1 = v2 = 0
        while a < m and version1[a] != ".":
            v1 = v1 * 10 + int(version1[a])
            a += 1
        a += 1
        while b < n and version2[b] != ".":
            v2 = v2 * 10 + int(version2[b])
            b += 1
        b += 1
        if v1 > v2:
            return 1
        elif v1 < v2:
            return -1

    v1 = v2 = 0
    while a < m:
        while a < m and version1[a] != ".":
            v1 = v1 * 10 + int(version1[a])
            a += 1
        a += 1

    while b < n:
        while b < n and version2[b] != ".":
            v2 = v2 * 10 + int(version2[b])
            b += 1
        b += 1

    if v1 > v2:
        return 1
    elif v1 < v2:
        return -1
    else:
        return 0

Miscellaneous

392. Is Subsequence (Easy)

Solution

Have two pointers each pointing to different arrays, and initialize them to 0.

Move second pointer b till the end, and while moving, advance first pointer a if a is pointing to same character as second pointer b.

If a has reached the end, that means, all the characters in s is present in t in order, hence we can say s is a subsequence of t.

Analysis

Time Complexity: O(min(M, N))

where:

  • M is the length of the first array

  • N is the length of second array

Space Complexity: O(1)

def isSubsequence(self, s: str, t: str) -> bool:
    m, n = map(len, (s, t))
    a = b = 0
    while a < m and b < n:
        if s[a] == t[b]:
            a += 1
        b += 1
    return a == m

844. Backspace String Compare (Easy)

Solution

Have two pointers each pointing to different arrays, and initialize them to from backwards.

If any of the pointers point to # while coming from right to left, maintain a variable called back_a or back_b. If back_a = k , then we need to skip k elements which are backspaced.

If both pointers are not pointing to # and there are no remaining back_* left, now we need to compare if both pointer characters are equal or not. If not, return False.

At the end, if any of the pointers is not actually exhausted, then we have few elements left in one string but another got exhausted. So we need to return False. If both pointers are exhausted, then return True meaning all elements are equal.

Analysis

Time Complexity: O(min(M, N))

where:

  • M is the length of the first array

  • N is the length of second array

Space Complexity: O(1)

def backspaceCompare(self, s: str, t: str) -> bool:
    a, b = len(s) - 1, len(t) - 1
    back_a = back_b = 0
    while a >= 0 or b >= 0:
        if a >= 0 and s[a] == "#":
            back_a += 1
            a -= 1
        elif back_a > 0:
            back_a -= 1
            a -= 1
        elif b >= 0 and t[b] == "#":
            back_b += 1
            b -= 1
        elif back_b > 0:
            back_b -= 1
            b -= 1
        elif a >= 0 and b >= 0 and s[a] == t[b]:
            a -= 1
            b -= 1
        else:
            return False
    return a < 0 and b < 0