443. String Compression (Medium)

Problem

Given an array of characters chars, compress it in place. For each group of consecutive repeating characters:

If the group length is 1, write just the character.
If the group length is greater than 1, write the character followed by each digit of the count.

Return the new length of the array after compression. The modified chars must hold the result; no extra array allowed.

Examples

['a','a','b','b','c','c','c'] → ['a','2','b','2','c','3'], return 6
['a'] → ['a'], return 1
['a','b','b','b','b','b','b','b','b','b','b','b','b'] → ['a','b','1','2'], return 4

Constraints

$1 \leq n \leq 2000$
chars[i] is a lowercase letter, digit, or space.
Must use $O(1)$ extra space.

LeetCode 443 · Link · Medium

Try it yourself

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Extra buffer

Build the compressed output in a separate list, then copy it back into chars.

def compress(chars: list[str]) -> int:
    result = []                                              # L1: extra buffer
    i = 0
    while i < len(chars):                                   # L2: scan groups
        char = chars[i]
        count = 0
        while i < len(chars) and chars[i] == char:         # L3: count group
            count += 1
            i += 1
        result.append(char)                                 # L4: write char
        if count > 1:                                       # L5: write count digits
            result.extend(list(str(count)))
    for i, c in enumerate(result):                         # L6: copy back
        chars[i] = c
    return len(result)

function compress(chars: string[]): number {
    const result: string[] = [];                             // L1: extra buffer
    let i = 0;
    while (i < chars.length) {                              // L2: scan groups
        const char = chars[i];
        let count = 0;
        while (i < chars.length && chars[i] === char) {    // L3: count group
            count++;
            i++;
        }
        result.push(char);                                   // L4: write char
        if (count > 1)                                      // L5: write count digits
            result.push(...String(count).split(''));
    }
    for (let j = 0; j < result.length; j++)                // L6: copy back
        chars[j] = result[j];
    return result.length;
}

import "strconv"

func compress(chars []byte) int {
    result := []byte{}                                       // L1: extra buffer
    i := 0
    for i < len(chars) {                                    // L2: scan groups
        char := chars[i]
        count := 0
        for i < len(chars) && chars[i] == char {           // L3: count group
            count++
            i++
        }
        result = append(result, char)                       // L4: write char
        if count > 1 {                                      // L5: write count digits
            for _, d := range strconv.Itoa(count) {
                result = append(result, byte(d))
            }
        }
    }
    copy(chars, result)                                     // L6: copy back
    return len(result)
}

final class Solution {
    @discardableResult
    func compress(_ chars: inout [String]) -> Int {
        var result: [String] = []
        var read = 0
        while read < chars.count {
            let character = chars[read]
            var end = read
            while end < chars.count && chars[end] == character { end += 1 }
            result.append(character)
            let count = end - read
            if count > 1 { result.append(contentsOf: String(count).map(String.init)) }
            read = end
        }
        chars = result
        return result.count
    }
}

Where the time goes, line by line

Variables: n = len(chars).

Line	Per-call cost	Times executed	Contribution
L2 outer loop	$O(1)$	$n$ total across all groups	$O(n)$
L3 inner loop	$O(1)$	$n$ total across all groups	$O(n)$
L6 copy back	$O(1)$	up to $n$	$O(n)$

Complexity

Time: $O(n)$ , two passes.
Space: $O(n)$ , the extra buffer.

Approach 2: Two-pointer in-place

Track a write pointer and a read pointer i. After consuming each group, write the character and count digits back at write. Because compressed output is always shorter than or equal to its source group, write never catches up to i and no data is overwritten before it is read.

def compress(chars: list[str]) -> int:
    write = 0                                               # L1: write pointer
    i = 0                                                  # L2: read pointer
    while i < len(chars):                                  # L3: scan groups
        char = chars[i]
        count = 0
        while i < len(chars) and chars[i] == char:        # L4: count group
            count += 1
            i += 1
        chars[write] = char                                # L5: write char
        write += 1
        if count > 1:                                      # L6: write count digits
            for digit in str(count):
                chars[write] = digit
                write += 1
    return write

function compress(chars: string[]): number {
    let write = 0;                                          // L1: write pointer
    let i = 0;                                             // L2: read pointer
    while (i < chars.length) {                            // L3: scan groups
        const char = chars[i];
        let count = 0;
        while (i < chars.length && chars[i] === char) {  // L4: count group
            count++;
            i++;
        }
        chars[write++] = char;                             // L5: write char
        if (count > 1)                                    // L6: write count digits
            for (const digit of String(count))
                chars[write++] = digit;
    }
    return write;
}

