Arrays, Strings, and Hashing Questions

Direct answer

Compare characters column by column across all the strings at once (vertical scanning): at each position i, check that every string shares the same character at that position. The first mismatch, or the first string that runs out of characters, marks the end of the common prefix. This is simple, correct, and exits as soon as a genuine mismatch is found, rather than fully comparing whole strings pairwise the way a naive approach might.

Structured elaboration

Vertical scanning approach

def longest_common_prefix_vertical(strs):
    if not strs:
        return ""
    for i, ch in enumerate(strs[0]):
        for other in strs[1:]:
            if i >= len(other) or other[i] != ch:
                return strs[0][:i]
    return strs[0]

O(n*m) naive complexity (the question's explicit ask)

With n strings and m the length of the shortest string, ANY correct approach touches at most n * m character comparisons in the worst case, imagine every string identical except for a mismatch right at the very last position checked. Vertical scanning does not beat this worst-case bound; what it buys you is exiting early on realistic negative cases, where a mismatch is usually found within the first handful of characters and strings, not at the theoretical worst-case position.

Binary-search-on-prefix-length approach (the question's explicit ask)

Binary search over candidate prefix lengths from 0 to the shortest string's length, using an O(n*m) helper ("is this length a common prefix of every string") as the check at each step:

def _is_common_prefix(strs, length):
    prefix = strs[0][:length]
    return all(s[:length] == prefix for s in strs)


def longest_common_prefix_binary_search(strs):
    if not strs:
        return ""
    min_len = min(len(s) for s in strs)
    lo, hi = 0, min_len
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if _is_common_prefix(strs, mid):
            lo = mid
        else:
            hi = mid - 1
    return strs[0][:lo]

Being honest about what this buys you: the per-step check itself costs O(nm) in the worst case, and binary search runs that check O(log m) times, so the WORST-CASE complexity of this version is actually O(n * m * log m), asymptotically worse than vertical scanning's O(nm), not better. Binary-search-over-the-answer is a genuinely useful general problem-solving pattern, and it can pay off here if the per-length check can be made cheap (for example, comparing precomputed rolling hashes of each candidate-length prefix instead of a fresh character-by-character comparison every time), but for the plain character-comparison check shown above, it is not a real optimization over vertical scanning. If a true asymptotic improvement is the goal, the standard technique is building a trie once over all the strings and walking it, which finds the common prefix in a single O(S) pass, where S is the total character count across all strings.

Worked example

Executed with python3 s78.py, both approaches run on the same inputs and confirmed to agree:

['flower', 'flow', 'flight']                  vertical='fl'       binary_search='fl'       agree=True
['dog', 'racecar', 'car']                     vertical=''         binary_search=''         agree=True
['interview', 'internal', 'interstate']       vertical='inter'    binary_search='inter'    agree=True
['single']                                    vertical='single'   binary_search='single'   agree=True

['flower', 'flow', 'flight'] maps to 'fl', matching the question's own stated example exactly.

Trade-offs and pitfalls

• Do not claim the binary-search version is asymptotically faster than vertical scanning for the plain per-length character check shown here; it is not, and overclaiming this specific trade-off is a common mistake that a careful interviewer will probe.
• Vertical scanning's early exit is a genuine, practical win on typical negative inputs (most real-world string sets diverge within the first few characters), even though its worst-case bound matches the fully naive pairwise approach.
• Edge cases worth naming explicitly: an empty list of strings (handled here by convention, returning ""), a single string (the whole string is trivially its own prefix), and one empty string anywhere in the list (the prefix is immediately "", which the vertical-scan loop handles correctly since strs[0] may be empty and its enumerate simply never executes).

Direct answer

Group strings that are anagrams of each other by mapping each string to a canonical key that is identical for all of its anagrams and different otherwise, then bucket strings by that key in a hash map. The two standard keys are the sorted-character string (simple, O(L log L) per string) and a fixed-length character-frequency vector (O(L) per string, faster for long strings, but only straightforward for a small, known, fixed alphabet).

Structured elaboration

Approach 1: sorted string as key

Sort each string's characters and join them back into a string; two strings are anagrams exactly when this sorted form is identical. Sorting a string of length L costs O(L log L), so grouping n strings this way costs O(n * L log L) in total, where L is the average or maximum string length.

Approach 2: frequency vector as key

Count the occurrences of each character into a fixed-size array (26 entries for lowercase English letters), then use that array, converted to an immutable tuple so it can be a hash-map key, as the grouping key. Building the count for one string costs O(L), so this approach costs O(n * (L + alphabet_size)) in total, asymptotically better than the sorted-key approach once L is large relative to log L, since counting avoids the sort entirely. The trade-off is that this fixed-size-array trick assumes a small, KNOWN alphabet; it does not generalize as cleanly the moment the alphabet is unbounded.

Unicode input

Both approaches need care once the input can contain arbitrary Unicode text rather than plain lowercase English letters. The frequency-vector approach's fixed 26-slot array breaks down immediately, since Unicode text can contain far more than 26 distinct characters; the practical fix is a hash map from character to count instead of a fixed array, which still works but loses the small constant-factor advantage of a fixed array. More subtly, even the sorted-key approach can give a WRONG answer on Unicode input if two visually and semantically identical strings are represented by different underlying code point sequences: an accented character can be represented either as a single precomposed code point, or as the base letter followed by a separate combining accent mark. These compare as different strings and produce different sorted keys even though they represent the same text. The fix is to first normalize every string using Unicode Normalization Form C (NFC), which canonicalizes precomposed and decomposed forms to the same representation, before computing either kind of key.

Performance for long strings and memory trade-offs

For long strings, the frequency-vector approach avoids the L log L sorting cost, which matters when strings are long, for example grouping DNA-like sequences or long tokenized identifiers rather than short English words. Memory-wise, the sorted-key approach's key is proportional to the string's own length, while the frequency-vector key has a FIXED size (26 entries, or however many distinct characters the chosen alphabet has) regardless of the string's length, which can be smaller for long strings but is pure overhead for very short ones.

Worked example

from collections import defaultdict
import unicodedata

def group_anagrams_sorted_key(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

def group_anagrams_freq_key(strs, alphabet_size=26):
    groups = defaultdict(list)
    for s in strs:
        counts = [0] * alphabet_size
        for ch in s:
            counts[ord(ch) - ord('a')] += 1
        groups[tuple(counts)].append(s)
    return list(groups.values())

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams_sorted_key(strs))
print(group_anagrams_freq_key(strs))

def normalize_for_unicode_anagram_key(s):
    return ''.join(sorted(unicodedata.normalize('NFC', s)))

precomposed = "café"          # single code point for e-acute
decomposed = "café"          # 'e' + combining acute accent
print(precomposed == decomposed)
print(''.join(sorted(precomposed)) == ''.join(sorted(decomposed)))
print(normalize_for_unicode_anagram_key(precomposed) == normalize_for_unicode_anagram_key(decomposed))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
False
False
True

Both approaches group the same six words into the same three anagram groups. The Unicode section demonstrates the normalization issue directly: two strings that print identically and represent the same visible text, cafe with an accented e built from a single precomposed code point versus the same word built from a base letter plus a separate combining accent mark, compare as unequal Python strings, and their naive sorted-character keys also disagree, but normalizing both to NFC before computing the key makes them match, exactly the correctness gap this section describes.

Trade-offs and pitfalls

A common mistake is assuming string equality in Python already handles Unicode normalization: it does not, two strings built from a precomposed versus a decomposed representation of the same visible text can compare as unequal, which silently splits what should be one anagram group into two. A second is hardcoding a 26-entry frequency array without checking the actual input alphabet, which either crashes on characters outside a-z or silently produces wrong groupings once real-world text with punctuation, digits, or non-English characters shows up. For genuinely massive input, the scale this problem is asked at in a batch-processing context, well beyond what fits comfortably in memory as one hash map, the practical extension is external-memory or streaming grouping: sort the (key, original-string) pairs using an external merge sort so anagrams become adjacent on disk without needing every group held in memory at once, or shard by a prefix of the key across multiple workers so each worker only needs to hold its own shard's groups in memory. That is a genuine and reasonable extension of this same technique at scale, but it is a distinct system-design problem from choosing a grouping key, and is mentioned here only as the natural next question, not as something this answer needs to design in full. The same two key strategies carry over unchanged in Java (HashMap<String, List<String>> or HashMap<List<Integer>, List<String>>) and JavaScript (a Map keyed on the same sorted-string or frequency-array-as-string idea).

Direct answer

Expand a window from the right, adding each new element to a running sum. The moment the running sum reaches or exceeds the target, record the window's length as a candidate answer and shrink from the left for as long as the sum still qualifies, since every valid window found this way is a candidate for the minimum. Track the smallest length seen across the whole single pass.

Structured elaboration

Approach

def min_subarray_len(s, nums):
    n = len(nums)
    left = 0
    window_sum = 0
    best = n + 1
    for right in range(n):
        window_sum += nums[right]
        while window_sum >= s:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return 0 if best == n + 1 else best

Why this requires positive numbers (the question's explicit ask)

The sliding-window technique relies on the running sum changing MONOTONICALLY as each pointer moves: adding an element (moving right) can only ever increase the sum, and removing an element (moving left) can only ever decrease it, if and only if every element is positive. That monotonicity is exactly what justifies greedily shrinking the window without ever needing to re-check a wider window later: once the sum drops below the target after removing the leftmost element, removing MORE elements from the left is guaranteed to keep it below target too, since removing a positive number is always a strict decrease. If the array could contain zero or negative values, adding an element to the right would no longer guarantee the sum increases, so a window that currently fails the threshold might still succeed if extended further, and the greedy shrink-from-the-left step is no longer safe. The standard fallback for arrays with negative numbers is prefix sums combined with a monotonic deque, or, for exact-sum variants, prefix sums indexed in a hash map.

Variant: count subarrays with product strictly less than k

A related ask uses the identical two-pointer skeleton, but tracks a running PRODUCT instead of a sum, and counts how many valid windows END at each right pointer rather than tracking a minimum length:

def num_subarrays_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    left = 0
    product = 1
    count = 0
    for right, x in enumerate(nums):
        product *= x
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1
    return count


def brute_force_count(nums, k):
    """O(n^2) reference: enumerate every subarray's product directly, with
    no window-shrinking logic to trust. Used only to cross-check the
    two-pointer version above, not as the real answer."""
    n = len(nums)
    count = 0
    for i in range(n):
        product = 1
        for j in range(i, n):
            product *= nums[j]
            if product < k:
                count += 1
    return count

The key insight that makes the counting step correct: for a fixed right pointer, every subarray from index left..right, left+1..right, ..., all the way to right..right, is also valid, since removing elements from the front of a window whose product is already below the threshold (with all-positive elements) can only make the product smaller or equal. So the count of newly valid subarrays ending exactly at right is right - left + 1, added once per right-pointer step. This again relies on positive integers for the same monotonicity reason as above.

Worked example

Executed with python3 s81.py (both the two-pointer function and the brute-force reference defined above):

min_subarray_len(s=7, nums=[2, 3, 1, 2, 4, 3]) = 2
min_subarray_len(s=100, nums=[1, 2, 3]) = 0

The window [4, 3] sums to 7 in exactly 2 elements, the shortest possible; with a target of 100 and a maximum possible total sum of 6, no window can ever reach it, so the function correctly returns 0.

num_subarrays_product_less_than_k(nums=[10, 5, 2, 6], k=100) = 8
brute_force_count(nums=[10, 5, 2, 6], k=100) = 8

The brute-force reference (shown above) agrees exactly: 8 qualifying subarrays out of 10 possible non-empty subarrays for a 4-element array.

Trade-offs and pitfalls

• The two-pointer approach is O(n) time and O(1) extra space; that is the entire value proposition over a brute-force O(n^2) (or worse) scan, and interviewers expect BOTH the working code AND the positivity argument for why the greedy shrink is valid, not just code that happens to pass test cases.
• A common bug in the counting variant is omitting the if k <= 1: return 0 guard: with k <= 1, no product of positive integers can ever be strictly less than k, and the main loop's while product >= k shrink condition would otherwise push left past right and read a stale or out-of-range element.
• It is easy to conflate "smallest window that reaches a target" (this problem, returning a length) with "count every window satisfying a condition" (the other variant, returning a count); keep straight which of the two output shapes a given question is actually asking for, since the bookkeeping each one needs is different even though the window-management code looks nearly identical.

Direct answer

Add the two digit strings exactly the way long addition is done by hand: walk both strings from the rightmost digit, add the corresponding digits plus any carry from the previous position, keep the ones digit as the result and carry the tens digit forward, and continue until both strings and the carry are exhausted. This never converts the whole number into a native integer type, runs in O(max(len(a), len(b))) time and space, and generalizes directly to any base by changing how individual digits are parsed and re-emitted.

Structured elaboration

Why this can't just use native integer addition. The entire point of the exercise is that the numbers may be arbitrarily large decimal strings, potentially larger than any fixed-width integer type can represent without an arbitrary-precision ("big-int") library; the question explicitly disallows using one, so digits are processed as characters, not as a machine integer.

The right-to-left digit-pair-plus-carry loop. Two index pointers start at the last character of each string and move left. At each step, the digit from a (or 0 if that pointer has run past the start of a) is added to the digit from b (or 0, similarly) plus the carry from the previous step. The result's ones digit (total % 10) is appended to the output, and the new carry is the tens digit (total // 10). The loop continues as long as either pointer still has digits left, or a carry is still pending, which correctly handles the case where the final addition produces an extra leading digit (e.g. 9 + 9 = 18, carrying a new leading 1).

Reversal at the end. Because digits are produced from least-significant to most-significant (processing right to left), the accumulated digit list is in reverse order relative to the final answer and must be reversed once before joining into the output string.

Generalizing to base 16 or other bases. The algorithm's structure doesn't change at all between bases; only two things change: how a single character is parsed into its numeric digit value, and how a numeric digit value is turned back into a character. In decimal, int(digit) and str(digit) handle this. For an arbitrary base b (2 through 36), Python's int(digit, b) parses a single base-b digit character (handling both decimal digits and letters a through z for bases above 10), and indexing into a fixed alphabet string (\"0123456789abcdefghijklmnopqrstuvwxyz\") re-emits a digit value as its base-b character. The carry logic is identical, just with % base and // base replacing % 10 and // 10.

Worked example

Full runnable code with pinned test cases, including the question's own large-number example, verified against Python's own native big-integer addition as ground truth (used here only to cross-check the from-scratch implementation, not as a substitute for it):

def add_strings(a, b):
    """Add two non-negative decimal-string integers without big-int libs.
    O(max(len(a), len(b))) time and space, single right-to-left pass with
    a carry, exactly like manual long addition."""
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    digits = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i]) if i >= 0 else 0
        db = int(b[j]) if j >= 0 else 0
        total = da + db + carry
        digits.append(str(total % 10))
        carry = total // 10
        i -= 1
        j -= 1
    return ''.join(reversed(digits))


def add_strings_base(a, b, base):
    """Same algorithm generalized to an arbitrary base (2-36), using
    int(digit, base) to parse and a base-N string alphabet to re-emit."""
    digits_alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    out = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i], base) if i >= 0 else 0
        db = int(b[j], base) if j >= 0 else 0
        total = da + db + carry
        out.append(digits_alphabet[total % base])
        carry = total // base
        i -= 1
        j -= 1
    return ''.join(reversed(out))


