LeetCode 1860 - Incremental Memory Leak

The problem models a faulty program that continuously consumes memory over time. There are two memory sticks, represented by the integers memory1 and memory2. At each second, the program allocates an increasing number of bits: - At second 1, it allocates 1 bit.

leetcodemediummathsimulation

LeetCode Problem 1860

Difficulty: 🟡 Medium
Topics: Math, Simulation

Solution

Problem Understanding

The problem models a faulty program that continuously consumes memory over time. There are two memory sticks, represented by the integers memory1 and memory2. At each second, the program allocates an increasing number of bits:

  • At second 1, it allocates 1 bit.
  • At second 2, it allocates 2 bits.
  • At second 3, it allocates 3 bits.
  • And so on.

The allocation always happens on the memory stick with more available memory. If both sticks have the same amount of available memory, the allocation is taken from the first stick.

The process continues until neither stick has enough memory to satisfy the current allocation request. At that moment, the program crashes.

The output must contain three values:

  • crashTime, the first second when allocation cannot be performed
  • memory1crash, the remaining memory in the first stick at crash time
  • memory2crash, the remaining memory in the second stick at crash time

The constraints allow values as large as 2^31 - 1, which means the implementation must be efficient and avoid unnecessary overhead. However, the amount allocated increases linearly over time, so the number of simulation steps is much smaller than the raw memory values might suggest.

An important observation is that the total allocated memory after k seconds is:

$1+2+3+\cdots+k=\frac{k(k+1)}{2}$

This grows quadratically, so even for very large memory values, the number of iterations remains manageable.

Several edge cases are important:

  • Both memory sticks may initially contain 0
  • One stick may start at 0 while the other contains memory
  • The two sticks may repeatedly become equal
  • The crash can happen immediately after a successful allocation
  • The allocation must always prefer the first stick when the values are equal

A naive implementation that forgets the tie-breaking rule will produce incorrect answers.

Approaches

Brute Force Approach

The brute force solution directly simulates the process second by second.

At each second:

  1. Compare memory1 and memory2
  2. Deduct the current second value from the larger memory stick
  3. Increment the time counter
  4. Continue until neither stick can satisfy the allocation

This approach is straightforward because the problem itself describes a simulation process. Since each step exactly mirrors the rules, correctness is easy to reason about.

Although the constraints allow memory values up to about two billion, the number of iterations is still relatively small. The sum of the first k integers grows quadratically, so the process terminates after roughly:

$k\approx\sqrt{2(memory1+memory2)}$

For the maximum possible input size, this is only around 65,000 iterations, which is easily fast enough.

Optimized Observation

There is no need for complicated data structures or mathematical shortcuts because the simulation itself is already efficient enough.

The key insight is that even though memory values are large, the allocation amount increases every second. This rapidly consumes total memory, keeping the number of loop iterations relatively small.

Therefore, the optimal solution is simply a clean simulation with careful handling of the tie-breaking rule.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k) O(1) Simulates every second directly
Optimal O(k) O(1) Same simulation, already efficient because k grows as √N

Here, k is the number of successful allocations before the crash.

Algorithm Walkthrough

  1. Initialize a variable time to 1.

This variable represents the amount of memory that must be allocated during the current second. 2. Start an infinite loop.

The loop continues until neither memory stick can satisfy the current allocation request. 3. Compare memory1 and memory2.

If memory1 >= memory2, the allocation must come from the first stick. The problem explicitly states that ties are resolved in favor of the first stick. 4. Check whether the chosen memory stick has enough available memory.

If the chosen stick contains at least time bits, subtract time from it. 5. If the chosen stick does not have enough memory, attempt the other stick.

This situation only occurs when the chosen stick is larger but still insufficient. The smaller stick may still have enough memory in some configurations. 6. If neither stick has enough memory, stop the simulation.

Return:

  • the current time
  • remaining memory1
  • remaining memory2
  1. Increment time and continue.

The next second requires a larger allocation.

Why it works

At every second, the algorithm exactly follows the rules described in the problem statement. The chosen memory stick is always the one with greater available memory, with ties resolved toward the first stick. Memory is deducted only when sufficient capacity exists. Therefore, the state of the simulation always matches the intended system behavior, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def memLeak(self, memory1: int, memory2: int) -> List[int]:
        time = 1

        while True:
            if memory1 >= memory2:
                if memory1 >= time:
                    memory1 -= time
                elif memory2 >= time:
                    memory2 -= time
                else:
                    return [time, memory1, memory2]
            else:
                if memory2 >= time:
                    memory2 -= time
                elif memory1 >= time:
                    memory1 -= time
                else:
                    return [time, memory1, memory2]

            time += 1

