Miscellaneous

The problems here do not share a pattern, which is exactly why they are worth doing. Nothing transfers as a template. What transfers is the habit of reading the specification precisely and deciding what happens at the edges before writing the loop.

That said, three of them do teach a technique of their own, and those techniques show up again elsewhere. This article covers those three, and then the part that is genuinely just care.

Prefix and suffix sweeps#

Product of Array Except Self is the one to learn properly. The question — for every position, the product of everything else — looks like it needs a nested loop, and the tempting shortcut is to multiply everything once and divide by each element as you go.

That shortcut is banned in the problem statement, and it would be wrong anyway: a single zero in the input makes the total zero and the division undefined. Worth saying out loud, because it shows you spotted the case rather than just obeying the constraint.

The real idea is that each answer splits cleanly in two — everything to the left of a position, times everything to its right — and each of those halves is a running product you can build in one sweep.

Watch the out row get written twice. The first sweep leaves each cell holding only the left-hand product, which is a partial answer, not a wrong one. The second sweep comes back the other way and finishes each cell by multiplying in the right-hand product — carried in a single variable, which is why no second array is ever allocated.

out = array of size n

left = 1
for i = 0 .. n - 1:
    out[i] = left                 // everything before i
    left = left * nums[i]

right = 1
for i = n - 1 .. 0:
    out[i] = out[i] * right       // times everything after i
    right = right * nums[i]

return out

O(n) time and O(1) extra space, since the output array does not count. The trick worth keeping is not the product — it is using the output array as scratch space for a partial result, which turns two auxiliary arrays into none.

Prefix sums in general#

The same shape solves a much broader family. Precompute pre[i] = sum of the first i elements, and the sum of any range [l, r) becomes pre[r] - pre[l] — one subtraction instead of a loop, so a thousand range queries cost a thousand subtractions after one O(n) pass.

The version worth recognising is prefix sums keyed in a hash map: if two prefix sums are equal, the stretch between them sums to zero, and more generally pre[j] - pre[i] == k means the subarray from i to j sums to k. That converts “count subarrays summing to k” from O(n²) into a single pass. It is the highest-value idea in this article by some distance, and it has a page of its own: prefix sums.

Traversing a matrix by boundaries#

Spiral Matrix is not a graph problem, however much it looks like one. There is no search — the path is completely determined — so the whole task is bookkeeping, and the clean way to do that bookkeeping is to track four boundaries and shrink them.

top = 0;  bottom = rows - 1
left = 0; right = cols - 1

while top <= bottom and left <= right:
    for c = left .. right:      emit m[top][c]
    top = top + 1

    for r = top .. bottom:      emit m[r][right]
    right = right - 1

    if top <= bottom:                              // re-check!
        for c = right .. left:  emit m[bottom][c]
        bottom = bottom - 1

    if left <= right:                              // re-check!
        for r = bottom .. top:  emit m[r][left]
        left = left + 1

The two re-checks are the entire difficulty, and leaving them out produces code that passes every square example and fails on a single row. Once top has been incremented past bottom, the third pass would walk a row that has already been emitted — in reverse — and duplicate it. The first two passes need no such guard because the while condition was just checked; the last two do, because two boundaries have moved since.

The alternative formulation uses direction vectors and turns right whenever the next cell is out of bounds or already visited. It is shorter but needs a visited grid, so the boundary version is usually the better answer when the interviewer asks for O(1) extra space.

The transferable habit here is smaller than a technique: when a traversal shrinks its own bounds, re-test the bounds after every change, not once per iteration.

Parsing, where the specification is the problem#

Two problems here are exercises in reading carefully.

Roman to Integer has one insight and it is a small one: the numeral system is additive except where a smaller symbol precedes a larger one, which means subtraction. So scan left to right and compare each symbol with the one after it — if it is smaller, subtract it, otherwise add it. No table of the six special pairs is needed, and building one is the sign of having missed the rule.

total = 0
for i = 0 .. n - 1:
    if i + 1 < n and value(s[i]) < value(s[i + 1]):
        total = total - value(s[i])
    else:
        total = total + value(s[i])

String to Integer (atoi) has no insight at all, which is the point. It is a specification with about six clauses, and the only way to get it right is to enumerate them before typing:

1. Skip leading whitespace — and only leading.
2. An optional single + or -.
3. Digits, until the first non-digit, which ends the number rather than failing.
4. No digits at all means return 0.
5. Clamp to the 32-bit signed range, at both ends.
6. Everything after the number is ignored.

Clause 5 is the one that bites. In a language with fixed-width integers, checking for overflow after it has happened is undefined or wrong — the test has to be made before the multiply, by asking whether the running value already exceeds INT_MAX / 10. In a language with arbitrary-precision integers, accumulate freely and clamp at the end.

Problems like this are testing whether you turn a wall of prose into a checklist. Writing the six clauses in comments first, then filling them in, is both the fastest route and the one that reads best to an interviewer.

Longest Common Prefix rounds out the group. Scan character position by character position across all the strings at once, and stop at the first disagreement or the first string that has run out. The answer can never be longer than the shortest input, which is the bound that makes the O(total characters) cost obvious. Sorting the array and comparing only the first and last string also works — they differ the earliest — but it costs a sort to save nothing.

The part that is just care#

What these problems really test is edge-case discipline, and that is a checklist rather than an idea. Before writing anything, ask:

• Empty input. An empty array, an empty string, an empty list of strings. Several of these problems return something specific rather than crashing.
• One element. Single-element arrays and single-row or single-column matrices — the case Spiral Matrix breaks on.
• All identical, or all different. The two ends of the distribution.
• Negatives and zero. Zero is what breaks the division shortcut above; negatives break assumptions about products growing.
• Overflow. Whenever values are multiplied or accumulated, and especially in a language where integers wrap.
• The boundary itself. Does the range include its endpoint? See closed and half-open intervals — the same question, in a different costume.

Say these out loud as you read the problem. It costs thirty seconds, it is the thing the interviewer is actually assessing on problems like these, and it is much cheaper than discovering the case in a failed submission.

Recognising it#

There is no signal to recognise, which is the honest answer. But there are two useful prompts:

• If a problem asks for something about every position, in terms of the rest of the array, think prefix and suffix sweeps before nested loops.
• If a problem statement is long and full of clauses rather than short and puzzling, it is a parsing problem. Turn the prose into a numbered list first; the code follows mechanically.

Summary#

Three techniques worth keeping: split each answer into a left part and a right part and sweep twice, using the output array as scratch; when a traversal shrinks its own bounds, re-check them after every change; and when the specification is the problem, write it out as a checklist before writing code. The rest is care — and on this group of problems, care is precisely the thing being measured.