Easy to understand O(n) C# solution (99.5%)


  • 0
    B
    /*
    Here is a better representation of the problem:
    
    Imagine the problem as stairs with each step numRows wide and long, and then diagonal lines are drawn in the number of numRows.
    P A Y
        P
        A L I
            S
            H I R
                I
                N G
    PAHN 0 4 8 12 <- First line
    APLSIIG 1 3 5 7 9 11 <- Second line
    YIR 2 6 10 <- Third line
    
    numRows = 4
    P A Y P
          A
          L
          I S H I
                R
                I
                N G
    PIN 0 6 12
    ALSIG 1 5 7 11 13
    YAHR 2 4 8 10
    PI 3 9
    
    numRows = 5
    P A Y P A
            L
            I
            S
            H I R I N
                    G
    numRows = 10
    P A Y P A L I S H I
                      N
                      G
    
    */
    public string Convert(string s, int numRows) {
            if(numRows == 1 || s.Length <= numRows) return s;
            int x = 0; // not necesary if string builder is used. x is just used to populate the char array
            int st = 0;
            int diff = 0;
            char[] res = new char[s.Length];
            bool alt;
            for(int i = numRows * 2 - 2, j = st; i >= 0; i-=2, diff += 2) { // for loop traverses every level, # of levels = numRows
                j = st;
                alt = false;
                while(j < s.Length) { // the while loop doesn't traverse the whole array, just the elements at the current level
                    res[x] = s[j];
                    x++;
                    if(i == 0) {
                        j +=  diff;
                    }
                    else if(diff == 0) {
                        j += i;
                    }
                    else {
                        j += alt ? diff : i;
                        alt = !alt;
                    }
                }
                st += 1;
            }
            return new string(res);
        }
    

Log in to reply
 

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