LeetCode 481 - Magical String

This problem defines a special infinite sequence called the magical string. The string contains only the characters '1' and '2', and its defining property is very unusual: If you group consecutive identical digits together and record the length of each group, the resulting…

leetcodemediumtwo-pointersstring

LeetCode Problem 481

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

This problem defines a special infinite sequence called the magical string. The string contains only the characters '1' and '2', and its defining property is very unusual:

If you group consecutive identical digits together and record the length of each group, the resulting sequence of lengths recreates the original string itself.

For example, the beginning of the magical string is:

1221121221221121122...

If we split it into groups of consecutive equal digits:

1 | 22 | 11 | 2 | 1 | 22 | 1 | 22 | ...

The lengths of these groups are:

1 2 2 1 1 2 1 2 ...

That sequence is exactly the same as the magical string.

The input is an integer n, and we must determine how many '1' characters appear in the first n elements of the magical string.

The constraints are:

1 <= n <= 10^5

This tells us several important things:

  • The solution must be efficient enough to handle up to one hundred thousand characters.
  • Generating the sequence incrementally is feasible.
  • Expensive recomputation or repeated string rebuilding should be avoided.

There are also several edge cases that matter:

  • n = 1, where the answer is immediately 1.
  • Very small values like n = 2 or n = 3, where initialization mistakes are common.
  • Cases where generation slightly exceeds n, because the sequence is produced in groups rather than one character at a time.
  • Counting only the first n characters, even if more characters are generated internally.

Approaches

Brute Force Approach

A naive solution would attempt to repeatedly rebuild the magical string by scanning the entire sequence every time we append new characters.

The idea would be:

  1. Start with the initial magical string prefix.
  2. Repeatedly group consecutive characters.
  3. Compute group lengths.
  4. Verify or regenerate the sequence from those lengths.
  5. Continue until the string reaches length n.

This approach works conceptually because it directly follows the definition of the magical string. However, it is highly inefficient because grouping and rescanning the sequence repeatedly introduces unnecessary repeated work.

If we rebuild or scan the sequence many times, the total complexity can become quadratic.

With n = 10^5, an O(n^2) approach is too slow.

Optimal Approach

The key observation is that the magical string describes its own run lengths.

This means we can generate the sequence incrementally while simultaneously reading instructions from the sequence itself.

We maintain:

  • A pointer that reads the next group size.
  • A current digit to append, alternating between 1 and 2.
  • A dynamically growing array representing the magical string.

For example:

Initial sequence: 1 2 2

The next unread value is 2, meaning:

append two copies of the opposite digit

Since the last digit is 2, we append:

1 1

Now the sequence becomes:

1 2 2 1 1

The process continues until we generate at least n elements.

This works efficiently because every character is generated exactly once.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeated rescanning and regrouping
Optimal O(n) O(n) Generates each character exactly once

Algorithm Walkthrough

  1. Handle the smallest edge case immediately.

If n <= 3, we already know the magical string starts as:

122

The counts of '1' are easy to determine directly. 2. Initialize the magical string.

We begin with:

magical = [1, 2, 2]

This is the known starting prefix of the sequence. 3. Maintain a pointer for reading group sizes.

We use an index called head.

This pointer tells us how many copies of the next digit to append.

Initially:

head = 2

because the first unread run length is the third element. 4. Track the next digit to append.

We alternate between 1 and 2.

Since the current sequence ends with 2, the next appended digit will be 1. 5. Generate the sequence incrementally.

While the sequence length is less than n:

  • Read the count from magical[head]
  • Append the current digit that many times
  • Count appended 1s if they fall within the first n positions
  • Flip the digit between 1 and 2
  • Advance head
  1. Stop once enough elements are generated.

Since we only care about the first n elements, generation stops as soon as the sequence reaches length n.

Why it works

The algorithm works because the magical string is self descriptive. Each value in the sequence specifies the size of the next group. By reading run lengths from the already generated portion while appending alternating digits, we exactly reproduce the magical string definition.

The invariant is:

Every generated prefix satisfies the magical string property.

Because each step extends the sequence using the next valid run length, correctness is preserved throughout the construction.

Python Solution

