Arrays, Strings, and Hashing Questions

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

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.

Direct answer

Walk the string once: skip leading whitespace, consume an optional sign, then consume digits until a non-digit character, converting as you go and clamping to the 32-bit signed integer range the moment the running value would exceed it. Overflow is detected before it happens, by comparing against a threshold, rather than by letting the value overflow and checking after the fact.

Structured elaboration

The parsing steps in order

1. Skip any leading space characters.
2. Read an optional + or -; anything else in that position (or nothing at all) means the sign defaults to positive.
3. Read consecutive digit characters, stopping at the first non-digit (including the end of the string). Everything after this point, including any trailing whitespace or trailing garbage characters, is ignored: there is no separate "trim the trailing spaces" step, because stopping the digit scan at the first non-digit already has the same effect as trimming, whatever comes after the last digit was never going to be parsed anyway.
4. If no digits were consumed at all, whether because the string was empty, all whitespace, or a sign with nothing after it, the result is invalid input and the function returns 0.
5. Apply the sign to the accumulated digits, then clamp to the 32-bit signed range: [-2147483648, 2147483647].

Detecting overflow without a big-integer library

The naive approach, accumulate the number as a normal machine integer and check afterward whether it exceeds the 32-bit range, does not work in a genuinely fixed-width language, because the multiplication and addition that build up the number can themselves overflow before you ever get to check. The safe pattern is to check BEFORE combining: given the current accumulated value num, the next digit d, and INT_MAX = 2147483647, the update num * 10 + d will exceed INT_MAX exactly when:

Since this comparison only involves num (kept within a checked range by this same rule applied to the previous digit) and small fixed constants, it never itself overflows, so you can safely bail out to the clamped INT_MAX (or INT_MIN for the negative sign) the moment the check trips, without ever needing arbitrary-precision arithmetic. In Python this exact discipline is not strictly required for correctness, since Python integers do not overflow, but it is exactly what a Java implementation of the same function needs: Java's int genuinely wraps around on overflow rather than raising an error, and Java's own Integer.parseInt throws a NumberFormatException on overflow rather than clamping, so a hand-rolled atoi in Java has to implement this check explicitly to match the clamp-on-overflow contract this problem asks for.

Treating invalid input

"Invalid" here specifically means: no digits were ever consumed. That covers an empty string, a string of only whitespace, a lone sign character with nothing after it, and a string that starts with a non-digit, non-sign, non-whitespace character. All of these return 0, matching the classic atoi contract; there is no exception path in this version of the problem.

Worked example

INT_MAX = 2**31 - 1
INT_MIN = -2**31

