# Incremental Memory Leak **Difficulty:** MEDIUM [External](https://leetcode.com/problems/incremental-memory-leak) Canonical: https://scaleengineer.com/dsa/problems/incremental-memory-leak **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math) --- ## Problem You are given two integers `memory1` and `memory2` representing the available memory in bits on two memory sticks. There is currently a faulty program running that consumes an increasing amount of memory every second. At the `ith` second (starting from 1), `i` bits of memory are allocated to the stick with **more available memory** (or from the first memory stick if both have the same available memory). If neither stick has at least `i` bits of available memory, the program **crashes**. Return _an array containing_ `[crashTime, memory1crash, memory2crash]`_, where_ `crashTime` _is the time (in seconds) when the program crashed and_ `memory1crash` _and_ `memory2crash` _are the available bits of memory in the first and second sticks respectively_. **Example 1:** **Input:** memory1 = 2, memory2 = 2 **Output:** [3,1,0] **Explanation:** The memory is allocated as follows: - At the 1st second, 1 bit of memory is allocated to stick 1. The first stick now has 1 bit of available memory. - At the 2nd second, 2 bits of memory are allocated to stick 2. The second stick now has 0 bits of available memory. - At the 3rd second, the program crashes. The sticks have 1 and 0 bits available respectively. **Example 2:** **Input:** memory1 = 8, memory2 = 11 **Output:** [6,0,4] **Explanation:** The memory is allocated as follows: - At the 1st second, 1 bit of memory is allocated to stick 2. The second stick now has 10 bit of available memory. - At the 2nd second, 2 bits of memory are allocated to stick 2. The second stick now has 8 bits of available memory. - At the 3rd second, 3 bits of memory are allocated to stick 1. The first stick now has 5 bits of available memory. - At the 4th second, 4 bits of memory are allocated to stick 2. The second stick now has 4 bits of available memory. - At the 5th second, 5 bits of memory are allocated to stick 1. The first stick now has 0 bits of available memory. - At the 6th second, the program crashes. The sticks have 0 and 4 bits available respectively. **Constraints:** * `0 <= memory1, memory2 <= 231 - 1` # Approaches ## Simple Iterative Simulation This approach directly simulates the memory allocation process second by second. It's the most straightforward way to solve the problem and is efficient enough given the problem constraints. **Time:** O(sqrt(M)), where M is the total initial memory (`memory1 + memory2`). The total memory consumed up to time `t` is the sum `1 + 2 + ... + t`, which is `t*(t+1)/2`. The loop runs until this sum approaches `M`, so `t^2` is proportional to `M`, which means `t` is proportional to `sqrt(M)`. · **Space:** O(1), as it only requires a few variables to store the current time and memory values, regardless of the input size. **Pros:** Very simple to understand and implement.; Robust and not prone to complex logical errors or floating-point inaccuracies.; Sufficiently efficient for the given constraints, passing within the time limit. **Cons:** May perform a large number of iterations if the initial memory values are very large.; Slower than a mathematical approach for cases where one memory stick is vastly larger than the other. ### Explanation We use a loop that increments a `time` variable, starting from 1. In each iteration, we determine which memory stick has more available memory (or stick 1 if they are equal). We then check if that stick has enough memory to cover the current `time` requirement. If it does, we subtract the memory and continue to the next second. If not, the program crashes, and we exit the loop. The final `time` and the remaining memory in both sticks are the result. ```java class Solution { public int[] memLeak(int memory1, int memory2) { long m1 = memory1; long m2 = memory2; long time = 1; while (Math.max(m1, m2) >= time) { if (m1 >= m2) { m1 -= time; } else { m2 -= time; } time++; } return new int[]{(int) time, (int) m1, (int) m2}; } } ``` ### Algorithm - Initialize a time counter `i` to 1. - Enter a loop that runs as long as an allocation is possible. - Inside the loop, compare `memory1` and `memory2`. - If `memory1 >= memory2`, check if `memory1 >= i`. If yes, update `memory1 -= i`. If no, break the loop. - If `memory2 > memory1`, check if `memory2 >= i`. If yes, update `memory2 -= i`. If no, break the loop. - Increment the time counter `i`. - When the loop terminates, `i` is the crash time. Return `[i, memory1, memory2]`. ## Optimized Simulation with Mathematical Jumps This approach improves upon the simple simulation by calculating in advance how many consecutive allocations can be made from the dominant memory stick. Instead of iterating one second at a time, it can 'jump' forward in time, which is particularly effective when there's a large disparity between `memory1` and `memory2`. **Time:** Worst case is O(sqrt(M)), same as the simple simulation, which occurs when memory values stay close and `k` is always small. Best/Average case is much better, potentially O((log M)^2), as each jump significantly reduces the remaining memory and increases the time quadratically. · **Space:** O(1), as it only uses a fixed number of variables for its calculations. **Pros:** Significantly more efficient than simple simulation when initial memory values are far apart.; Reduces a large number of loop iterations into a few mathematical calculations. **Cons:** Much more complex to implement correctly.; Involves floating-point arithmetic (`Math.sqrt`), which can have precision issues if not handled carefully.; In the worst-case scenario (memory values remain close), it degenerates to the performance of the simple simulation, but with higher overhead per step. ### Explanation The simulation is divided into phases. In each phase, one memory stick has more memory than the other. Let's assume `memory1 >= memory2`. We can mathematically determine the maximum number of steps, `k`, that can be taken from `memory1` before either it runs out of memory or its value drops below `memory2`. This calculation involves solving a quadratic equation to find how many steps can be taken before the memory difference is overcome. Once `k` is found, we check if `memory1` has enough memory for these `k` allocations. If yes, we update `memory1` and `time` in a single operation. If no, a crash is imminent, and we calculate the exact number of steps until the crash, update the state, and terminate. This avoids many small iterations of the simpler approach. ```java class Solution { public int[] memLeak(int memory1, int memory2) { long m1 = memory1; long m2 = memory2; long time = 1; while (true) { if (m1 >= m2) { if (m1 < time) break; long diff = m1 - m2; long b = 2 * time - 1; double k_double = (-b + Math.sqrt((double)b * b + 8 * diff)) / 2.0; long k = (long) k_double; if (k == 0) { m1 -= time++; continue; } long needed = k * time + k * (k - 1) / 2; if (m1 >= needed) { m1 -= needed; time += k; } else { k_double = (-b + Math.sqrt((double)b * b + 8 * m1)) / 2.0; long k_crash = (long) k_double; needed = k_crash * time + k_crash * (k_crash - 1) / 2; m1 -= needed; time += k_crash; break; } } else { if (m2 < time) break; long diff = m2 - m1; long b = 2 * time - 1; double k_double = (-b + Math.sqrt((double)b * b + 8 * diff)) / 2.0; long k = (long) k_double; if (k == 0) { m2 -= time++; continue; } long needed = k * time + k * (k - 1) / 2; if (m2 >= needed) { m2 -= needed; time += k; } else { k_double = (-b + Math.sqrt((double)b * b + 8 * m2)) / 2.0; long k_crash = (long) k_double; needed = k_crash * time + k_crash * (k_crash - 1) / 2; m2 -= needed; time += k_crash; break; } } } return new int[]{(int) time, (int) m1, (int) m2}; } } ``` ### Algorithm - Initialize `time`, `m1`, `m2` using `long` to handle large values. - In a loop, first determine the dominant memory stick (e.g., `m1 >= m2`). - Calculate `k`, the number of steps that can be taken from the dominant stick before it's no longer guaranteed to be dominant. This involves solving the quadratic inequality `d >= k*t + k*(k-1)/2`, where `d` is the memory difference and `t` is the current time. - If `k` is 0, simply perform one step of the simulation and continue. - Calculate the total memory `needed` for these `k` steps. - If the dominant stick has `>= needed` memory, update its value and the time, then continue the loop. - If the dominant stick has `< needed` memory, a crash will occur. Solve another quadratic equation to find the exact number of steps until the crash, update the state, and break the loop. - Repeat this process, alternating between sticks as their relative memory changes. - Return the final state `[time, m1, m2]`. # Solutions ### Java ```java class Solution { public int[] memLeak(int memory1, int memory2) { int i = 1; for (; i <= Math.max(memory1, memory2); ++i) { if (memory1 >= memory2) { memory1 -= i; } else { memory2 -= i; } } return new int[]{i, memory1, memory2}; } } ``` ### JavaScript ```javascript /** * @param {number} memory1 * @param {number} memory2 * @return {number[]} */ var memLeak = function (memory1, memory2) { let i = 1; for (; i <= Math.max(memory1, memory2); ++i) { if (memory1 >= memory2) { memory1 -= i; } else { memory2 -= i; } } return [i, memory1, memory2]; }; ``` ### CPP ```cpp class Solution { public: vector memLeak(int memory1, int memory2) { int i = 1; for (; i <= max(memory1, memory2); ++i) { if (memory1 >= memory2) { memory1 -= i; } else { memory2 -= i; } } return {i, memory1, memory2}; } }; ``` ### Python ```python class Solution: def memLeak(self, memory1: int, memory2: int) -> List[int]: i = 1 while i <= max(memory1, memory2): if memory1 >= memory2: memory1 -= i else: memory2 -= i i += 1 return [i, memory1, memory2] ```