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.
The problem can be approached by allocating the memory in a loop, where we start allocating 1 bit of memory in the first second, 2 bits in the second second, and so on. We always allocate to the stick with more available memory. If both sticks have the same amount of memory, we choose the first stick. The process continues until neither stick has enough memory to accommodate the required bits.
This C code snippet implements an iterative approach where memory is allocated to the stick with more available memory. If both are equal, the memory is allocated to the first stick. The process continues until it can no longer allocate `i` bits at the `i`th second. The crash time and remaining memory in both sticks are recorded.
Time complexity: O(sqrt(N)), where N is the initial total memory, due to the arithmetic progression of increments in memory allocation. Space complexity: O(1), constant space is used.
This approach uses a formulaic method to determine the exact second when the system crashes without running a loop up till that point. By calculating cumulative allocations and comparing with initial memory, we can quickly deduce the crash point.
The mathematical approach reduces iterations by leveraging arithmetic sequence properties, here modeled mathematically to quickly bond over how many second intervals the subsequent memory would need and approximate point of failure through direct deduction.
Python
Time Complexity: Reduced using mathematical predictions compared to a simple iterative process, aiming for O(logN) at cost of complexity. Space Complexity: Meanwhile kept at O(1).
We directly simulate the allocation of memory.
Assume t is the moment of unexpected exit, then the two memory sticks can definitely accommodate the memory consumed at the moment t-1 and before, so we have:
$
sum_{i=1}^{t-1} i = \frac{ttimes (t-1)}{2} leq (m_1+m_2)
The time complexity is O(\sqrt{m_1+m_2}), where m_1 and m_2$ are the sizes of the two memory sticks respectively.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Simple Iterative Approach | Time complexity: O(sqrt(N)), where N is the initial total memory, due to the arithmetic progression of increments in memory allocation. Space complexity: O(1), constant space is used. |
| Mathematical Cumulative Calculation | Time Complexity: Reduced using mathematical predictions compared to a simple iterative process, aiming for O(logN) at cost of complexity. Space Complexity: Meanwhile kept at O(1). |
| Simulation | — |
| 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. |
Leetcode Biweekly Contest 52 | Problem 1859 , 1860 , 1861 | LEETCODE • code Explainer • 2,106 views views
Watch 4 more video solutions →Practice Incremental Memory Leak with our built-in code editor and test cases.
Practice on FleetCode