The problem asks us to compress a list of characters in-place and return the new length. Since we need to modify the array while reading it, a Two Pointer approach is perfect. One pointer (read_index) reads through the original characters to find groups, and another pointer (write_index) keeps track of where we are writing the compressed result.

Approach

  1. Initialize two pointers:
    • read_index: used to iterate through the array and counting consecutive characters.
    • write_index: used to overwrite chars with our compressed results.
  2. Iterate through the array while read_index < len(chars).
  3. Inside the loop, we identify the current character (ch) and count its consecutive occurrences using an inner while loop.
  4. Once we have the count:
    • We write the character ch to the write_index position.
    • If the count is greater than 1, we convert the count to a string and write each digit to the chars array, incrementing write_index as we go.
  5. Finally, we return write_index, which represents the new length of the compressed array.

Example Trace: Chars = ["a", "a", "B", "B", "C"]

  1. Start Pointers read_index (R) and write_index (W) start at the beginning.
["a", "a", "b", "b", "c"]
  ^    ^
  W    R
  1. Process Group a. We find two as. We write a and 2.
["a", "2", "b", "b", "c"]
            ^    ^
            W    R
  1. Process Group b We find two bs. We write b and 2.
["a", "2", "b", "2", "c"]
                      ^    ^
                      W    R
  1. Process Group c We find one c. We write c. (no number needed)
["a", "2", "b", "2", "c"]
                           ^ (Done)
                           W

Code

def compress(self, chars: List[str]) -> int:
    if not chars:
        return 0
    write_index = 0
    read_index = 0
    N = len(chars)

    while read_index < N:
        current_char = chars[read_index]
        count = 0

        while read_index < N and chars[read_index] == current_char:
            count += 1
            read_index += 1

        chars[write_index] = current_char
        write_index += 1

        if count > 1:
            for digit in str(count):
                chars[write_index] = digit
                write_index += 1
    return write_index

Complexity

  • Time complexity: $O(N)$
    We iterate through the chars array exactly once.

  • Space complexity: $O(1)$
    We perform the compression in-place.