A Problem-Solving Procedure

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.