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·
Explanation

We are given two sorted arrays nums1 (with capacity for m + n elements, but only the first m are valid) and nums2 (with n valid elements). The goal is to merge them in-place into nums1 in non-decreasing order.

Why fill from the back? The tail of nums1 is free space - those n trailing slots are placeholders. If we filled from the front we would immediately overwrite valid elements in nums1 before we had a chance to compare them. Starting from position m + n - 1 and working left gives us a write position that is always beyond the read positions of both arrays, so no element is ever clobbered.

The classic 3-while template:

  • Pointer a starts at the last valid index of nums1 (m - 1), pointer b at the last index of nums2 (n - 1), and insert_here at the last slot (m + n - 1).
  • First while - both arrays still have elements: compare nums1[a] and nums2[b], write the larger one to insert_here, then advance the corresponding source pointer and insert_here left by one.
  • Second while - only nums1 elements remain: copy them into position. (In practice these are already in the right place, but the loop handles the case correctly.)
  • Third while - only nums2 elements remain: copy them. This is the critical mop-up: if nums2 exhausts slower than nums1, the remaining nums2 values must be written into the front of nums1.

At the end every element from both arrays occupies exactly one slot in nums1, sorted in place with no extra memory.

Analysis
Time
O(M+N)
  • M and N are the number of valid elements in nums1 and nums2 respectively. Every element is visited exactly once across the three while loops.
Space
O(1)
  • The merge is done in-place using only the existing capacity of nums1. No auxiliary array is allocated.
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·
Explanation

We interleave two strings character by character: take one from word1, one from word2, one from word1, and so on. If one string runs out before the other, the remaining characters of the longer string are appended in order.

Parallel walk:

  • Pointers a and b start at the beginning of word1 and word2 respectively.
  • The first while loop advances both pointers in lock-step: append word1[a] then word2[b] to the result list, then increment both. This loop runs exactly min(m, n) times.
  • The second while handles leftover characters in word1 when word1 is longer.
  • The third while handles leftover characters in word2 when word2 is longer.

Result:

  • "".join(ans) collapses the list into the final merged string. Using a list and joining at the end avoids repeated string concatenation, keeping the overall work linear.

The 3-while structure mirrors the classic merge pattern: process the shared prefix together, then drain whichever tail remains.

Analysis
Time
O(M+N)
  • M and N are the lengths of word1 and word2. Every character from both strings is visited exactly once.
Space
O(M+N)
  • The result list ans accumulates all M + N characters before the final join.
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·
Explanation

A version string is a sequence of non-negative integer revisions separated by dots (e.g. "1.01.0"). Two versions are compared revision by revision from left to right; if all compared revisions are equal, trailing missing revisions are treated as 0.

Parsing each revision on the fly:

  • Pointers a and b walk version1 and version2 character by character.
  • An inner loop accumulates digits into an integer (v1 or v2) until it hits a dot or the end of the string. After each inner loop the outer pointer is advanced past the dot with a += 1 (or b += 1), so the next outer iteration starts at the first character of the next revision.
  • Leading zeros are automatically collapsed because we multiply into a running integer (v1 = v1 * 10 + int(char)).

Comparison:

  • After extracting both current revisions, compare v1 and v2. Return 1 or -1 immediately if they differ.
  • If they are equal, continue to the next revision pair.

Trailing revisions:

  • When one string is exhausted first, the remaining revisions of the other string must still be compared against 0. The two cleanup while loops drain the remaining characters of version1 and version2 into v1 and v2, then the final three-way comparison handles the result.

Key insight: version "1.0" equals "1.0.0" because any unspecified trailing revision defaults to zero, and both cleanup loops leave v1 = v2 = 0 when the shorter string was already empty at that point.

Analysis
Time
O(M+N)
  • M and N are the lengths of version1 and version2. Each character is visited exactly once.
Space
O(1)
  • Only a fixed number of integer variables are used; no extra strings or arrays are allocated.
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·
Explanation

A string s is a subsequence of t if every character of s can be found in t in the same relative order, with possibly other characters in between. We do not need to find every possible alignment - the greedy approach works: always match s[a] against the earliest available character in t.

Two-pointer walk:

  • Pointer a tracks our position in s (the pattern); pointer b tracks our position in t (the text).
  • b advances on every iteration - we always move forward through t.
  • a advances only when s[a] == t[b], recording a successful match.

Why greedy is correct:

  • Suppose we skip a matching position in t hoping for a later one. That can never help: using the earliest match leaves the most remaining characters in t available for the rest of s. Taking the first opportunity is always at least as good as taking a later one.

Result:

  • After the loop, a == m means every character of s was matched in order - return True.
  • If b exhausts t while a < m, some characters of s were never matched - return False.
  • An empty s is trivially a subsequence of any t: the loop body never executes and a == 0 == m.
Analysis
Time
O(N)
  • N is the length of t. Pointer b advances on every step, so the loop runs at most N iterations. M (length of s) is bounded by N in the worst case.
Space
O(1)
  • Only two integer pointers and the two length variables are used.
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·
Explanation

Given two strings where # represents a backspace key, we need to determine whether the two strings produce the same result after all backspaces are applied. The O(1)-space approach avoids materializing the processed strings by scanning both from right to left and skipping characters that would have been deleted.

Key insight - scan from the right:

  • Processing left-to-right is hard because a # deletes the character before it - you would need to look backward. Scanning right-to-left is natural: a # tells us to skip the next non-# character we encounter, which is the one immediately to the left.

Skip counters back_a and back_b:

  • When we see a # at s[a], we increment back_a and move left. This schedules one deletion.
  • When back_a > 0 and the current character is not #, we decrement back_a and move left - this character has been "deleted" by a pending backspace.
  • The same logic applies independently to t via b and back_b.

Comparison step:

  • Once both pointers have cleared their pending skips and both point to a surviving character, we compare s[a] and t[b]. If they differ, the strings are not equal - return False immediately.
  • If they match, advance both pointers and continue.

Termination:

  • The loop continues as long as at least one pointer is still in range. After the loop, both arrays must be fully exhausted (a < 0 and b < 0) for equality. If one still has surviving characters left, they cannot match the empty other side.
Analysis
Time
O(M+N)
  • M and N are the lengths of s and t. Each pointer moves strictly left on every branch, so the total iterations are bounded by M + N.
Space
O(1)
  • Only two pointers and two skip counters are used. No processed string is ever stored.
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