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·

88Merge Sorted Array

Three-While Merge from the Back

O(M+N) timeO(1) aux

FIG. 88 MERGE SORTED ARRAY● INTERACTIVE

visualization loads as you reach it

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·

1768Merge Strings Alternately

Parallel Walk

O(M+N) timeO(M + N) aux

FIG. 1768 MERGE STRINGS ALTERNATELY● INTERACTIVE

visualization loads as you reach it

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·

165Compare Version Numbers

Parallel Revision Scan

O(M+N) timeO(1) aux

FIG. 165 COMPARE VERSION NUMBERS● INTERACTIVE

visualization loads as you reach it

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·

392Is Subsequence

Greedy Match

O(N) timeO(1) aux

FIG. 392 IS SUBSEQUENCE● INTERACTIVE

visualization loads as you reach it

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·

844Backspace String Compare

Reverse Scan with Skip Counters

O(M+N) timeO(1) aux

FIG. 844 BACKSPACE STRING COMPARE● INTERACTIVE

visualization loads as you reach it

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

---

242. Valid Anagram

Easy·

242Valid Anagram

3 Approaches · 2 patterns

Sort Both, Walk in Lockstep

O(N + 2N log N) timeO(sort + 2N) aux

Compare Two Frequency Counters

O(2N + k) timeO(2k) aux

Sliding Window↗ Sliding Window

O(N) timeO(1) aux

FIG. 242 VALID ANAGRAM SORTED LOCKSTEP● INTERACTIVE

visualization loads as you reach it

class Solution:

def isAnagram(self, s: str, t: str) -> bool:

if len(s) != len(t):

return False

s = sorted(s)

t = sorted(t)

for i, j in zip(s, t):

if i != j:

return False

return True

---