LeetCode 385 - Mini Parser

The problem gives us a string representation of a nested integer structure and asks us to reconstruct the corresponding NestedInteger object hierarchy. A NestedInteger can represent one of two things: 1. A single integer value 2.

leetcodemediumstringstackdepth-first-search

LeetCode Problem 385

Difficulty: 🟡 Medium
Topics: String, Stack, Depth-First Search

Solution

Problem Understanding

The problem gives us a string representation of a nested integer structure and asks us to reconstruct the corresponding NestedInteger object hierarchy.

A NestedInteger can represent one of two things:

  1. A single integer value
  2. A list of other NestedInteger objects

The input string uses a format similar to JSON arrays. For example:

  • "324" represents a single integer
  • "[123,[456,[789]]]" represents a nested list structure

The challenge is to correctly parse nested brackets while preserving the hierarchy.

The provided NestedInteger interface handles the actual storage. Our job is only to parse the string and build the structure using methods like:

  • NestedInteger(value) for integers
  • add(elem) for adding children to lists

The constraints are important:

  • The string length can be up to 5 * 10^4
  • Nesting can be deep
  • Numbers may be negative
  • Input is guaranteed to be valid

These constraints tell us that:

  • Recursive substring parsing may become inefficient
  • Repeated string slicing should be avoided
  • We need a linear-time parsing strategy

Several edge cases are especially important:

  • A single integer without brackets, such as "324"
  • Negative numbers, such as "-12"
  • Empty nested lists, such as "[[]]"
  • Deeply nested structures
  • Multi-digit numbers
  • Consecutive nested lists separated by commas

A naive parser can easily fail when distinguishing commas that separate elements at different nesting levels. Proper nesting management is the core challenge.

Approaches

Brute Force Approach

A straightforward solution is to recursively parse substrings.

The idea is:

  • If the string does not start with '[', it must be a single integer
  • Otherwise, remove the outer brackets
  • Split the inside into top-level components
  • Recursively parse each component

The difficulty comes from splitting correctly. We cannot simply split by commas because commas inside nested lists do not separate top-level elements.

For example:

[123,[456,789]]

Splitting blindly by commas produces:

["123", "[456", "789]"]

which is incorrect.

To solve this, the brute-force solution tracks bracket depth while scanning the substring.

Although this approach works, it repeatedly creates substrings and recursive calls. With deeply nested inputs and large strings, the overhead becomes expensive.

Optimal Approach

The optimal solution uses a stack-based iterative parser.

The key observation is that brackets naturally describe a hierarchy, and stacks are ideal for managing nested scopes.

The algorithm processes the string character by character:

  • '[' means a new nested list begins
  • ']' means the current list is complete
  • Digits and '-' build integer values
  • ',' separates elements

Whenever we enter a new list, we push it onto the stack. When we finish a list, we pop it and attach it to its parent.

This avoids:

  • Expensive substring creation
  • Complex recursive splitting logic
  • Multiple passes over the input

The entire string is processed exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Recursive substring parsing creates repeated scans and copies
Optimal O(n) O(n) Single-pass stack-based parser

Algorithm Walkthrough

Stack-Based Parsing Algorithm

  1. First, handle the simplest case.

If the string does not start with '[', then the entire input is just a single integer. We directly return:

NestedInteger(int(s))
  1. Create an empty stack.

The stack stores the currently active nested lists. The top of the stack always represents the current list we are building. 3. Initialize variables for number parsing.

We need:

  • num_start to track where a number begins
  • Current index while scanning the string
  1. Iterate through the string character by character.

At each character, we determine whether it starts a list, ends a list, or belongs to a number. 5. When encountering '[':

Create a new empty NestedInteger list and push it onto the stack.

This represents entering a deeper nesting level. 6. When encountering a digit or '-':

Record the start position if we are beginning a new number.

We do not immediately create the integer because numbers may contain multiple digits. 7. When encountering ',' or ']':