def string_to_int(s: str) -> int:
    i, n = 0, len(s)
    while i < n and s[i] == ' ':
        i += 1
    sign = 1
    if i < n and s[i] in '+-':
        if s[i] == '-':
            sign = -1
        i += 1
    digits_start = i
    num = 0
    while i < n and s[i].isdigit():
        digit = ord(s[i]) - ord('0')
        if num > (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        num = num * 10 + digit
        i += 1
    if i == digits_start:
        return 0
    return sign * num

for t in ["42", "   -42", "4193 with words", "words and 987", "-91283472332", "91283472332"]:
    print(repr(t), "->", string_to_int(t))

Output:

'42' -> 42
'   -42' -> -42
'4193 with words' -> 4193
'words and 987' -> 0
'-91283472332' -> -2147483648
'91283472332' -> 2147483647

The last two lines show the overflow clamp firing correctly in both directions: 91283472332 is far larger than INT_MAX, and the function returns exactly 2147483647, not a wrapped or garbage value.

Trade-offs and pitfalls

The most common bug is checking for overflow AFTER the multiply-and-add, which is unsafe once you are in a language with real fixed-width integers, since the overflow has already corrupted the value by the time you inspect it. A second common mistake is forgetting that a sign character with no digits after it (just "-", or a sign followed only by more whitespace) must return 0, not treat the sign alone as meaningful. A third is stopping only at whitespace instead of at any non-digit, which mishandles inputs like "12a34" (should return 12, not attempt to parse further digits after the letter). Finally, remember this problem's clamp-and-return-0 behavior is a deliberate simplification for interview purposes: production-grade parsers, and most standard library functions, instead raise an exception on malformed or out-of-range input, so this should not be presented as how you would design a real parsing API, only as the exact contract this problem specifies.

Direct answer

Walk through long once with a single pointer, and advance a second pointer into short only when the current character of long matches the character short is currently waiting for. If the pointer into short reaches the end before long runs out, every character of short was found in order, so short is a subsequence of long.

Structured elaboration

Approach

def is_subsequence(short, long):
    i = 0
    if not short:
        return True
    for ch in long:
        if i < len(short) and ch == short[i]:
            i += 1
        if i == len(short):
            return True
    return i == len(short)

Only one pass over long is made, and the pointer into short never moves backward, so the total work is O(n) where n is the length of long, matching the question's explicit complexity requirement. No extra data structure is needed since matching only ever needs to compare the CURRENT position of short against the current character of long.

Application context (the question's explicit ask)

This same one-pass check is the building block behind approximate matching and fuzzy token mapping: for example, checking whether a user's typed abbreviation could plausibly expand to a longer canonical term ("gcm" as a subsequence of "google cloud monitoring"), or filtering a large candidate list down to the ones that could still match a partially typed query, before applying a more expensive scoring step only to that smaller candidate set.

Worked example

Executed with python3 s83.py, five pinned cases including two explicit edge cases (empty short, empty long):

is_subsequence('abc', 'ahbgdc')     = True  expected=True  match=True
is_subsequence('axc', 'ahbgdc')     = False expected=False match=True
is_subsequence('', 'anything')      = True  expected=True  match=True
is_subsequence('abc', '')           = False expected=False match=True
is_subsequence('ace', 'abcde')      = True  expected=True  match=True

'abc' is found in order inside 'ahbgdc' (a, then b, then c, each appearing later than the last), so it returns True. 'axc' fails because after matching 'a', no 'x' appears anywhere later in 'ahbgdc', so the pointer into short never reaches the end.

Trade-offs and pitfalls

• The empty-short-is-always-a-subsequence edge case (is_subsequence('', 'anything') returning True) is easy to get backwards if the loop logic is written slightly differently; the explicit if not short: return True guard above makes this an intentional decision rather than an accident of how the loop happens to terminate.
• If this check needs to run many times against the SAME long string with many different short candidates, a smarter structure (precomputing, for each position and character, the next occurrence of that character) avoids repeating the full O(n) scan per query, at the cost of O(n * alphabet size) preprocessing; that preprocessing trade is only worth it when the number of queries against the same long string is large.
• This only answers yes/no. If the caller also needs the actual matched positions in long (for example, to highlight which characters satisfied the match), track and return the index list as the pointer advances, rather than just the boolean.

Direct answer

Use a read/write two-pointer: walk the array once with a read index, and every time you see a value that isn't val, copy it into the next open slot tracked by a write index. The write index at the end is the new length. Whether order must be preserved decides which of two variants you use: the read/write copy above preserves the original relative order in O(n) writes; if order doesn't matter, you can instead swap a matching element with the current last element and shrink the array, which does fewer writes when val is rare.

Approach

1. Order-preserving (read/write two-pointer): write starts at 0. For each read index in order, if nums[read] != val, copy it to nums[write] and advance write. Every kept element lands in its original relative order, one slot earlier than or at its original position.
2. Order-not-preserved (swap-with-last): keep a shrinking logical length n. When nums[i] == val, overwrite it with nums[n-1] (the current last element) and shrink n by one, without advancing i (the swapped-in element still needs to be checked). When nums[i] != val, advance i. This does one write per removal instead of potentially shifting every later element, which is cheaper when matches are rare and scattered.
3. Both mutate nums in place and return the new length; elements at or past the returned length are not meaningfully defined afterward.

Complexity

Both variants: O(n) time (single pass), O(1) extra space. The order-preserving version always does one write per surviving element; the swap variant does one write per removed element, which is fewer when val is rare.

Edge cases

• val not present at all: every element is kept, new length equals original length, zero writes beyond the initial pass.
• All elements equal val: new length is 0.
• Empty input: returns 0 immediately.

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    del nums[write:]
    return write


def remove_element_unordered(nums, val):
    i = 0
    n = len(nums)
    while i < n:
        if nums[i] == val:
            n -= 1
            nums[i] = nums[n]
        else:
            i += 1
    del nums[n:]
    return n


payload = [4, 2, 5, 2, 7, 2, 9]
k = remove_element(payload, 2)
print(k, payload)

payload2 = [4, 2, 5, 2, 7, 2, 9]
k2 = remove_element_unordered(payload2, 2)
print(k2, payload2)

Output:

4 [4, 5, 7, 9]
4 [4, 9, 5, 7]

Both agree on the count (4 surviving elements), but the surviving values land in different positions: [4, 5, 7, 9] keeps the original left-to-right order, while [4, 9, 5, 7] does not (9 moved from the end into an earlier slot during a swap), which is exactly the trade-off the question is asking about.

Trade-offs and pitfalls

• A common bug: using list.remove(val) or deleting elements from the middle of the array inside a loop, which is O(n) per removal (everything after the deletion point shifts down), making the whole operation O(n^2) in the worst case, and it also skips the next element if you don't adjust the loop index after a deletion. The two-pointer approaches here avoid both problems.
• The same read/write two-pointer technique applies directly to low-level, fixed-size buffers, not just Python lists. In C, given a null-terminated char *s, removing all space characters in place is the identical idea: a write index and a read index both walk the buffer, the write index only advances when the current character should be kept, and a null terminator is placed at the final write position. There's no list-resize step (del nums[write:]) because a C string doesn't carry a separate length field the way a Python list does; the null terminator is the length.
• Backend-cleanup framing from the question: "compacting payload arrays before storage" is exactly the order-preserving case if the array represents an ordered sequence (e.g. a time-ordered log) where reordering would corrupt meaning, or the order-not-preserved case if it's an unordered set of records where minimizing writes matters more than position.