Incremental Memory Leak - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Simple Iterative Approach
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.
Complexity
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.
Approach 2: Mathematical Cumulative Calculation
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.
Code
Python
Complexity
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).
Approach 3: Simulation
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.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Leetcode 1860.Incremental Memory Leak||Biweekly contest 52||Code + Explanation + example walkthrough • Code with Alisha • 614 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Incremental Memory Leak easy or hard?
Incremental Memory Leak Python/Java solution
How to solve Incremental Memory Leak in O(1)?
What is the best approach for Incremental Memory Leak?
Is Incremental Memory Leak asked at Google/Amazon/Meta?
What data structure is used in Incremental Memory Leak?
What is the time complexity of Incremental Memory Leak?
Ready to solve this problem?
Practice Incremental Memory Leak with our built-in code editor and test cases.
Practice on FleetCode