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

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

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

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
// if dup we need a number
int totalDups = 1;
// 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;
}
}
``````

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