# Unexpected Memory Limit Exceeded -- Possible LeetCode bug!

• During the contest, I had to code this question twice, because my first attempt got memory limit exceeded. After the contest, I saw similar solutions to my MLE solution got accepted! Here is the solution that gets MLE:

``````class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
vector<vector<int>> DP(1001, vector<int>(1001));
int ans = 0;
for (int i = A.size()-1; i >= 0; --i) {
for (int j = 0; j < B.size(); ++j) {
if (A[i] == B[j]) {
DP[i][j] = DP[i+1][j+1]+1;
ans = max(ans, DP[i][j]);
}
}
}
return ans;
}
};
``````

I want to point out that this appears to be a faithful, idomatic C++ translation of the intended solution. So it is unfair that it should MLE.

If I replace vectors with static arrays, or dynamically allocated arrays, it passes. It is ONLY vectors that fail. Can anyone explain this? Is it a problem with leetcode? Running on my machine, I cannot find a case that causes much more memory usage than with other methods, including the breaking case that gets MLE on leetcode. They all use < 8MB on my machine.

This equivalent code passes:

``````class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int DP[1001][1001];
for (int i = 0; i <= A.size(); ++i) {
for (int j = 0; j <= B.size(); ++j) {
DP[i][j] = 0;
}
}
int ans = 0;
for (int i = A.size()-1; i >= 0; --i) {
for (int j = 0; j < B.size(); ++j) {
if (A[i] == B[j]) {
DP[i][j] = DP[i+1][j+1]+1;
ans = max(ans, DP[i][j]);
}
}
}
return ans;
}
};
``````

UPDATE:

I have done some more testing, and I definitely think something strange is going on with LeetCode. The code below passes. Also, running the MLE test case on my machine using this code (compiled under G++ 6.3.0 in Ubuntu 17.04) only uses around 6616 KB at peak memory usage, while the accepted code uses around 7192 KB, which is more! Both are still very small, however.

I also experimented using the MLE and the accepted code below with the MLE test case from LeetCode, and running the test case 100 times. I was thinking perhaps something odd is going on with the vector destructor in the STL. However, this produced the exactly same peak memory as before.

Thus, I make the tentative claim that this is a bug in LeetCode's system.

``````vector<vector<int>> DP(1001, vector<int>(1001));
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
for (int i = 0; i < A.size()+1; ++i) {
for (int j = 0; j < B.size()+1; ++j) {
DP[i][j] = 0;
}
}
int ans = 0;
for (int i = A.size()-1; i >= 0; --i) {
for (int j = 0; j < B.size(); ++j) {
if (A[i] == B[j]) {
DP[i][j] = DP[i+1][j+1]+1;
ans = max(ans, DP[i][j]);
}
}
}
return ans;
}
};
``````

• Can I ask you a problem about LeetCode judge system? if we want use some C language library functions, do we need to include corresponding head file?
In today contest, I tried to use itoa function(transfer int data type to char*), but got CE(Compile error)。Can you help me?

• @FuZhihong I tried to write this `#include<cstdlib>`, but failed and got CE too.

• @cuiaoxiang It is starting to look like this is a reproducible bug!

• I ran into the same issue during the contest, when I was using a 2D vector<vector<int>> array. Then TLE forced me to switch to using a 1D vector array for the dp.

• We have just finish rejudged all affected submissions. The scoreboard is being updated as well.

• @1337c0d3r Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.