Incremental Memory Leak

Incremental Memory Leak is LeetCode 1860. You have two memory sticks with memory1 and memory2 bytes of available memory. At each second i (starting at 1), you allocate i bytes to the stick with more available memory. If both sticks have the same amount, you allocate to stick 1. The process continues until neither stick has enough memory for the next allocation, at which point the system crashes. Return the crash second and the remaining memory on both sticks.

The approach

This is a pure simulation problem. You do not need any clever data structures or tricky algorithms. Just walk through each second one at a time:

1. Start with i = 1.
2. Compare memory1 and memory2.
3. If memory2 is strictly greater than memory1, subtract i from memory2. Otherwise subtract i from memory1 (this handles ties, since the problem says to prefer stick 1 when they are equal).
4. Increment i.
5. If neither stick has at least i bytes remaining, return [i, memory1, memory2].

The key insight is that you only need to check whether the larger stick (or stick 1 when tied) has enough memory. If the larger one cannot handle the allocation, the smaller one certainly cannot either.

The solution

def mem_leak(memory1, memory2):
    i = 1
    while True:
        if memory1 >= memory2:
            if memory1 < i:
                return [i, memory1, memory2]
            memory1 -= i
        else:
            if memory2 < i:
                return [i, memory1, memory2]
            memory2 -= i
        i += 1

The loop runs until one allocation fails. At each step, you pick the stick with more memory (stick 1 if tied), check whether it can hold i bytes, and either allocate or crash.

Visual walkthrough

Let's trace through the simulation with memory1 = 2, memory2 = 2. Watch how the memory bars shrink at each second, and notice when the crash happens.

The system crashes at second 3 because neither stick can hold 3 bytes. The answer is [3, 1, 0].

The math shortcut

The simulation runs in O(sqrt(memory1 + memory2)) time because you are subtracting 1, then 2, then 3, and so on. The sum 1 + 2 + ... + k equals k * (k + 1) / 2, so you run roughly sqrt(2 * total) steps before exhausting memory. For the given constraints (memory values up to 2^31 - 1), that is about 65,000 iterations at most. The simulation is fast enough.

If you wanted to skip ahead, you could binary search for the largest k such that k * (k + 1) / 2 fits within the total memory, then simulate only the last few seconds to figure out the exact split. But the direct simulation is clean and well within time limits, so there is no reason to add that complexity here.

Complexity analysis

Time: each iteration subtracts an increasing amount from the total pool. The sum 1 + 2 + ... + k grows quadratically, so the number of iterations is proportional to the square root of the total memory.

Space: you only track three variables: i, memory1, and memory2. No arrays, no extra data structures.

Building blocks

This problem exercises two fundamental patterns.

Loop simulation. You walk through a process step by step, updating state at each iteration. The same pattern appears in problems like Game of Life, Spiral Matrix, and any problem where the instructions say "repeat until some condition." The skill is translating the problem description into a clean loop with the right termination condition.

Greedy allocation. At each step, you allocate to the stick with the most available memory. This greedy rule keeps the sticks balanced for as long as possible, which maximizes the number of seconds before a crash. You do not need to prove optimality here (the problem tells you the rule), but recognizing greedy decision-making helps you spot it in harder problems.

Edge cases

• One stick starts at 0. Every allocation goes to the other stick until it runs out. The simulation handles this naturally since memory2 > memory1 (or vice versa) always picks the non-zero stick.
• Both sticks start at 0. The very first allocation (i = 1) cannot be handled. Return [1, 0, 0].
• Very large values. With memory1 and memory2 up to 2^31 - 1, the total memory can be about 4.3 billion. The square root of that is about 65,000 iterations, which runs in under a millisecond.
• One stick much larger than the other. The larger stick absorbs most of the early allocations. Eventually the smaller stick catches up and they alternate. The simulation handles all of this without special cases.

From understanding to recall

Simulation problems like this feel easy when you read the solution. The logic maps directly to the problem statement. But that is exactly what makes them tricky to retain. A month from now, will you remember to check the larger stick first? Will you remember that ties go to stick 1, not stick 2?

The gap between understanding a solution and reproducing it under pressure is real. Spaced repetition closes that gap. You type the solution from scratch, and the system schedules your next review right before you would forget. After a few reps, the simulate-compare-subtract loop becomes automatic.

Related posts

• Design Memory Allocator - Another memory allocation problem where you simulate allocate and free operations on an array
• Happy Number - A loop simulation that runs until a condition is met or a cycle is detected
• Sqrt(x) - Uses the same square-root relationship between input size and iteration count

---

Want to lock in simulation patterns? CodeBricks breaks each problem into building blocks and drills them at increasing intervals, so the patterns stick.