Scale Engineer

Incremental Memory Leak

Med
#1699Time: 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.
Patterns
Math

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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].

Walkthrough

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.

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};    }}

Complexity

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.

Trade-offs

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.

Solutions

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};  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem