Minimum Relocations to Avoid Debt

A coding challenge from Microsoft interviews involving array manipulation and prefix sums.

Problem Statement

A company has a list of expected revenues and payments for the upcoming year in chronological order. The problem is that at some moments in time the sum of previous payments can be larger than the total previous revenue. This would put the company in debt.

To avoid this problem, the company takes a very simple approach: it reschedules some expenses to the end of the year.

Task

Given an array A of N integers, where:

• Positive numbers represent revenues
• Negative numbers represent expenses

Find the minimum number of relocations (moving a negative number to the end of the array) so that the company never falls into debt.

In other words: ensure there is no consecutive sequence of elements starting from the beginning of the array that sums to a negative number.

Constraints

• N is an integer within the range [1…100,000]
• Each element of array A is an integer within the range [-1,000,000,000…1,000,000,000]
• Sum of all elements in A is nonnegative (guaranteed to have a valid solution)

Examples

Example 1: A = [10, -10, -1, -1, 10]

• Function should return 1
• Move -10 to the end: [10, -1, -1, 10, -10]
• Running sums: 10, 9, 8, 18, 8 (all non-negative)

Example 2: A = [-1, -1, -1, 1, 1, 1, 1]

• Function should return 3
• Move all three -1s at the beginning to the end
• Result: [1, 1, 1, 1, -1, -1, -1]

Example 3: A = [5, -2, -3, 1]

• Function should return 0
• Running sums: 5, 3, 0, 1 (all non-negative)

Solution

using System;
using System.Collections.Generic;

class Solution
{
    public int solution(int[] A)
    {
        int relocations = 0;
        long runningSum = 0;

        // Use a max-heap to track expenses (as positive values)
        var maxHeap = new PriorityQueue<long, long>();

        for (int i = 0; i < A.Length; i++)
        {
            runningSum += A[i];

            // If it's an expense, add its absolute value to the heap
            if (A[i] < 0)
            {
                maxHeap.Enqueue(-A[i], A[i]);  // priority is negative for max-heap
            }

            // If we're in debt, relocate the largest expense
            while (runningSum < 0 && maxHeap.Count > 0)
            {
                long largestExpense = maxHeap.Dequeue();
                runningSum += largestExpense;  // "remove" the expense
                relocations++;
            }
        }

        return relocations;
    }
}

Solution Explanation

Greedy Approach with Max-Heap

1. Track running sum as we iterate through the array
2. Keep expenses in a max-heap (priority queue)
3. When running sum goes negative, remove the largest expense seen so far
4. Continue until running sum is non-negative

Why Greedy Works

• We want to minimize relocations
• When we must relocate, we should relocate the largest expense
• This gives us the most “room” to absorb future expenses
• The largest expense can be any expense we’ve seen so far (not just current)

Complexity Analysis

• Time Complexity: O(N log N) - each element can be added/removed from heap once
• Space Complexity: O(N) - heap can contain all expenses in worst case

Alternative Solution (Without Heap)

For a simpler approach when heap isn’t available:

public int SolutionSimple(int[] A)
{
    int relocations = 0;
    long runningSum = 0;
    var expenses = new List<long>();

    for (int i = 0; i < A.Length; i++)
    {
        runningSum += A[i];

        if (A[i] < 0)
        {
            expenses.Add(-A[i]);
        }

        while (runningSum < 0 && expenses.Count > 0)
        {
            // Find and remove maximum expense
            int maxIdx = 0;
            for (int j = 1; j < expenses.Count; j++)
            {
                if (expenses[j] > expenses[maxIdx])
                    maxIdx = j;
            }

            runningSum += expenses[maxIdx];
            expenses.RemoveAt(maxIdx);
            relocations++;
        }
    }

    return relocations;
}

Note: This simple solution is O(N²) in worst case.

Test Cases

// Test case 1
int[] a1 = { 10, -10, -1, -1, 10 };
Console.WriteLine(solution(a1));  // Expected: 1

// Test case 2
int[] a2 = { -1, -1, -1, 1, 1, 1, 1 };
Console.WriteLine(solution(a2));  // Expected: 3

// Test case 3
int[] a3 = { 5, -2, -3, 1 };
Console.WriteLine(solution(a3));  // Expected: 0

// Test case 4: All positive
int[] a4 = { 1, 2, 3, 4 };
Console.WriteLine(solution(a4));  // Expected: 0

// Test case 5: Single expense at start
int[] a5 = { -5, 10 };
Console.WriteLine(solution(a5));  // Expected: 1

// Test case 6: Large numbers
int[] a6 = { 1000000000, -1000000000 };
Console.WriteLine(solution(a6));  // Expected: 0

Key Insights

1. Greedy is optimal - Always relocating the largest expense minimizes total relocations
2. Order matters for relocation - We can only relocate expenses we’ve already “seen”
3. Use long for running sum - Integers can overflow with values up to 1 billion
4. Max-heap efficiency - PriorityQueue in .NET uses min-heap by default, so we negate values

Edge Cases to Consider

• Empty array: return 0
• All positive: return 0
• All expenses at start: relocate as needed
• Large values: use long to prevent overflow

Sources

• C#/Intrebari interviu/Interviu Microsoft/problema3_1.png