Unexpected Memory Limit Exceeded -- Possible LeetCode bug!


  • 2
    M

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

  • 0
    F

    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?


  • 0
    F

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


  • 2

  • 0
    M

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


  • 0
    P

    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.


  • 0

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


  • 0
    M

    @1337c0d3r Thanks!


Log in to reply
 

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