If we were parsing a number, extract the substring, convert it to an integer, and add it to the current top-level list.

This works because commas and closing brackets mark the end of a number token. 8. After processing a number, if the current character is ']' and the stack has more than one element:

  • Pop the completed nested list
  • Add it to its parent list

This reconstructs the hierarchy naturally. 9. After the loop finishes:

The remaining object on the stack is the fully constructed result.

Why it works

The stack always maintains the active nesting hierarchy.

Whenever we see '[', we descend into a deeper list and push a new container. Whenever we see ']', we finish the current container and attach it to its parent.

Because every nested list is processed exactly once and attached at the correct moment, the final structure exactly matches the serialized representation.

Python Solution

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#     def __init__(self, value=None):
#         """
#         If value is not specified, initializes an empty list.
#         Otherwise initializes a single integer equal to value.
#         """
#
#     def isInteger(self):
#         pass
#
#     def add(self, elem):
#         pass
#
#     def setInteger(self, value):
#         pass
#
#     def getInteger(self):
#         pass
#
#     def getList(self):
#         pass

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        # Single integer case
        if s[0] != '[':
            return NestedInteger(int(s))

        stack = []
        num_start = None

        for i, char in enumerate(s):

            if char == '[':
                stack.append(NestedInteger())

            elif char == '-' or char.isdigit():
                if num_start is None:
                    num_start = i

            elif char == ',' or char == ']':
                # Finish parsing a number
                if num_start is not None:
                    number = int(s[num_start:i])
                    stack[-1].add(NestedInteger(number))
                    num_start = None

                # Finish current nested list
                if char == ']' and len(stack) > 1:
                    completed = stack.pop()
                    stack[-1].add(completed)

        return stack[0]

The implementation begins by checking whether the input is a plain integer. This special case is important because inputs like "324" do not contain brackets and therefore do not require stack processing.

The stack stores partially constructed nested lists. Every time we encounter '[', we create a new empty NestedInteger and push it onto the stack.

Number parsing is handled lazily. Instead of constructing integers digit by digit, we record the starting index and wait until we reach either a comma or closing bracket. At that moment, we know the number token is complete.

When a closing bracket appears, the current nested structure is complete. If there is a parent list on the stack, we pop the completed child and add it to the parent.

By the end of the traversal, the stack contains exactly one fully constructed NestedInteger.

Go Solution

import "strconv"

/**
 * // 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
 * 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
 * func (n NestedInteger) GetList() []*NestedInteger {}
 */

func deserialize(s string) *NestedInteger {

	if s[0] != '[' {
		num, _ := strconv.Atoi(s)
		result := &NestedInteger{}
		result.SetInteger(num)
		return result
	}

	stack := []*NestedInteger{}
	numStart := -1

	for i := 0; i < len(s); i++ {
		char := s[i]

		if char == '[' {

			stack = append(stack, &NestedInteger{})

		} else if char == '-' || (char >= '0' && char <= '9') {

			if numStart == -1 {
				numStart = i
			}

		} else if char == ',' || char == ']' {

			if numStart != -1 {
				num, _ := strconv.Atoi(s[numStart:i])

				newInteger := NestedInteger{}
				newInteger.SetInteger(num)

				stack[len(stack)-1].Add(newInteger)

				numStart = -1
			}

			if char == ']' && len(stack) > 1 {

				completed := stack[len(stack)-1]
				stack = stack[:len(stack)-1]

				stack[len(stack)-1].Add(*completed)
			}
		}
	}

	return stack[0]
}

The Go implementation follows the same logic as the Python solution but differs in a few language-specific details.

Go does not support direct stack operations, so slices are used as stacks. Appending pushes elements, and slicing removes the top element.

Since Go distinguishes between values and pointers, the stack stores *NestedInteger pointers. This avoids unnecessary copying and ensures modifications affect the correct objects.

