Mini Parser solution and explanation
6 more videos on this problem
Leetcode Question 385 "Mini Parser" in JavaGhumman Tech · 12:04 · 964 views
【每日一题】385. Mini Parser, 08/13/2019Huifeng Guan · 59:36 · 787 views
385. Mini ParserMuerde un zombie · 11:35 · 563 views
Mini Parser (Medium), Leetcode, C++H William Polenz · 1:55:40 · 350 views
LeetCode 385: Mini ParserAlitaCode · 33:22 · 156 views
No Sound Leetcode 385: Mini ParserExtremeProgrammer · 2:35 · 142 views
385. Mini Parser | Leetcode Unlocked - PythonLeetcode Unlocked · 4:15 · 37 views
The problem
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.
class Solution:
def deserialize(self, s: str) -> NestedInteger:
stack = []
num, negative = 0, False
current = NestedInteger()
for i, char in enumerate(s):
if char.isdigit():
num = num * 10 + int(char)
elif char == '-':
negative = True
elif char == '[':
stack.append(current)
current = NestedInteger()
elif char == ']' or char == ',':
if i > 0 and s[i-1].isdigit():
if negative:
num = -num
current.add(NestedInteger(num))
if char == ']' and stack:
ni = current
current = stack.pop()
current.add(ni)
num, negative = 0, False
return currentimport java.util.*;
// Assume the NestedInteger class is defined.
public class Solution {
public NestedInteger deserialize(String s) {
Stack<NestedInteger> stack = new Stack<>();
NestedInteger current = new NestedInteger();
int number = 0;
boolean negative = false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '-') {
negative = true;
} else if (c == '[') {
stack.push(current);
current = new NestedInteger();
} else if (c == ']' || c == ',') {
if (Character.isDigit(s.charAt(i-1))) {
if (negative) number = -number;
current.add(new NestedInteger(number));
}
if (c == ']' && !stack.isEmpty()) {
NestedInteger ni = current;
current = stack.pop();
current.add(ni);
}
number = 0;
negative = false;
}
}
return current;
}
}#include <iostream>
#include <stack>
#include <string>
using namespace std;
// Assume NestedInteger class is defined here with necessary methods.
NestedInteger deserialize(string s) {
stack<NestedInteger> st;
int number = 0;
bool negative = false;
NestedInteger current;
for (size_t i = 0; i < s.size(); ++i) {
if (isdigit(s[i])) {
number = number * 10 + (s[i] - '0');
} else if (s[i] == '-') {
negative = true;
} else if (s[i] == '[') {
st.push(current);
current = NestedInteger();
} else if (s[i] == ']' || s[i] == ',') {
if (isdigit(s[i-1])) {
if (negative) number = -number;
current.add(NestedInteger(number));
number = 0;
negative = false;
}
if (s[i] == ']' && !st.empty()) {
NestedInteger ni = current;
current = st.top();
st.pop();
current.add(ni);
}
}
}
return current;
}// Assume NestedInteger is a constructor with necessary methods implemented.
function deserialize(s) {
let stack = [];
let num = 0;
let negative = false;
let current = new NestedInteger();
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (!isNaN(char)) {
num = num * 10 + parseInt(char);
} else if (char === '-') {
negative = true;
} else if (char === '[') {
stack.push(current);
current = new NestedInteger();
} else if (char === ']' || char === ',') {
if (!isNaN(s[i - 1])) {
if (negative) num = -num;
current.add(new NestedInteger(num));
}
if (char === ']' && stack.length > 0) {
const ni = current;
current = stack.pop();
current.add(ni);
}
num = 0;
negative = false;
}
}
return current;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// Assume NestedInteger and necessary functions such as NestedIntegerInit,
// NestedIntegerAdd, etc., are defined appropriately.
NestedInteger* deserialize(char* s) {
// Implementation here
return NULL; // Placeholder
}using System;
using System.Collections.Generic;
// Assume the NestedInteger class interface is available.
public class Solution {
public NestedInteger Deserialize(string s) {
var stack = new Stack<NestedInteger>();
NestedInteger current = new NestedInteger();
int number = 0;
bool negative = false;
for (int i = 0; i < s.Length; i++) {
char c = s[i];
if (char.IsDigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '-') {
negative = true;
} else if (c == '[') {
stack.Push(current);
current = new NestedInteger();
} else if (c == ']' || c == ',') {
if (char.IsDigit(s[i - 1])) {
if (negative) number = -number;
current.Add(new NestedInteger(number));
}
if (c == ']' && stack.Count > 0) {
NestedInteger ni = current;
current = stack.Pop();
current.Add(ni);
}
number = 0;
negative = false;
}
}
return current;
}
}This Python solution uses a similar stack approach. We iterate through the characters and build numbers. If a closing bracket is found, the last NestedInteger object is removed from the stack and integrated into the new stack top.
Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(n).
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.
class Solution:
def deserialize(self, s: str) -> NestedInteger:
def parse(index):
ni = NestedInteger()
num = 0
negative = False
while index < len(s):
char = s[index]
index += 1
if char.isdigit():
num = num * 10 + int(char)
elif char == '-':
negative = True
elif char == '[':
parsed, index = parse(index)
ni.add(parsed)
elif char == ']' or char == ',':
if s[index - 1].isdigit():
if negative: num = -num
ni.add(NestedInteger(num))
if char == ']':
return ni, index
num = 0
negative = False
return ni, index
parsed, _ = parse(0)
return parsedimport java.util.*;
// NestedInteger assumed defined.
public class Solution {
private int index = 0;
private NestedInteger parse(String s) {
NestedInteger result = new NestedInteger();
int number = 0;
boolean negative = false;
while (index < s.length()) {
char c = s.charAt(index++);
if (Character.isDigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '-') {
negative = true;
} else if (c == '[') {
result.add(parse(s));
} else if (c == ']' || c == ',') {
if (Character.isDigit(s.charAt(index - 1))) {
if (negative) number = -number;
result.add(new NestedInteger(number));
}
if (c == ']') return result;
number = 0;
negative = false;
}
}
return result;
}
public NestedInteger deserialize(String s) {
return parse(s);
}
}#include <iostream>
// Assume NestedInteger is implemented with required methods.
NestedInteger parse(const std::string &s, size_t &index) {
NestedInteger result;
int number = 0;
bool negative = false;
while (index < s.size()) {
char c = s[index++];
if (isdigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '-') {
negative = true;
} else if (c == '[') {
NestedInteger list = parse(s, index);
result.add(list);
} else if (c == ']' || c == ',') {
if (index > 0 && isdigit(s[index - 1])) {
if (negative) number = -number;
result.add(NestedInteger(number));
}
if (c == ']') return result;
number = 0;
negative = false;
}
}
return result;
}
NestedInteger deserialize(const std::string &s) {
size_t index = 0;
return parse(s, index);
}function deserialize(s) {
let index = 0;
function parse() {
const ni = new NestedInteger();
let num = 0;
let negative = false;
while (index < s.length) {
const char = s[index++];
if (!isNaN(char)) {
num = num * 10 + parseInt(char);
} else if (char === '-') {
negative = true;
} else if (char === '[') {
ni.add(parse());
} else if (char === ']' || char === ',') {
if (!isNaN(s[index - 1])) {
if (negative) num = -num;
ni.add(new NestedInteger(num));
}
if (char === ']') return ni;
num = 0;
negative = false;
}
}
return ni;
}
return parse();
}#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
// Assume NestedInteger and necessary functions are defined appropriately.
NestedInteger* deserialize(const char* s) {
// Recursive implementation placeholder for C.
return NULL;
}using System;
// Assume NestedInteger class is defined.
public class Solution {
private int index = 0;
private NestedInteger Parse(string s) {
var ni = new NestedInteger();
int number = 0;
bool negative = false;
while (index < s.Length) {
char c = s[index++];
if (char.IsDigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '-') {
negative = true;
} else if (c == '[') {
ni.Add(Parse(s));
} else if (c == ']' || c == ',') {
if (char.IsDigit(s[index - 1])) {
if (negative) number = -number;
ni.Add(new NestedInteger(number));
}
if (c == ']') return ni;
number = 0;
negative = false;
}
}
return ni;
}
public NestedInteger Deserialize(string s) {
index = 0;
return Parse(s);
}
}This Python function makes use of a nested function 'parse' which takes an index and recursively handles nested structures. It handles digit parsing, negative signs, and nested list integration.
Time Complexity: O(n).
Space Complexity: O(n) due to recursion depth.
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.
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* If value is provided, then it holds a single integer
* Otherwise it holds an empty nested list
* constructor(value?: number) {
* ...
* };
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* isInteger(): boolean {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* getInteger(): number | null {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* setInteger(value: number) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* add(elem: NestedInteger) {
* ...
* };
*
* Return the nested list that this NestedInteger holds,
* or an empty list if this NestedInteger holds a single integer
* getList(): NestedInteger[] {
* ...
* };
* };
*/
function deserialize(s: string): NestedInteger {
if (s === '' || s === '[]') {
return new NestedInteger();
}
if (s[0] !== '[') {
return new NestedInteger(+s);
}
const ans: NestedInteger = new NestedInteger();
let depth = 0;
for (let i = 1, j = 1; i < s.length; ++i) {
if (depth === 0 && (s[i] === ',' || i === s.length - 1)) {
ans.add(deserialize(s.slice(j, i)));
j = i + 1;
} else if (s[i] === '[') {
++depth;
} else if (s[i] === ']') {
--depth;
}
}
return ans;
}/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (n NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (n NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (n *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (n NestedInteger) GetList() []*NestedInteger {}
*/
func deserialize(s string) *NestedInteger {
ans := &NestedInteger{}
if s == "" || s == "[]" {
return ans
}
if s[0] != '[' {
v, _ := strconv.Atoi(s)
ans.SetInteger(v)
return ans
}
depth := 0
for i, j := 1, 1; i < len(s); i++ {
if depth == 0 && (s[i] == ',' || i == len(s)-1) {
(*ans).Add(*deserialize(s[j:i]))
j = i + 1
} else if s[i] == '[' {
depth++
} else if s[i] == ']' {
depth--
}
}
return ans
}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.
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* If value is provided, then it holds a single integer
* Otherwise it holds an empty nested list
* constructor(value?: number) {
* ...
* };
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* isInteger(): boolean {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* getInteger(): number | null {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* setInteger(value: number) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* add(elem: NestedInteger) {
* ...
* };
*
* Return the nested list that this NestedInteger holds,
* or an empty list if this NestedInteger holds a single integer
* getList(): NestedInteger[] {
* ...
* };
* };
*/
function deserialize(s: string): NestedInteger {
if (s[0] !== '[') {
return new NestedInteger(+s);
}
const stk: NestedInteger[] = [];
let x = 0;
let neg = false;
for (let i = 0; i < s.length; ++i) {
if (s[i] === '-') {
neg = true;
} else if (s[i] === '[') {
stk.push(new NestedInteger());
} else if (s[i] >= '0' && s[i] <= '9') {
x = x * 10 + s[i].charCodeAt(0) - '0'.charCodeAt(0);
} else if (s[i] === ',' || s[i] === ']') {
if (s[i - 1] >= '0' && s[i - 1] <= '9') {
stk[stk.length - 1].add(new NestedInteger(neg ? -x : x));
}
x = 0;
neg = false;
if (s[i] === ']' && stk.length > 1) {
const t = stk.pop()!;
stk[stk.length - 1].add(t);
}
}
}
return stk[0];
}/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (n NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (n NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (n *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (n NestedInteger) GetList() []*NestedInteger {}
*/
func deserialize(s string) *NestedInteger {
if s[0] != '[' {
v, _ := strconv.Atoi(s)
ans := NestedInteger{}
ans.SetInteger(v)
return &ans
}
stk := []*NestedInteger{}
x := 0
neg := false
for i, c := range s {
if c == '-' {
neg = true
} else if c >= '0' && c <= '9' {
x = x*10 + int(c-'0')
} else if c == '[' {
stk = append(stk, &NestedInteger{})
} else if c == ',' || c == ']' {
if s[i-1] >= '0' && s[i-1] <= '9' {
if neg {
x = -x
}
t := NestedInteger{}
t.SetInteger(x)
stk[len(stk)-1].Add(t)
}
x = 0
neg = false
if c == ']' && len(stk) > 1 {
t := stk[len(stk)-1]
stk = stk[:len(stk)-1]
stk[len(stk)-1].Add(*t)
}
}
}
return stk[0]
}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). |
| Recursion | – |
| Stack | – |
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. |
Frequently asked questions
Is Mini Parser easy or hard?
Mini Parser is usually rated Medium difficulty. The challenge comes from correctly handling nested structures, multi-digit numbers, and negative values while building the nested object representation in a single pass.
How to solve Mini Parser in O(n)?
Parse the string from left to right and construct NestedInteger objects while tracking nesting levels. Using a stack, push a new list when encountering '[' and pop when encountering ']'. Numbers are parsed and appended directly. Because each character is processed once, the algorithm runs in O(n) time.
What is the best approach for Mini Parser?
The stack-based parsing approach is generally considered the best solution. It processes the string sequentially while maintaining a stack to track nested lists. Each character is handled once, giving O(n) time complexity and O(n) space complexity for deeply nested structures.
What data structure is used in Mini Parser?
A stack is the primary data structure used in the iterative solution. It tracks parent lists while parsing nested brackets. The recursive approach instead relies on the call stack to manage nested levels during depth-first parsing.
What is the time complexity of Mini Parser?
The optimal time complexity is O(n), where n is the length of the input string. Each character is processed exactly once during parsing, whether using the stack-based iterative method or recursive deserialization.
Mini Parser Python or Java solution approach
Both Python and Java solutions follow the same logic: parse characters, detect integers, and manage nested lists using a stack or recursion. Python implementations often use simple loops and lists, while Java solutions build NestedInteger objects and maintain a Stack for hierarchy tracking.
Is Mini Parser asked at Google, Amazon, or Meta?
Serialization and deserialization problems like Mini Parser appear in interviews at large tech companies including Amazon, Google, and Meta. The problem tests parsing logic, stack usage, and handling nested structures—skills commonly evaluated in system and data structure interviews.