sankalp_'s blog

Why am I getting Memory Limit exceeded in this solution?
By sankalp_, history, 6 years ago, In English

I was solving a question which uses a trie and I've taken care of the number of nodes and I repeatedly got MLE upon implementing it using 2D arrays and pointers as well.

I've looked at submissions that used a similar logic and they are getting AC.

Any help as to why this is happening is highly appreciated.

Question : 514C

Submission with Pointers : Pointers

Similar submission : Also Pointers

Submission with 2D array : Array

Similar submission : Also Array

Sorry if I missed something obvious. I am legit stuck here and I can't figure out why this is happening. Can anyone please tell why?

[UPD]

The MLE was occurring because string str was being stored in the function stack multiple times and when the level of recursion becomes huge, it resulted in an MLE. Declaring the variable global solved it.

Accepted submissions :

Array

Pointers

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 4   Vote: I like it +7 Vote: I do not like it

UPD: oh, I didn't see your UPD that you already have found your mistake.

You just not oprimize well your solution. There might be something else that can be done better, but I got AC with pointers from your solution
by changing void findString(Node *cur,string str,int idx,bool flag) to

this

Don't forget that local variables in recyrsions stores on stack and exists here until function is over. You have pretty big recursion, that's why it gives MLE.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you very much.

    I will declare variables common to function calls globally from the next time onwards.

    Once again, thank you for your time :)

    → Reply