Array manipulation

For each position, return the product of every other element, without division.

Trigger

'Without division' plus 'all other elements' — the prefix/suffix pattern.

Approach

1. Division is banned (and would break on zeros anyway) — say why it is banned before moving on.
2. Each answer is prefix product × suffix product.
3. Two passes: fill the output with prefixes left to right, then multiply by suffixes right to left with a running variable.
4. That gives O(1) extra space, since the output does not count.

Target complexity

O(n) time, O(1) extra space.

Pitfall

Allocating two full arrays. Correct, but the interviewer is asking for the constant-space version.

Say it out loud

“Division is off the table, and it would break on zeros regardless. Each answer is the prefix product times the suffix product, so I do a left-to-right pass into the output and then a right-to-left pass with a single running variable — that keeps the extra space constant.”

Solve on LeetCode

Sort an array of three distinct values in one pass, in place.

Trigger

'Three values', 'one pass', 'constant space' — the Dutch national flag.

Approach

1. Counting sort in two passes is valid — say it first.
2. One pass: three pointers, low, mid and high. Everything below low is 0, above high is 2.
3. The subtlety: after swapping with high, do **not** advance mid — the incoming value is unseen.

Target complexity

O(n) time, O(1) space, one pass.

Pitfall

Advancing mid after the swap with high. You skip an unexamined element.

Say it out loud

“Two passes with counts is the easy answer. One pass is the Dutch flag partition with three pointers. The detail that catches people: when I swap with the high pointer, the value I receive hasn't been examined yet, so I don't advance the middle pointer.”

Solve on LeetCode