CODEWITHSUNDEEP
algorithmprefix-sum
rohit
rohit

Reputation: 103

Minimum reallocations required to make all prefix sum >=0

Give an Array of integers eg : 10, -10, -1, -1, 10 . I have to find minimum reallocations such that all the prefix sums of the array are >=0. The sum of all elements in the array
is assumed to be non-negative. In the above example, we can move -10 to the end of the array to make all prefix sum positive. Not sure how to approach this problem efficiently. Where taking a number and inserting it anywhere else is to be treated as one reallocation. The problem is to be solved for one more type of reallocation :

  1. Any negative number can be moved to the end of the array

Upvotes: 5

Views: 2409

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

We can scan left to right, moving the minimum integer scanned so far to the end each time the sum of scanned integers goes negative. The proof idea is that, if we compare what this greedy algorithm does to any optimal solution OPT, whenever greedy and OPT have moved the same number of integers, greedy’s total moved is less than or equal (i.e., larger, since we’re moving negative numbers) than OPT’s, therefore greedy never does a move that puts it behind OPT.

import heapq


def min_relocations(lst):
    relocations = 0
    heap = []
    total = 0
    for x in lst:
        heapq.heappush(heap, x)
        total += x
        if total < 0:
            relocations += 1
            total -= heapq.heappop(heap)
    return relocations

Upvotes: 4

Related Questions