Watch 5 video solutions for Incremental Memory Leak, a medium level problem involving Math, Simulation. This walkthrough by code Explainer has 2,106 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 - 1Problem Overview: Two memory sticks start with memory1 and memory2. At second i, you must allocate i units of memory to the stick with more remaining memory (choose memory1 on ties). If neither stick can handle the request, the process stops and you return the current second and the remaining memory values.
Approach 1: Simple Iterative Simulation (Time: O(√(memory1 + memory2)), Space: O(1))
This approach directly simulates the process described in the problem. Start with i = 1. At each step, compare memory1 and memory2, subtract i from the larger one, then increment i. The loop stops when neither stick has at least i memory left. The key insight is that i grows while total memory decreases, so the number of iterations is bounded by the triangular sum 1 + 2 + ... + i. With memory limits up to 10^9, the loop runs only about 60k iterations, which is easily fast enough. This method is straightforward and maps directly to the rules of the problem, making it the most readable solution using basic simulation.
Approach 2: Mathematical Cumulative Calculation (Time: O(1), Space: O(1))
The allocation pattern follows an arithmetic sequence, which allows a math-based shortcut. First compute the difference between the two memory sticks. Allocate the largest prefix of the sequence 1..k that can fit entirely into the larger stick without switching. Using the triangular number formula k(k+1)/2, you can solve for k directly. After balancing the difference, the remaining allocations alternate between the two sticks. Another arithmetic sum calculation determines how many more steps each stick can support before running out of memory. This avoids explicit iteration and computes the stopping second using constant-time formulas.
Recommended for interviews: The iterative simulation is what most interviewers expect first. It shows you can translate problem rules into code quickly and reason about runtime bounds. The mathematical approach demonstrates deeper pattern recognition with arithmetic series and is a strong optimization once the simulation behavior is understood.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iterative Simulation | O(√(memory1 + memory2)) | O(1) | Best for clarity and interviews. Directly simulates the allocation rules with minimal code. |
| Mathematical Cumulative Calculation | O(1) | O(1) | Useful when optimizing or demonstrating math insight using triangular number formulas. |