C++ solution memory limit exceed, help needed


  • 0
    O

    I tested in both windows and mac it uses quite limited memory. My other slower solution which uses more memory passed however this one gives me memory limit exceed at test case where there are a large number of duplicate 1s. My solution shouldn't have problem at that particular case since I removed all consecutive duplicates. And If I ran the test by itself, it passed with correct answer. I suspect it triggered something earlier in the submission test run and cased MLE. Can someone have a look at it and spot the issue?

    void lengthOfLIS2(vector<int>& nums, const int pos, vector<list<int>> & L) {
        int N = (int)nums.size();
        int cur = nums[pos];
        if (pos == N - 1)
        {
            L[pos] = list<int>(1, cur);
        }
        else
        {
            
            list<int> maxList;
            for (int i = pos + 1; i < N; i++)
            {
                const list<int> & prevL = L[i];
                int j = 0;
                for (auto it = prevL.begin(); it != prevL.end();++it)
                {
                    szt potentialLen = 1 + prevL.size() - j;
                    if (potentialLen < maxList.size()) break;
                    if (*it > cur)
                    {
                        list<int> list(it, prevL.end());
                        list.push_front(cur);
                        if (list.size() > maxList.size())
                        {
                            maxList = std::move(list);
                        }
                    }
                    j++;
                }
            }
            if(maxList.size() == 0)
            { 
                L[pos] = list<int>(1, cur);
            }
            else L[pos] = maxList;
        }
    
        if (pos != 0)
        {
            lengthOfLIS2(nums, pos - 1, L);
        }
    }
    
    int lengthOfLIS(vector<int>& nums) {
        int result = 0;
    
        if (nums.size() > 0)
        {
            // remove consecutive duplicates
            auto it = nums.begin();
            std::advance(it, 1);
            for (; it != nums.end();)
            {
                int cur = *it;
                std::advance(it, -1);
                int prev = *it;
                std::advance(it, 1);
                if (cur == prev)
                {
                    it = nums.erase(it);
                }
                else
                {
                    ++it;
                }
            }
    
            vector<list<int>> newL(nums.size(), list< int > ());
            lengthOfLIS2(nums, (int)nums.size() - 1, newL);
            for (auto l : newL)
            {
                result = std::max(result,(int) l.size());
            }
         }
    
        return result;
    }

Log in to reply
 

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