import "strconv"

func compress(chars []byte) int {
    write := 0                                             // L1: write pointer
    i := 0                                                // L2: read pointer
    for i < len(chars) {                                 // L3: scan groups
        char := chars[i]
        count := 0
        for i < len(chars) && chars[i] == char {        // L4: count group
            count++
            i++
        }
        chars[write] = char                              // L5: write char
        write++
        if count > 1 {                                  // L6: write count digits
            for _, digit := range strconv.Itoa(count) {
                chars[write] = byte(digit)
                write++
            }
        }
    }
    return write
}

final class Solution {
    @discardableResult
    func compress(_ chars: inout [String]) -> Int {
        let originalCount = chars.count
        var read = 0
        var write = 0
        while read < originalCount {
            let character = chars[read]
            var end = read
            while end < originalCount && chars[end] == character { end += 1 }
            chars[write] = character
            write += 1
            let count = end - read
            if count > 1 {
                for digit in String(count) {
                    chars[write] = String(digit)
                    write += 1
                }
            }
            read = end
        }
        if write < chars.count { chars.removeSubrange(write..<chars.count) }
        return write
    }
}

Why write never overtakes read

A group of $k$ identical characters compresses to $1 + \lfloor\log_{10}k\rfloor + 1$ bytes at most. For any $k \geq 1$ that is always $\leq k$ , so write advances no faster than i finishes each group.

Where the time goes, line by line

Variables: n = len(chars).

Line	Per-call cost	Times executed	Contribution
L1, L2 init	$O(1)$	1	$O(1)$
L3 outer while	$O(1)$	groups visited	$O(n)$
L4 inner while	$O(1)$	$n$ total	$O(n)$
L5, L6 writes	$O(1)$	at most $n$	$O(n)$

Complexity

Time: $O(n)$ , one pass.
Space: $O(1)$ , two scalar pointers.

How to recognize this pattern

The two-word trigger: “in place.” Any problem that says modify the array in place and return a new length is telling you that a scratch buffer is off-limits. That constraint removes the obvious approach (build a result list and copy back) and forces you toward in-place mutation. The question becomes: how do you write output into the same array you are reading from without corrupting unread data?

The answer is almost always a read/write pointer split.

The mental model. Imagine two cursors on a tape. The read cursor (i) moves forward freely, consuming input. The write cursor (write) moves forward only when it has something valid to emit. At any moment, everything to the left of write is already-committed output; everything between write and i is consumed but irrelevant; everything at i and beyond is unread input. The key insight: the write cursor can only reach the read cursor if output is ever longer than input. If you can prove it cannot be, in-place mutation is safe.

For compression, a group of $k$ identical characters always compresses to fewer than $k$ characters (1 char plus at most a few digits). So write is guaranteed to trail i. For remove-duplicates problems, each output element was already read, so write trails by definition. Recognizing this trailing guarantee is what unlocks the pattern.

When to reach for it. Ask yourself three questions:

Is the problem asking you to filter, compress, or transform an array with a fixed output length constraint?
Does the output at any position depend only on already-consumed input, never on future input?
Can you prove the output never grows longer than the input consumed to produce it?

Three yes answers: read/write pointers. One no answer: think harder, or accept O(n) space.

Why not just use extra space? You can, and Approach 1 is correct. But in-place is worth understanding for three reasons. First, it cuts space from O(n) to O(1), which matters at scale (2000 characters is small, but the same logic applies to streaming 10 GB logs). Second, it eliminates a second pass to copy results back. Third, it is the canonical form the interviewer expects when the problem says “O(1) extra space.” Producing Approach 1 under in-place constraints signals you missed the constraint.

The wrong first move. Most people instinctively write Approach 1. There is nothing wrong with recognizing that and then asking: can I make write trail read safely? If yes, collapse the two steps into one pointer pair. If the safety proof fails (output could be longer than input), stick with the buffer.

Problem	Same shape
26. Remove Duplicates from Sorted Array	Write pointer, in-place, return new length
27. Remove Element	Write pointer skips unwanted values
125. Valid Palindrome	Two pointers, one pass over a string

Key takeaways

write always trails i because compressed output fits inside the space the source group occupied.
Multi-digit counts like 12 write as individual characters '1', '2', not as an integer.
Single-character groups write only the character, no count digit.
Edge case: n = 1 always returns 1 with no count written.

Two Pointers, the two index invariant that shrinks or coordinates positions without nested loops.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.