Mini Parser - Solution & Explanation
Problem Statement
Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.
Each element is either an integer or a list whose elements may also be integers or other lists.
Example 1:
Input: s = "324" Output: 324 Explanation: You should return a NestedInteger object which contains a single integer 324.
Example 2:
Input: s = "[123,[456,[789]]]"
Output: [123,[456,[789]]]
Explanation: Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
i. An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789
Constraints:
1 <= s.length <= 5 * 104sconsists of digits, square brackets"[]", negative sign'-', and commas','.sis the serialization of validNestedInteger.- All the values in the input are in the range
[-106, 106].
Approach Overview
Problem Overview: You receive a string that represents a nested list of integers such as [123,[456,[789]]]. The goal is to deserialize this string into a NestedInteger structure where each element is either a single integer or a list of nested integers.
Approach 1: Stack-Based Parsing (O(n) time, O(n) space)
This approach processes the string character by character while maintaining a stack of partially constructed NestedInteger objects. Whenever you encounter an opening bracket '[', create a new list and push the current object onto the stack. When digits (or a negative sign) appear, parse the full integer value and add it to the current list. On encountering a closing bracket ']', the current nested list is complete, so pop the parent from the stack and attach the finished list to it.
The key insight is that nested lists follow a clear hierarchical structure, which stacks model naturally. Each '[' represents a new context and each ']' ends it. Because each character in the string is processed exactly once, the runtime is O(n), where n is the string length. The stack can grow to the depth of nesting, giving O(n) space in the worst case. This technique heavily relies on string parsing and stack operations similar to problems in string and stack processing.
Approach 2: Recursive Deserialization (O(n) time, O(n) space)
Recursive parsing mirrors the nested structure of the input directly. When the parser sees '[', it recursively constructs a list until the corresponding closing bracket appears. If the current character starts a number, parse the integer and return a single NestedInteger containing that value.
The recursion naturally handles nested lists: each recursive call processes one sublist and returns it to its parent. A shared index pointer moves through the string so every character is parsed once. This results in O(n) time complexity and up to O(n) space due to recursion depth and the constructed data structure.
This solution closely resembles recursive tree or graph parsing patterns. Conceptually, the string is treated like a preorder traversal of a nested structure, making the technique similar to problems solved using depth-first search.
Recommended for interviews: The stack-based parser is typically preferred because it demonstrates explicit control over parsing state and avoids recursion limits. Many interviewers expect this approach for serialization/deserialization problems. Still, explaining the recursive method first can show strong understanding of the nested structure before implementing the iterative stack solution.
Approach 1: Stack-Based Parsing
This approach uses a stack to manage NestedInteger objects as we traverse the string. When encountering '[', a new NestedInteger object is created and pushed onto the stack. When encountering ']', the top object is popped and added to the NestedInteger on the top of the stack (if any). Numbers are parsed and added as individual NestedIntegers.
The solution in C involves writing or assuming existing implementations for NestedInteger operations, then using a stack to process the string character by character.
Complexity
Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(n), for the stack and dynamic NestedInteger objects.
Approach 2: Recursive Deserialization
This approach leverages recursion to simplify handling nested structures. By using a helper function with an index parameter, the parsing function can call itself to deserialize nested lists efficiently.
The C solution for this approach would involve crafting a recursive function that handles the index traversal through the string, invoking itself for nested brackets.
Complexity
Time Complexity: O(n), where n is the length of s, though work specific to C may yield additional nuances for dynamic operations.
Space Complexity: O(n), due to recursion depth and dynamic NestedInteger allocations.
Approach 3: Recursion
We first judge whether the string s is empty or an empty list. If so, simply return an empty NestedInteger. If s is an integer, we simply return a NestedInteger containing this integer. Otherwise, we traverse the string s from left to right. If the current depth is 0 and we encounter a comma or the end of the string s, we take a substring and recursively call the function to parse the substring and add the return value to the list. Otherwise, if the current encounter is a left parenthesis, we increase the depth by 1 and continue to traverse. If we encounter a right parenthesis, we decrease the depth by 1 and continue to traverse.
After the traversal is over, return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Stack
We can use a stack to simulate the recursive process.
We first judge whether the string s is an integer. If so, we simply return a NestedInteger containing this integer. Otherwise, we traverse the string s from left to right. For the character c currently traversed:
- If
cis a negative sign, we set the negative sign totrue; - If
cis a number, we add the number to the current numberx, where the initial value ofxis0; - If
cis a left parenthesis, we push a newNestedIntegeronto the stack; - If
cis a right parenthesis or comma, we judge whether the previous character of the current character is a number. If so, we add the current numberxto the topNestedIntegerof the stack according to the negative sign, and then reset the negative sign tofalseand the current numberxto0. Ifcis a right parenthesis and the size of the current stack is greater than1, we pop the topNestedIntegerof the stack and add it to the topNestedIntegerof the stack.
After the traversal is over, return the top NestedInteger of the stack.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Stack-Based Parsing | Time Complexity: O(n), where n is the length of the string s. |
| Recursive Deserialization | Time Complexity: O(n), where n is the length of s, though work specific to C may yield additional nuances for dynamic operations. |
| Recursion | — |
| Stack | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Parsing | O(n) | O(n) | Best general solution. Explicit control over nested structure and commonly expected in interviews. |
| Recursive Deserialization | O(n) | O(n) | Clean and intuitive when recursion is allowed and nesting depth is manageable. |
Video Solution
Leetcode Question 385 "Mini Parser" in Java • Ghumman Tech • 964 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Mini Parser easy or hard?
How to solve Mini Parser in O(n)?
What is the best approach for Mini Parser?
What data structure is used in Mini Parser?
What is the time complexity of Mini Parser?
Mini Parser Python or Java solution approach
Is Mini Parser asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Mini Parser with our built-in code editor and test cases.
Practice on FleetCode