Clear solution; Seems to be O(M * N) but exceeds Time limit


  • -1
    N

    I believe my solution to be O(M * N) because it only passes through the string the number of rows there are:

    public String convert(String s, int numRows) {
            
            String answer = "";
            
            int universal = (numRows-1)*2;
            int stepSize = universal;
            int altStepSize = universal;
            for (int i = 0; i < numRows; i++) {
                if (i == 0 || i == numRows-1) {
                    stepSize = universal;
                    altStepSize = universal;
                } else {
                    stepSize -= 2;
                    altStepSize = universal - stepSize;
                }
                
                int counter = 0;
                for (int j = i; j < s.length();) {
                    
                    answer += s.charAt(j);
                    
                    if ((counter % 2) == 0) j += stepSize;
                    else j += altStepSize;
                    
                    counter++;
                }
                
                
            }
            
            return answer;
        }
    

  • 0

    I suggest to not ignore which test case you fail.

    Also, what do you mean with "M" and "N"?


  • 0
    N

    M = number of rows
    N = length of string

    it fails on the A, 1 test case saying that the time limit is exceeded


  • 0

    @nicolasflores said in Clear solution; Seems to be O(M * N) but exceeds Time limit:

    it fails on the A, 1 test case saying that the time limit is exceeded

    And you didn't bother looking into how you could possibly exceed the time limit on such a tiny case?

    It most likely means you have some bug getting you into an infinite loop. Which you'd then better fix, instead of throwing your hands in the air and being like "time limit exceeded, oh well, that's life".

    M = number of rows
    N = length of string

    Then it's not O(MN), because you're building the answer solely by adding single characters which overall takes Θ(N2) time.

    The extra name "M" is btw unnecessary and confusing, since we already have "numRows" defined.


Log in to reply
 

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