if __name__ == "__main__":
    a = "9876543210123456789"
    b = "1234567890987654321"
    result = add_strings(a, b)
    expected_via_python_int = str(int(a) + int(b))
    print(f"add_strings({a!r}, {b!r})")
    print(f"  result   = {result}")
    print(f"  expected = {expected_via_python_int} (cross-checked via Python's native int addition)")
    print(f"  match: {result == expected_via_python_int}")

    more_tests = [
        ("0", "0", "0"),
        ("1", "9", "10"),
        ("99", "1", "100"),
        ("123", "0", "123"),
    ]
    for x, y, exp in more_tests:
        r = add_strings(x, y)
        print(f"add_strings({x!r}, {y!r}) = {r} (expected {exp})")

    hex_result = add_strings_base("ff", "1", 16)
    print(f"add_strings_base('ff', '1', 16) = {hex_result} (expected 100)")

Output (actual run):

add_strings('9876543210123456789', '1234567890987654321')
  result   = 11111111101111111110
  expected = 11111111101111111110 (cross-checked via Python's native int addition)
  match: True
add_strings('0', '0') = 0 (expected 0)
add_strings('1', '9') = 10 (expected 10)
add_strings('99', '1') = 100 (expected 100)
add_strings('123', '0') = 123 (expected 123)
add_strings_base('ff', '1', 16) = 100 (expected 100)

This confirms the question's own stated example: '9876543210123456789' + '1234567890987654321' -> '11111111101111111110' is correct, verified both by the character-by-character implementation and by cross-checking against Python's native arbitrary-precision integer addition on the same inputs. The base-16 example ('ff' + '1' = '100' in hex, i.e. 255 + 1 = 256) confirms the generalization: the carry chain propagates through both hex digits exactly as it would for 99 + 1 = 100 in decimal.

Trade-offs and pitfalls

• Converting both strings to native integers, adding, and converting back (str(int(a) + int(b))) is the obvious shortcut and was used above only as a cross-check, not as the answer: for genuinely arbitrary-precision inputs in a language without native big-int support (or under an explicit "no big-int library" constraint, as this question states), this shortcut isn't available at all, which is the entire point of the exercise.
• A common bug is forgetting the final carry: if the loop condition doesn't check carry as an independent continuation condition (only checking i >= 0 or j >= 0), an addition like 9 + 9 (which produces 18, needing an extra leading digit) silently drops the final carry digit.
• Building the result with repeated string concatenation (result = digit + result instead of appending to a list and reversing once at the end) works but is less efficient in languages or situations where string concatenation is O(current length) per operation, making a naive left-prepend approach O(n^2) overall instead of O(n); appending to a list and reversing once avoids this.
• This implementation assumes both inputs are non-negative digit strings with no sign character or leading-zero ambiguity beyond a literal "0"; supporting signed values would require detecting and handling a leading - or + before the digit-processing loop, which is a real but separate extension.
• The base generalization above supports bases 2 through 36 only, since it relies on Python's int(digit, base) and a 36-character alphabet; supporting arbitrary bases beyond 36 would require a different, explicitly-provided digit alphabet rather than reusing 0-9a-z.

Direct answer

An array gives O(1) random access because an index maps directly to a memory address via arithmetic, but inserting or deleting anywhere except the very end requires shifting every following element, an O(n) operation. A singly linked list gives O(1) insert or delete once you already hold a reference to the relevant node, but finding that node in the first place (including "the middle") costs O(n), since there is no arithmetic shortcut, only following pointers one at a time.

Structured elaboration

• The "O(1) insert" caveat, worth stating explicitly. A linked-list insert or delete is only O(1) when you ALREADY have a reference to the right node, typically because you're iterating and acting as you go. If you're only given a numeric position (say, "insert at index 500,000"), you still have to walk there first, which costs O(n); claiming a flat "O(1) insert" without that condition is the single most common oversimplification of this comparison.
• Concrete scenario favoring the array. A lookup table mapping millions of user IDs to profile records, queried by index or key extremely frequently: O(1) random access is the whole point, and the data is rarely inserted into at arbitrary positions.
• Concrete scenario favoring the linked list. An eviction-order list for a cache, where an arbitrary, already-known node is frequently removed from the middle and a new node re-inserted at the front; both operations are O(1) once you hold the node reference, with no shifting cost regardless of list size.

Worked example

Consider inserting one new element at the FRONT of a collection holding 1,000,000 items. On an array, every one of the 1,000,000 existing elements must shift one position to make room, an O(n) cost that scales with however large the array has grown. On a singly linked list, the operation is exactly two pointer writes (the new node's next pointer, and the head pointer), regardless of whether the list holds 10 elements or 10,000,000: the cost does not grow with list size at all. This is the concrete shape of the O(n)-versus-O(1) difference in the table above, not just an abstract notation.

Trade-offs & pitfalls

• Memory overhead and cache locality. Each linked-list node carries at least one extra pointer (8 bytes on a 64-bit system) beyond its payload, and nodes are not stored contiguously in memory. For an iteration-heavy workload, an array is often noticeably faster IN PRACTICE despite both being asymptotically O(n), because sequential array access is cache-friendly while pointer-chasing a linked list typically is not; this is a constant-factor, hardware-driven effect, not a difference in asymptotic complexity.
• The most common oversimplification is stating "linked-list insert/delete is O(1)" without the caveat that this assumes the relevant node reference is already in hand; always confirm whether the scenario gives you the node or just a position.
• Singly linked lists only walk forward. Anything that needs "delete the node before this one" or other backward movement needs either a doubly linked list, or tracking a trailing pointer while iterating forward.
• Don't confuse this with dynamic-array append. A dynamic array (Python's list, Java's ArrayList) amortizes appending at the END to O(1) via geometric growth, which is a different operation from inserting at an ARBITRARY position; conflating the two is a common mistake when reasoning about array costs.