Can we do it, following the approach of solving the N-Queens problem?


  • 0
    I

    Below is my solution, that follows the recursive N-queens approach, i.e.

    First, we assign 1 to first node, then go to second node, if its larger, we assign 2 and so on, but if at some point, we can't allocate any number of candies to a child, then we return to the previous child and increase its candy count and then, move forward again.

    But the solution is giving "Memory Limit Exceeded", probably due to number of recursive calls included.

    int flag=0,temp;
    int candy(vector<int> &ratings){
        int l = ratings.size();
        place(ratings,0,-1,0);
        
        return temp;
    }
    
    void place(vector<int> ratings, int x, int prev, int ans){
        
    if(x==ratings.size()){
        flag=1;
        temp = ans;
        return;
    }
    int i=0;
    while(1){
        i++;
        if(x==0){
            place(ratings,x+1,i,ans+i);
            if(flag==1)
                break;
            else{
                continue;
            }
        }
        else{
            if(ratings[x] < ratings[x-1]){
                if(i < prev){
                    place(ratings,x+1,i,ans+i);
                    if(flag==1)
                        break;
                    else{
                        continue;
                    }
                }
                else{
                    return;
                }
            }
            else if(ratings[x]==ratings[x-1]){
                if(i==prev){
                    place(ratings,x+1,i,ans+i);
                    if(flag==1)
                        break;
                    else{
                        // i++;
                        continue;
                    }
                }
                else{
                    if(i < prev){
                        // i++;
                        continue;
                    }
                    else{
                        return;
                    }
                }
            }
            else if(ratings[x] > ratings[x-1]){
                if(i > prev){
                    place(ratings,x+1,i,ans+i);
                    if(flag==1)
                        break;
                    else{
                        continue;
                    }
                }
                else{
                    // i++;
                    continue;
                }
            }
        }
    }
    }

  • 1
    S

    It is not a good solution, time complexity would be large. The reason why you get MLE, I think it is becaseu the stack overflow, or I think it would be TLE.

    You can see other question post in Candy category to find out a better solution.


  • 0
    I

    Thanks for the quick reply.
    Yes, I saw the other solution and have understood that.
    But, though this algo gives tle/mle , I just want to confirm that this algorithm will correct answer, right?


  • 0
    W

    What's the meaning of MLE and TLE?


  • 0
    S

    MLE = memory limit exceed, TLE = time limit exceed.


Log in to reply
 

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