# Time Limit Exceeded

• I am getting Time Limit Exceeded error . Where Am I doing unnecessary work ?Is that in vector Elements' shifts?

``````int evalRPN(vector<string> &tokens) {

int i=0,len=tokens.size();

while(i<len && len>1){

if(tokens[i]=="+"){
int a = stoi(tokens[i-2]);
int b= stoi(tokens[i-1]);
int c = a+b;
tokens[i-2] = to_string(c);

tokens.erase(tokens.begin()+i);
tokens.erase(tokens.begin()+i-1);
i=i-2;
len = len - 2;
continue;
}

if(tokens[i]=="-"){
int a = stoi(tokens[i-2]);
int b= stoi(tokens[i-1]);
int c = a-b;
tokens[i-2] = to_string(c);

tokens.erase(tokens.begin()+i);
tokens.erase(tokens.begin()+i-1);
i=i-2;
len = len - 2;
continue;
}

if(tokens[i]=="*"){
int a = stoi(tokens[i-2]);
int b= stoi(tokens[i-1]);
int c = a*b;
tokens[i-2] = to_string(c);

tokens.erase(tokens.begin()+i);
tokens.erase(tokens.begin()+i-1);
i=i-2;
len = len - 2;
continue;
}

if(tokens[i]=="/"){
int a = stoi(tokens[i-2]);
int b= stoi(tokens[i-1]);
int c = a/b;
tokens[i-2] = to_string(c);

tokens.erase(tokens.begin()+i);
tokens.erase(tokens.begin()+i-1);
i=i-2;
len = len - 2;
continue;
}

i++;

}//while

return stoi(tokens[0]);
}``````

• Erase function of vector may take up to O(n) time complexity in the worst case because vectors use an array as their underlying storage, erasing elements in positions other than the vector end causes the container to relocate all the elements after the segment erased to their new positions.

This is generally an inefficient operation, hence above program in the worst case has O(n^2) time complexity, where as the best possible time complexity for the problem is O(n).

``````class Solution {
public int evalRPN(String[] tokens) {
String operator = "+-*/%";
Stack<Integer> stack =  new Stack<Integer>();
for(String s: tokens) {
if (!operator.contains(s))
stack.push(Integer.valueOf(s));
else {
int index = operator.indexOf(s);
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(stack.pop());
switch (index) {
case 0: stack.push((a + b);break;
case 1: stack.push(b - a);break;
case 2: stack.push(a*b);break;
case 3: stack.push(b / a);break;
case 4: stack.push(a % b);break;
}
}
}
return stack.pop();

}
}``````

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