Skip to main content

Two Heads for Two Arrays

Each pointer walks a different array. A first while advances both while they are valid and decides what to take; two trailing while loops drain whichever array still has leftovers. This 3-loop template handles merges and comparisons cleanly, and the fill direction (forward or backward) is chosen to avoid clobbering data still being read.

Three While Loops​

88. Merge Sorted Array​

Easy·
Solutions:
Visualize
class Solution:
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·
Solutions:
Visualize
class Solution:
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·
Solutions:
Visualize
class Solution:
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·
Solutions:
Visualize
class Solution:
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·
Solutions:
Visualize
class Solution:
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