JAVA O(n) time, O(1) space easy to understand explanation


  • 0
    M

    Just throwing my two cents in incase it can help someone...

    We can complete this question with the help of two pointers,

    read: the next index to read in
    write: the next index to write to

    Write will hold our final answer

    Since chars with no successive duplicates do not need to be followed by "1" we know this method can work without overwriting a new number we have not read yet

    We know that we are going to need a O(n) solution since there is no particular order to the elements, so we will have to read to the end of the array to figure out all counts. We create a for loop to do this

    At each repeat of the for loop the read head is at a new character (new meaning it does not match with the one before it) - this is our invariant. As such we know we have to record it and increment the write and read heads

    chars[write++] = chars[read++];
    

    Now we need to consider if this character has duplicates following it. We simply update a counter (totalDups) as long as this character matches the previous one. We also increment read each time. At the end of the while loop, read would either be at an index outside of the scope of the string or at a character that does not match our dup trail. So on the next tick of the for loop read will be at a "new" character thus maintaining our invariant

    All we have left to do is to write the dup count. If the count is 1, meaning it is a single character with no dups following it, we have noting to write. Otherwise we need to write each digit of the variable totalDups. We can get the digit count by turning it to a String and taking the length

    To get each digit, we can divide by the necessary power of 10 and then mod our number with that same power of 10 in order to repeat and get the next digit. For example:

    Suppose we had a totalDups count of 1234 we want to push "1" then "2" then "3" then "4"
    First we use 1000
    1234 / 1000 = 1 we push that
    1234 % 1000 = 234

    So on the next iteration of our loop, we have 234 / 100 this is 2 so we push that
    2 % 100 = 34

    .. and so on

    class Solution {
        public int compress(char[] chars) {
            int read = 0, write = 0;
            for (; read < chars.length;) {
                // at new char
                chars[write++] = chars[read++];
                // if dup we need a number
                int totalDups = 1;
                while (read < chars.length && chars[read] == chars[read-1]) {totalDups++; read++;}
                // no dups means no numbers needed
                if (totalDups == 1) continue;
                
                int lenNeeded = Integer.toString(totalDups).length();
                for (int select = (int)Math.pow(10, lenNeeded-1); select >= 1; select /= 10) {
                    chars[write++] = Character.forDigit(totalDups/select, 10);
                    totalDups = totalDups % select;
                }
            }
            return write;
        }
    }
    

Log in to reply
 

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