0

Maximize minus signs with positive prefix sums

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Maximize minus signs with positive prefix sums

Companies: Amazon

Difficulty: Medium

Problem statement

You are given a list of positive integers nums = [a1, a2, ..., an]. Put a sign, + or -, in front of each number. Keep the order.

After each position i, the running total of the signed numbers (±a1 ± a2 ... ± ai) must be strictly greater than zero.

Return the largest number of - signs you can use while every running total stays positive.

def max_negative_signs(nums: list[int]) -> int: ...

Constraints

  • 0 <= n <= 10^5
  • 1 <= nums[i] <= 10^9

Example 1

nums = [4, 3, 1, 2]
output: 2

4 + 3 - 1 - 2 gives running totals 4, 7, 6, 4. Using 4 - 3 early leaves a total of 1, which then blocks both later values, so it is worse.

Example 2

nums = [1, 1, 1, 1]
output: 1

1 + 1 - 1 + 1 gives 1, 2, 1, 2. Any second - makes some running total 0, which is not allowed.

Note: the first number always gets +.

Approach

Every value is a positive integer. We walk left to right and decide a sign for
each one. The running total after each position must stay strictly above zero.
We want as many minus signs as possible.

Brute force. Try all 2^n sign patterns, keep those whose prefix sums are
all positive, and take the one with the most minus signs. This is fine for
n <= 20 and is a good checker, but it is exponential.

Greedy with a max-heap. Flipping value x from + to - lowers every
later prefix sum by 2x. So when two choices give the same number of minus
signs, the one that flipped smaller values leaves more room for the future.

Scan left to right and keep:

  • total: the current prefix sum under our chosen signs.
  • flipped: a max-heap of the values we have made negative so far.

For each x:

  1. Tentatively make it negative: total -= x, push x onto the heap.
  2. If total <= 0, the prefix is broken. Undo the largest flipped value
    so far: pop y, total += 2y. The count of minus signs is unchanged
    compared with before step 1 (we added one, removed one), but the set of
    flipped values is now as small as it can be.

One undo is always enough. Before step 1 we had total_prev > 0. After step 1
and popping y >= x, the total is total_prev - x + 2y >= total_prev + x > 0.

Why it is optimal. Invariant after processing the first i values: the
heap holds the maximum possible number k of minus signs for that prefix, and
among all valid choices with k minus signs its values have the smallest
possible sum. That gives the largest possible total, so it dominates any other
choice for every future step. Adding x either keeps all k + 1 (still valid,
and nothing better exists) or forces us back to k, where dropping the largest
of the k + 1 candidates gives the minimum-sum set of size k. This is the
same exchange argument as "Course Schedule III" and the minimum-refuelling
problem.

The first value can never be negative: its prefix sum would be -a1 < 0. The
greedy handles this on its own (it flips a1, sees total <= 0, undoes it).

Code

import heapq
from itertools import product


def max_negative_signs(nums: list[int]) -> int:
    """Return the most minus signs we can assign so every prefix sum stays > 0."""
    total = 0
    flipped: list[int] = []  # max-heap of negated values (stored as -value)
    for x in nums:
        total -= x
        heapq.heappush(flipped, -x)
        if total <= 0:
            largest = -heapq.heappop(flipped)
            total += 2 * largest
    return len(flipped)


def assign_signs(nums: list[int]) -> list[int]:
    """Return one optimal signed list (same values, chosen signs)."""
    total = 0
    flipped: list[tuple[int, int]] = []  # (-value, index)
    for i, x in enumerate(nums):
        total -= x
        heapq.heappush(flipped, (-x, i))
        if total <= 0:
            neg_val, _ = heapq.heappop(flipped)
            total += 2 * -neg_val
    negative = {i for _, i in flipped}
    return [-x if i in negative else x for i, x in enumerate(nums)]


def brute_force(nums: list[int]) -> int:
    best = 0
    for signs in product((1, -1), repeat=len(nums)):
        total, ok = 0, True
        for s, x in zip(signs, nums):
            total += s * x
            if total <= 0:
                ok = False
                break
        if ok:
            best = max(best, signs.count(-1))
    return best


