Sign of the Product of an Array · Optimal Solution

Flip the sign. Never multiply.

A financial ledger records daily gain/loss multipliers for a portfolio — positive for gains, negative for losses, zero if the account was frozen. Before rendering the balance indicator, the system must determine whether the cumulative effect is positive, negative, or zero — without computing the potentially enormous product itself. One scan, flipping a running sign on each negative and bailing at the first zero, answers the question in O(n) time and O(1) space.

Interactive

Watch the sign oscillate

Concept

Three rules, no arithmetic

The product's sign depends only on how many negatives appear and whether any zero is present. Magnitudes are irrelevant — -100 flips the sign exactly like -1.

zero dominates

If any element is zero, the entire product is zero. The scan terminates immediately — no subsequent value can change the outcome.

negative flips

Each negative value flips the running sign. Positive values leave it unchanged. The magnitude of each factor is never used.

parity decides

Even number of flips returns the sign to positive. Odd number leaves it negative. That is the entire logic.

Algorithm

Scan, flip, or bail

A single pass through the array with a running sign variable that starts at +1.

  1. 1

    Initialize running sign as +1

    The identity element for multiplication. No factors examined yet — the sign is positive by default.

  2. 2

    For each element

    If the value is 0, return 0 immediately. If the value is negative, flip the running sign: sign = −sign. If positive, do nothing.

  3. 3

    Return the running sign

    After all elements: the running sign is the answer. +1 for positive product, −1 for negative. No overflow. No multiplication.

Edge Cases

Where the sign tells the story

The running sign's final state encodes everything the problem asks for.

All positive — no flips

When every element is positive, the sign never flips. The scan is effectively a zero-check — confirming no zero exists. The result is +1.

Zero terminates early

The moment a zero is encountered, the product is zero regardless of remaining elements. The scan halts — values after the zero are never examined. This is the only early termination case.

Overflow avoidance

The naive approach of multiplying all values overflows even 64-bit integers for large arrays. Tracking only the sign — a single bit of information — makes overflow impossible and the solution trivially correct.