Mini Parser

Medium Stack Stack Basics Original on LeetCode

Reported atAirbnb

Mini Parser is a medium stack problem solved with the stack basics pattern. The best approach, optimal (one pass with a stack), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (split at top-level commas and recurse) up.

Problem

You are given a string s that describes a nested list of integers in bracket notation, for example "[7,[-12,[]],3]", or a single integer such as "-408". Parse it and return the corresponding NestedInteger object.

Each element of a nested list is either an integer or another nested list. You build the result with the provided NestedInteger class: NestedInteger() creates an empty list, NestedInteger(value) holds a single integer, add(ni) appends an element to a list, and setInteger(value) turns the object into a single integer. isInteger(), getInteger() and getList() read it back.

Examples

Example 1

Input
s = "[7,[-12,[]],3]"
Output
[7,[-12,[]],3]
Why
A list holding 7, a sub-list (with -12 and an empty list) and 3. The output shows the returned object written back in the same notation.

Example 2

Input
s = "-408"
Output
-408
Why
Without brackets the string is a single integer, so the result holds an integer, not a list.

Example 3

Input
s = "[[[5]]]"
Output
[[[5]]]
Why
The integer 5 wrapped in three levels of lists.

Constraints

  • 1 <= s.length <= 5 * 10^4
  • s contains only digits, '[', ']', '-' and ',', with no spaces.
  • s is a valid serialization of a nested integer list or of a single integer.
  • Every integer in s is in the range [-10^6, 10^6].

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (split at top-level commas and recurse)O(n · d)O(n · d)
Optimal (one pass with a stack)O(n)O(n)

1Brute force (split at top-level commas and recurse)

TimeO(n · d)Each character is scanned and copied once per level of nesting around it, and d is the maximum depth.
SpaceO(n · d)Substrings at every level of the recursion are alive at the same time.

A valid string is either an integer or [ + comma-separated valid strings + ]. Strip the outer brackets, find the commas at bracket depth 0, and recursively deserialize every piece between them, adding each result to a new list.

  1. If s[0] is not [, return NestedInteger(parseInt(s)).
  2. Take the body between the outer brackets and scan it with a depth counter ([ +1, ] -1).
  3. At each comma with depth 0, and at the end, deserialize the piece since the last cut and add it to the result list (skip empty pieces, which only occur for []).
class Solution {
    public NestedInteger deserialize(String s) {
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        NestedInteger list = new NestedInteger();
        String body = s.substring(1, s.length() - 1);
        int depth = 0, start = 0;
        for (int i = 0; i <= body.length(); i++) {
            if (i == body.length() || (body.charAt(i) == ',' && depth == 0)) {
                if (i > start) list.add(deserialize(body.substring(start, i)));
                start = i + 1;
            } else if (body.charAt(i) == '[') {
                depth++;
            } else if (body.charAt(i) == ']') {
                depth--;
            }
        }
        return list;
    }
}

2Optimal (one pass with a stack)

TimeO(n)Every character is read once and every list is pushed and popped once.
SpaceO(n)The stack holds at most d open lists, and the built structure has O(n) elements.

Read the string left to right, keeping the lists that are still open on a stack. [ pushes a new empty list. A number (with an optional minus sign) is parsed in full and added to the list on top. ] pops the finished list and adds it to the list below it, or makes it the result if the stack is now empty. Commas carry no information.

  1. If s[0] is not [, return NestedInteger(parseInt(s)).
  2. On [: push a new empty NestedInteger.
  3. On - or a digit: read the whole number and add NestedInteger(value) to the top list.
  4. On ]: pop the top; if the stack is empty it is the result, else add it to the new top.
class Solution {
    public NestedInteger deserialize(String s) {
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        Deque<NestedInteger> stack = new ArrayDeque<>();
        NestedInteger result = null;
        int i = 0, n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c == '[') {
                stack.push(new NestedInteger());
                i++;
            } else if (c == ']') {
                NestedInteger done = stack.pop();
                if (stack.isEmpty()) result = done;
                else stack.peek().add(done);
                i++;
            } else if (c == ',') {
                i++;
            } else {
                int j = i + 1;
                while (j < n && Character.isDigit(s.charAt(j))) j++;
                stack.peek().add(new NestedInteger(Integer.parseInt(s.substring(i, j))));
                i = j;
            }
        }
        return result;
    }
}

Edge cases to test

  • A bare integer, including a negative one
  • An empty list [], alone or nested
  • Deep nesting such as [[[[1]]]]
  • Multi-digit and negative numbers next to brackets

Hints

Hint 1

If s does not start with [, it is one integer: wrap it with new NestedInteger(value).

Hint 2

Otherwise strip the outer brackets and cut the inside at commas that are not inside any deeper bracket; each piece is itself a valid serialization.

Hint 3

To avoid re-scanning substrings, read the string once with a stack: [ opens a new list, ] closes the top list and attaches it to the one below, and a number is added to the top list.

FAQ

What is the best time complexity for Mini Parser?

Optimal (one pass with a stack) runs in O(n) time and O(n) extra space. Every character is read once and every list is pushed and popped once.

Which pattern does Mini Parser use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Is there a brute force solution for Mini Parser?

Yes. Brute force (split at top-level commas and recurse) takes O(n · d) time and O(n · d) space. A valid string is either an integer or [ + comma-separated valid strings + ].

Which edge cases should I test for Mini Parser?

A bare integer, including a negative one; An empty list [], alone or nested; Deep nesting such as [[[[1]]]]; Multi-digit and negative numbers next to brackets.