if __name__ == "__main__":
    import random

    assert max_negative_signs([5]) == 0
    assert max_negative_signs([5, 1, 1, 1, 1]) == 4
    assert max_negative_signs([2, 3, 1, 1]) == 2
    assert max_negative_signs([1, 1, 1, 1]) == 1
    assert max_negative_signs([4, 3, 1, 2]) == 2
    assert max_negative_signs([10, 9, 1, 1]) == 2
    assert max_negative_signs([]) == 0

    signed = assign_signs([4, 3, 1, 2])
    run = 0
    for v in signed:
        run += v
        assert run > 0
    assert sum(v < 0 for v in signed) == 2

    for _ in range(2000):
        arr = [random.randint(1, 9) for _ in range(random.randint(1, 10))]
        assert max_negative_signs(arr) == brute_force(arr), arr
        out = assign_signs(arr)
        run = 0
        for v in out:
            run += v
            assert run > 0
        assert sum(v < 0 for v in out) == brute_force(arr)
    print("ok")

Complexity

  • max_negative_signs / assign_signs: O(n log n) time (one push and at
    most one pop per element), O(n) space for the heap.
  • brute_force: O(n * 2^n) time, O(n) space. Use it only to check answers.

Test cases

  • [5] → 0 (the first value can never be negative).
  • [] → 0.
  • [5, 1, 1, 1, 1] → 4: 5 - 1 - 1 - 1 - 1 = 1 > 0.
  • [1, 1, 1, 1] → 1: 1 + 1 - 1 + 1. A second minus would bring some
    prefix sum to 0, which is not positive.
  • [2, 3, 1, 1] → 2: 2 + 3 - 1 - 1. Flipping 3 gives -1, so it stays
    +.
  • [4, 3, 1, 2] → 2: the greedy first flips 3 (4 - 3 = 1), then must
    undo a flip at 1, drops 3 instead of 1, and ends with 4 + 3 - 1 - 2 = 4.
  • [10, 9, 1, 1] → 2: flipping 9 early looks good (10 - 9 = 1) but
    blocks both 1s; swapping it out gives 10 + 9 - 1 - 1.
  • Randomised: 2,000 random arrays of length up to 10 match the brute force.

Follow-ups

  • Return the signs, not just the count. Store (value, index) in the heap,
    as assign_signs does. Ties do not matter for the count.
  • Non-negative instead of positive prefix sums. Change the check to
    total < 0. With zeros allowed in the input, a zero can always be flipped
    for free.
  • Some positions are fixed (must be + or must be -). Forced - values
    are subtracted and never pushed on the heap. If the total drops to <= 0,
    keep popping the largest optional flip until it recovers; if the heap is
    empty and it still fails, there is no valid assignment.
  • Each minus sign has a weight (score) and we maximise total weight. The
    greedy no longer works directly. With small value ranges, use a DP over the
    current prefix sum (dp[s] = best weight), O(n * S).
  • Streaming input / online queries. The algorithm is already one pass; the
    answer after each prefix is len(heap) at that moment, so it can answer
    "best so far" after every element.

Interviewer expectations

Mid-level (L4)

  • Restates the rule: strictly positive prefix sums, and the first value is
    always +.
  • Notices the simple greedy "flip if it still fits" fails on [10, 9, 1, 1].
  • Reaches the heap fix with some hints and codes it cleanly.

Senior (L5)

  • Gets to the max-heap swap without hints and explains why one pop is enough.
  • Gives the exchange argument: same count, smallest flipped sum, so the
    largest remaining total.
  • Writes a brute-force checker or careful hand traces, and covers edge cases.

Staff (L6+)

  • Connects the pattern to Course Schedule III and refuelling-style problems,
    and states the invariant precisely.
  • Handles the follow-ups: forced signs, non-strict bound, weighted signs (and
    why the greedy breaks there).
  • Talks about testing strategy (random tests against brute force) and limits
    such as integer overflow in other languages.

Sign in to comment, vote or remix.