Author at SyntaxFlow
DSA Interview Guide · C++ · Two Pointers
LeetCode 443, solved three ways — a separate output array, an in-place two-pointer version using to_string, and a fully constant-space version with manual digit extraction — with intuition, C++ code, an animated dry run for each approach, and complexity analysis you can explain out loud.
Compress an array of characters in place: for each maximal run of consecutive identical characters, write the character once, followed by the run's length if it's greater than 1. Return the new length. Only constant extra space is allowed — the result must be written back into the input array itself.
Example: chars = ['a','a','b','b','c','c','c'] → new length 6, array becomes ['a','2','b','2','c','3',...].
To exercise the tricky part of this problem — counts with more than one digit — we'll trace all three approaches on chars = twelve 'a's, one 'b', two 'c's (15 characters total), which compresses to "a12bc2", a new length of 6.
Approach 1 · Brute Force
The most natural first solution ignores the space constraint entirely: scan through chars, identify each run of identical characters, and push the compressed representation — the character, then its count's digits if the run is longer than one — onto a brand-new output container. Once the scan is done, copy that container back over the front of chars.
It's correct and easy to verify, but it directly violates the problem's own requirement, since the separate output array is O(n) extra memory — worth writing down mentally, then immediately talking your way out of.
result array.chars left to right, grouping consecutive identical characters.result; if the group's length is greater than 1, convert the length to a string and push each digit too.result back into the front of chars.result.size().int compress(vector<char>& chars) {
int n = chars.size();
vector<char> result;
int i = 0;
while (i < n) {
char ch = chars[i];
int start = i;
while (i < n && chars[i] == ch) i++;
int count = i - start;
result.push_back(ch);
if (count > 1) {
string cnt = to_string(count);
for (char digit : cnt) result.push_back(digit);
}
}
for (int k = 0; k < (int)result.size(); k++) chars[k] = result[k];
return result.size();
}Approach 2 · Better
There's no real need for a separate array — the compressed output is never longer than the original input, so it can always be written back into chars itself, just behind where the scan currently is. Use a read pointer to find each group and a write pointer to place the compressed characters, and the whole compression happens in one pass with no auxiliary container.
read and write pointers, both starting at 0.read across the whole run of matching characters.chars[write++].to_string and write each digit at chars[write++].read reaches the end; return write.int compress(vector<char>& chars) {
int n = chars.size();
int read = 0, write = 0;
while (read < n) {
char ch = chars[read];
int start = read;
while (read < n && chars[read] == ch) read++;
int count = read - start;
chars[write++] = ch;
if (count > 1) {
string cnt = to_string(count); // small temporary allocation
for (char digit : cnt) chars[write++] = digit;
}
}
return write;
}Approach 3 · Optimal
Even the small string from to_string is unnecessary. A count's digits can be peeled off directly with % 10 and / 10 and written straight into chars — but that naturally produces them in reverse order (least significant digit first). The fix is simple: write them in that reversed order, then reverse just that small segment in place afterward so 12 ends up as '1', '2' instead of '2', '1'.
read and write pointers, both starting at 0, exactly as before.chars[write++].digitStart = write, then repeatedly write '0' + count % 10 and divide count by 10 until it reaches 0.chars[digitStart .. write) in place to fix the digit order.read reaches the end; return write.int compress(vector<char>& chars) {
int n = chars.size();
int read = 0, write = 0;
while (read < n) {
char ch = chars[read];
int start = read;
while (read < n && chars[read] == ch) read++;
int count = read - start;
chars[write++] = ch;
if (count > 1) {
int digitStart = write;
while (count > 0) {
chars[write++] = char('0' + count % 10);
count /= 10;
}
reverse(chars.begin() + digitStart, chars.begin() + write);
}
}
return write;
}to_string first to get a working in-place solution quickly, but proactively flag that it technically allocates memory, and offer the manual digit-extraction version as the fully compliant follow-up.write never passes read.Why can't you use an extra array or string for String Compression?
The problem explicitly requires constant extra space and asks for the result to be written back into the original array, so a separate output buffer — while correct — uses O(n) extra memory and doesn't satisfy the constraint.
Which approach should I lead with in an interview?
Frame the constant-space requirement upfront, write the two-pointer in-place version (with to_string if that's fastest to get working), then offer the manual digit-extraction version as the fully compliant final answer.
How do you handle counts with more than one digit, like 12?
Write the digits least-significant-first using count % 10 and count / 10, then reverse just that written segment in place so the digits appear in the correct order afterward.
Is using std::to_string() considered O(1) extra space?
Only loosely — it allocates a small temporary string on the heap, so while it's asymptotically negligible, it isn't strictly constant extra space, which is why the fully optimal solution avoids it in favor of manual digit extraction.