String-to-integer conversion uses strconv.Atoi.

Unlike Python, Go requires explicit integer object creation before adding elements to a nested list.

Worked Examples

Example 1

s = "324"

Since the string does not begin with '[', we immediately return:

NestedInteger(324)

No stack is needed.

Example 2

s = "[123,[456,[789]]]"

Step-by-Step Trace

Index Character Action Stack State
0 [ Push new list [ [] ]
1 1 Start number [ [] ]
4 , Add 123 [ [123] ]
5 [ Push new list [ [123], [] ]
6 4 Start number [ [123], [] ]
9 , Add 456 [ [123], [456] ]
10 [ Push new list [ [123], [456], [] ]
11 7 Start number [ [123], [456], [] ]
14 ] Add 789 [ [123], [456], [789] ]
14 ] Pop nested list [ [123], [456,[789]] ]
15 ] Pop nested list [ [123,[456,[789]]] ]

Final result:

[123,[456,[789]]]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed exactly once
Space O(n) Stack depth and constructed output may require linear space

The algorithm performs a single pass over the input string. Every character contributes to at most one parsing action, making the runtime linear.

The stack size depends on the maximum nesting depth. In the worst case, deeply nested inputs require linear auxiliary space.

Test Cases

# Provided example: single integer
assert Solution().deserialize("324").getInteger() == 324

# Provided example: nested structure
result = Solution().deserialize("[123,[456,[789]]]")
assert result.getList()[0].getInteger() == 123

# Negative integer
assert Solution().deserialize("-42").getInteger() == -42

# Single empty list
result = Solution().deserialize("[]")
assert result.getList() == []

# Nested empty list
result = Solution().deserialize("[[]]")
assert len(result.getList()) == 1

# Multiple integers
result = Solution().deserialize("[1,2,3]")
assert len(result.getList()) == 3

# Deep nesting
result = Solution().deserialize("[[[[1]]]]")
assert result.getList()[0].getList()[0].getList()[0].getList()[0].getInteger() == 1

# Negative numbers in nested lists
result = Solution().deserialize("[-1,[-2,-3]]")
assert result.getList()[0].getInteger() == -1

# Multi-digit numbers
result = Solution().deserialize("[12345,[67890]]")
assert result.getList()[0].getInteger() == 12345

# Mixed nesting
result = Solution().deserialize("[1,[2,[3,[4]]],5]")
assert result.getList()[2].getInteger() == 5
Test Why
"324" Validates plain integer handling
"[123,[456,[789]]]" Validates nested parsing
"-42" Validates negative integer parsing
"[]" Validates empty list handling
"[[]]" Validates nested empty lists
"[1,2,3]" Validates multiple sibling elements
"[[[[1]]]]" Validates deep nesting
"[-1,[-2,-3]]" Validates negative numbers inside lists
"[12345,[67890]]" Validates multi-digit parsing
"[1,[2,[3,[4]]],5]" Validates mixed nesting structures

Edge Cases

Single Integer Input

An input like "324" does not contain brackets. A parser that assumes every input is a list may incorrectly initialize stack structures or fail entirely.

The implementation explicitly checks whether the first character is '['. If not, it directly constructs and returns a single NestedInteger.

Negative Numbers

Negative integers introduce parsing complexity because '-' is not a digit but still belongs to the number token.

The implementation treats '-' as part of number parsing and includes it when extracting substrings before conversion with int() or strconv.Atoi().

Deeply Nested Lists

Inputs such as:

[[[[[1]]]]]

can easily break recursive solutions due to recursion depth limitations or repeated substring creation.

The stack-based iterative solution avoids recursion entirely and handles arbitrary nesting depth within memory limits.

Empty Nested Lists

Cases like:

[[]]

can expose bugs where empty lists are ignored or never attached to their parent.

The implementation creates a new NestedInteger immediately when encountering '[', even before any elements are added. This guarantees that empty lists are preserved correctly.