Magical String - Solution & Explanation
Problem Statement
A magical string s consists of only '1' and '2' and obeys the following rules:
- The string s is magical because concatenating the number of contiguous occurrences of characters
'1'and'2'generates the stringsitself.
The first few elements of s is s = "1221121221221121122……". If we group the consecutive 1's and 2's in s, it will be "1 22 11 2 1 22 1 22 11 2 11 22 ......" and the occurrences of 1's or 2's in each group are "1 2 2 1 1 2 1 2 2 1 2 2 ......". You can see that the occurrence sequence is s itself.
Given an integer n, return the number of 1's in the first n number in the magical string s.
Example 1:
Input: n = 6 Output: 3 Explanation: The first 6 elements of magical string s is "122112" and it contains three 1's, so return 3.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 105
Approach Overview
Problem Overview: The magical string is a sequence consisting only of 1 and 2 where the counts of consecutive groups form the same sequence itself. Starting from "122", each value in the sequence tells how many times the next number should appear. Given n, you need to generate the first n characters of this sequence and return the number of 1s.
Approach 1: Explicit Count Method for Small n (Time: O(n), Space: O(n))
This approach directly builds the magical string using an expandable list. Start with the base sequence [1,2,2]. Maintain a pointer that reads how many times the next value should appear and append that many 1s or 2s to the sequence. After each append operation, flip the next value between 1 and 2. Continue until the sequence length reaches n. Finally, iterate through the first n elements and count the number of 1s. This method is straightforward and easy to reason about, making it useful when implementing quickly during practice. It primarily relies on sequential array expansion and simple iteration over the string-like sequence.
Approach 2: Two-Pointer Simulation Approach (Time: O(n), Space: O(n))
The optimal solution simulates the construction of the magical string using two pointers. One pointer (read) tracks the position that tells how many characters to generate next, while another pointer effectively extends the sequence. Start with [1,2,2] and maintain a variable for the next number to append. For each step, read the count at the read pointer and append that many occurrences of the next number. After generating the values, toggle between 1 and 2 and advance the pointer. While appending, keep a running count of 1s to avoid an extra pass. The algorithm behaves similarly to a classic two pointers simulation where one pointer drives generation and the other grows the sequence.
This technique works because the magical string is self-referential: the sequence itself dictates the lengths of its groups. Instead of recomputing group sizes, you reuse previously generated values through pointer traversal. Each element is processed once, giving linear time complexity. The approach is efficient and predictable since every append operation is directly determined by an earlier value.
Recommended for interviews: The two-pointer simulation approach. It demonstrates that you recognize the self-referential pattern and can model it with controlled sequence generation. Interviewers usually expect the O(n) simulation rather than repeatedly recomputing counts. Implementing the simple explicit construction first shows understanding, while the two-pointer version shows stronger algorithmic control.
Approach 1: Two-Pointer Simulation Approach
The goal is to generate the magical string up to at least the nth element and count the number of '1's within that range. This approach uses a two-pointer technique to simulate the generation of the magical string using two lists simultaneously. One of the lists keeps track of how many times '1' or '2' should be appended, while the other keeps track of the actual magical string. We iterate through this structure simulating the given formation rules until we have enough elements.
This Python code creates the magical string starting with '122'. The function then uses a variable i to iterate over the string, using each character to determine how many of the opposite character should be added next (matching the sequence rules). The list s is gradually extended until it contains at least n elements. Finally, the number of '1's in the first n characters of s is returned.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Explicit Count Method for Small n
This approach is more suited for smaller values of n due to its direct and straightforward nature. It explicitly constructs the magical string up to the required n elements and counts 1s until that point, optimizing not towards large n but ensuring correctness by directly simulating each step with loop control. This approach starts with the initial series and grows using the two-pointer write technique, appending directly to the result string, and counting in place.
This is implemented in Python by initializing the sequence and dynamically extends it. It maintains a position idx to know how many to append and what to append 1 or 2, which number should be following the rule 1 -> 2 and vice versa. It then counts the number of '1's within the first n elements.
Code
Python
C++
Java
JavaScript
Complexity
Time Complexity: O(nĀ²) in small n context, since each append can cause a full list extension
Space Complexity: O(n)
Approach 3: Simulate the Construction Process
According to the problem, we know that each group of numbers in the string s can be obtained from the digits of the string s itself.
The first two groups of numbers in string s are 1 and 22, which are obtained from the first and second digits of string s, respectively. Moreover, the first group of numbers contains only 1, the second group contains only 2, the third group contains only 1, and so on.
Since the first two groups of numbers are known, we initialize string s as 122, and then start constructing from the third group. The third group of numbers is obtained from the third digit of string s (index i=2), so at this point, we point the pointer i to the third digit 2 of string s.
1 2 2
^
i
The digit pointed by pointer i is 2, indicating that the third group of numbers will appear twice. Since the previous group of numbers is 2, and the numbers alternate between groups, the third group of numbers is two 1s, i.e., 11. After construction, the pointer i moves to the next position, pointing to the fourth digit 1 of string s.
1 2 2 1 1
^
i
At this point, the digit pointed by pointer i is 1, indicating that the fourth group of numbers will appear once. Since the previous group of numbers is 1, and the numbers alternate between groups, the fourth group of numbers is one 2, i.e., 2. After construction, the pointer i moves to the next position, pointing to the fifth digit 1 of string s.
1 2 2 1 1 2
^
i
Following this rule, we simulate the construction process sequentially until the length of string s is greater than or equal to n.
The time complexity is O(n), and the space complexity is O(n).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Simulation Approach | Time Complexity: O(n) |
| Explicit Count Method for Small n | Time Complexity: O(nĀ²) in small n context, since each append can cause a full list extension |
| Simulate the Construction Process | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Explicit Count Method for Small n | O(n) | O(n) | When implementing a simple simulation or when n is small and readability is preferred |
| Two-Pointer Simulation Approach | O(n) | O(n) | General case and interview settings where efficient sequential generation is expected |
Video Solution
481. Magical String Leetcode ā¢ Code Crusaders ā¢ 2,518 views views
Watch 8 more video solutions āFrequently Asked Questions
Is Magical String easy or hard?
Magical String Python/Java solution
How to solve Magical String in O(n)?
What is the best approach for Magical String?
Is Magical String asked at Google/Amazon/Meta?
What data structure is used in Magical String?
What is the time complexity of Magical String?
Ready to solve this problem?
Practice Magical String with our built-in code editor and test cases.
Practice on FleetCode