class Solution:
    def magicalString(self, n: int) -> int:
        if n <= 3:
            return 1

        magical = [1, 2, 2]

        head = 2
        next_num = 1

        ones_count = 1

        while len(magical) < n:
            repeat = magical[head]

            for _ in range(repeat):
                magical.append(next_num)

                if next_num == 1 and len(magical) <= n:
                    ones_count += 1

            next_num = 2 if next_num == 1 else 1
            head += 1

        return ones_count

The implementation starts with the known prefix [1, 2, 2], which already satisfies the magical string property.

The variable head acts as the reader pointer. Instead of recomputing group sizes, we directly use values already present in the sequence.

The variable next_num tracks which digit should be appended next. Since groups alternate between 1 and 2, we simply toggle the value after each group.

Whenever a 1 is appended within the first n positions, we increment ones_count.

The loop stops once the sequence contains at least n elements.

Go Solution

func magicalString(n int) int {
    if n <= 3 {
        return 1
    }

    magical := []int{1, 2, 2}

    head := 2
    nextNum := 1

    onesCount := 1

    for len(magical) < n {
        repeat := magical[head]

        for i := 0; i < repeat; i++ {
            magical = append(magical, nextNum)

            if nextNum == 1 && len(magical) <= n {
                onesCount++
            }
        }

        if nextNum == 1 {
            nextNum = 2
        } else {
            nextNum = 1
        }

        head++
    }

    return onesCount
}

The Go implementation follows the same logic as the Python solution.

Slices are used instead of Python lists, and append dynamically grows the sequence. Integer overflow is not a concern because the constraint is only 10^5.

Unlike Python, Go does not have a built in ternary operator, so digit toggling uses a standard if statement.

Worked Examples

Example 1

Input:

n = 6

Initial state:

Variable Value
magical [1, 2, 2]
head 2
next_num 1
ones_count 1

Step by step generation:

Step repeat Appended magical ones_count
Initial - - [1,2,2] 1
1 2 1,1 [1,2,2,1,1] 3
2 1 2 [1,2,2,1,1,2] 3

Now length is 6, so we stop.

Result:

3

Example 2

Input:

n = 1

Since n <= 3, we immediately return:

1

The first character of the magical string is:

1

which contains exactly one '1'.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is generated exactly once
Space O(n) The generated magical string is stored

The algorithm is linear because every appended digit is processed only once. The head pointer advances steadily through the sequence without revisiting earlier elements repeatedly.

The space complexity is also linear because we explicitly store the generated sequence up to size n.

Test Cases

solution = Solution()

assert solution.magicalString(1) == 1  # smallest input
assert solution.magicalString(2) == 1  # prefix "12"
assert solution.magicalString(3) == 1  # prefix "122"
assert solution.magicalString(4) == 2  # prefix "1221"
assert solution.magicalString(5) == 3  # prefix "12211"
assert solution.magicalString(6) == 3  # provided example
assert solution.magicalString(7) == 4  # prefix "1221121"
assert solution.magicalString(10) == 5  # larger prefix validation
assert solution.magicalString(20) == 10  # medium sized case
assert solution.magicalString(1000) > 0  # stress test
assert solution.magicalString(100000) > 0  # maximum constraint

Test Summary

Test Why
n = 1 Smallest valid input
n = 2 Small prefix handling
n = 3 Initialization boundary
n = 4 First generated extension
n = 5 Multiple appended ones
n = 6 Provided example
n = 7 Alternating group validation
n = 10 Longer sequence correctness
n = 20 Medium sized verification
n = 1000 Performance sanity check
n = 100000 Maximum constraint stress test

Edge Cases

One important edge case is n <= 3. The magical string starts as "122", and many implementations incorrectly attempt to generate additional values even for these tiny inputs. This can lead to off by one errors or incorrect counts. The implementation handles this immediately with a direct return of 1.

Another subtle case occurs when generation exceeds n. Since digits are appended in groups of size one or two, the algorithm may append slightly beyond the required prefix length. If counting is done carelessly, extra '1' values beyond position n could be included. The implementation avoids this by checking:

len(magical) <= n

before incrementing the count.

A third important edge case involves alternating digits correctly. Because the magical string is generated from its own run lengths, forgetting to alternate between 1 and 2 after each group breaks the entire construction. The implementation explicitly flips the value after processing every group, ensuring the generated sequence maintains the magical property.