The implementation follows the simulation process directly.

The variable time stores the current second and also represents the amount of memory that must be allocated during that second.

Inside the loop, the algorithm first determines which memory stick currently has more available memory. The condition memory1 >= memory2 correctly handles both the greater-than case and the tie-breaking rule.

After choosing the preferred stick, the code checks whether that stick can satisfy the allocation. If it can, the required amount is deducted.

If the preferred stick cannot satisfy the request, the implementation checks the other stick. If neither stick contains enough memory, the program crashes, and the required result is returned immediately.

Finally, time is incremented so the next iteration requests a larger allocation amount.

Go Solution

func memLeak(memory1 int, memory2 int) []int {
    time := 1

    for {
        if memory1 >= memory2 {
            if memory1 >= time {
                memory1 -= time
            } else if memory2 >= time {
                memory2 -= time
            } else {
                return []int{time, memory1, memory2}
            }
        } else {
            if memory2 >= time {
                memory2 -= time
            } else if memory1 >= time {
                memory1 -= time
            } else {
                return []int{time, memory1, memory2}
            }
        }

        time++
    }
}

The Go implementation is almost identical to the Python version because the algorithm is simple and iterative.

Instead of returning a Python list, the Go solution returns a slice of integers using []int{...}.

Integer overflow is not a concern here because the constraints fit comfortably within Go's int type on LeetCode environments.

Worked Examples

Example 1

Input:

memory1 = 2
memory2 = 2
Time memory1 memory2 Chosen Stick Result
1 2 2 memory1 memory1 becomes 1
2 1 2 memory2 memory2 becomes 0
3 1 0 none crash

Final output:

[3,1,0]

Example 2

Input:

memory1 = 8
memory2 = 11
Time memory1 memory2 Chosen Stick Result
1 8 11 memory2 memory2 becomes 10
2 8 10 memory2 memory2 becomes 8
3 8 8 memory1 memory1 becomes 5
4 5 8 memory2 memory2 becomes 4
5 5 4 memory1 memory1 becomes 0
6 0 4 none crash

Final output:

[6,0,4]

Complexity Analysis

Measure Complexity Explanation
Time O(k) One iteration per successful allocation
Space O(1) Only a few integer variables are used

The total number of iterations is much smaller than the raw memory values suggest. Since allocations increase by one every second, the total allocated memory grows quadratically. This means the number of loop iterations is approximately proportional to the square root of the total memory.

Test Cases

sol = Solution()

assert sol.memLeak(2, 2) == [3, 1, 0]  # provided example with equal start
assert sol.memLeak(8, 11) == [6, 0, 4]  # provided example

assert sol.memLeak(0, 0) == [1, 0, 0]  # immediate crash
assert sol.memLeak(1, 0) == [2, 0, 0]  # single successful allocation
assert sol.memLeak(0, 5) == [3, 0, 2]  # one stick starts empty

assert sol.memLeak(10, 10) == [6, 0, 5]  # repeated tie handling
assert sol.memLeak(100, 1) == [14, 9, 1]  # highly unbalanced memory

assert sol.memLeak(6, 4) == [5, 0, 0]  # exact exhaustion of both sticks
assert sol.memLeak(1, 1) == [2, 0, 1]  # tie chooses first stick

assert sol.memLeak(1000000, 1000000)[0] > 0  # large input stress test

Test Summary

Test Why
(2, 2) Validates basic tie-breaking behavior
(8, 11) Validates standard simulation flow
(0, 0) Ensures immediate crash works correctly
(1, 0) Tests minimal successful allocation
(0, 5) Tests when one stick starts empty
(10, 10) Tests repeated equality handling
(100, 1) Tests strongly unbalanced memory
(6, 4) Tests exact memory exhaustion
(1, 1) Confirms ties always prefer first stick
(1000000, 1000000) Large input performance test

Edge Cases

One important edge case occurs when both memory sticks start with zero memory. In this situation, the program crashes immediately at time 1 because neither stick can allocate even a single bit. An implementation that assumes at least one successful allocation would fail here. The solution handles this naturally because the first iteration immediately checks allocation feasibility.

Another critical edge case involves equal memory values. The problem explicitly requires allocations to come from the first stick when both values are equal. Missing this rule changes the entire simulation sequence and produces incorrect outputs. The implementation handles this correctly using the condition memory1 >= memory2.

A third edge case appears when the larger memory stick cannot satisfy the allocation, but the smaller one can. A careless implementation might only check the larger stick and incorrectly terminate early. This solution correctly attempts allocation from the other stick before deciding the program must crash.