Time Limit Exceeded


  • 0
    A

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

  • 1
    V

    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) {
        int answer = 0;
        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();
    
    }
    }

Log in to reply
 

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