A Problem-Solving Procedure

If you start typing as soon as you hear the problem, you tend to discover too late that you misread a requirement or missed a better approach. This chapter applies a six-step procedure to a single example: clarify, work through examples, brute force, optimize, code, test.

The example problem: "Given an array nums of positive integers and a value target, return the length of the shortest contiguous subarray whose sum is at least target. If there is no such subarray, return 0."

Step 1: Clarify

Restate the problem in your own words and ask about anything ambiguous. The answers often decide which algorithm you can use.

• Are all values positive? With negatives, extending a window can make the sum smaller, which calls for a different technique.
• Can the array be empty? Should that return 0?
• How large can the array and the values be? If n can reach 100,000, O(n²) is risky.
• Do you only need the length, or also the position of the subarray?

Assume the answers are: all positive, n up to 100,000, length only.

Step 2: Work through examples

Do not rely only on the examples you are given. Build a few small ones yourself and compute the expected results by hand: one typical case plus two or three edge cases is plenty.

Step 3: Brute force

Describe the simplest solution first. For each start index, extend to the right and record the length as soon as the sum reaches the target. That is O(n²) time. Even if you do not write it out, stating it along with its complexity gives you a baseline to improve on, and the function doubles as a reference answer for testing later.

def shortest_at_least_brute(nums: list[int], target: int) -> int:
    best = 0
    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):
            total += nums[end]
            if total >= target:
                length = end - start + 1
                if best == 0 or length < best:
                    best = length
                break  # extending further only makes it longer
    return best

Step 4: Optimize

Look for repeated work in the brute force. Every time the start index moves, the sum is rebuilt from scratch. Because all values are positive, two facts hold:

• Extending the right end can only increase the sum.
• Shrinking from the left end can only decrease the sum.

So you can grow the right end one step at a time, and once the sum reaches the target, pull the left end in for as long as the condition still holds, updating the shortest length as you go. This is a variable-size sliding window. Each pointer moves at most n times, so the total is O(n). Say this out loud and get the interviewer's agreement before you start coding.

Tracing nums = [3, 1, 2, 4, 1] with target = 6:

Step 5: Code

Write the code you just described and briefly narrate why each line is there. Name variables after their roles: left, right, total.

def shortest_at_least(nums: list[int], target: int) -> int:
    left = 0
    total = 0
    best = float("inf")
    for right, value in enumerate(nums):
        total += value
        while total >= target:          # shrink while the condition holds
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else int(best)

Step 6: Test

Finishing the code is not the end. Trace the examples from step 2 line by line and check the edge cases. If time allows, mention that you would compare against the brute force on random inputs; interviewers notice that.

cases = [
    ([3, 1, 2, 4, 1], 6, 2),
    ([1, 1, 1], 5, 0),
    ([7], 7, 1),
    ([], 1, 0),
]
for nums, target, expected in cases:
    assert shortest_at_least(nums, target) == expected
    assert shortest_at_least_brute(nums, target) == expected
print("all tests passed")

Budgeting a 45-minute interview

Summary

The six steps are less a ritual than a set of guard rails. Clarifying fixes the constraints and therefore the algorithm, the brute force becomes both a baseline and a testing tool, and agreeing on the optimization before coding saves rewrites. The next chapter implements the most common patterns in real code.