2759. Convert JSON String to Object - Solution

Q: Is Convert JSON String to Object easy or hard?

This problem is considered Hard because it requires implementing a full parser for nested data structures. Handling strings, numbers, arrays, objects, and literals while managing indices and recursion makes the implementation complex.

Q: Convert JSON String to Object Python/Java solution

The core algorithm is language independent. In Python you track an index and recursively parse dictionaries and lists, while in Java you build HashMap and ArrayList structures. Both implementations run in O(n) time and O(n) space using recursive parsing.

Q: How to solve Convert JSON String to Object in O(n)?

Maintain a pointer that walks through the string and parse values based on the current character. Use recursion to parse objects and arrays, reading keys, values, and delimiters sequentially. Since each character is processed once and nested values are parsed directly, the overall complexity remains O(n).

Q: What is the best approach for Convert JSON String to Object?

Recursive descent parsing is the most common solution. You iterate through the string with an index pointer and recursively construct arrays and objects when encountering '[' or '{'. Each character is processed once, resulting in O(n) time and O(n) space for nested structures.

Q: Is Convert JSON String to Object asked at Google/Amazon/Meta?

Problems involving JSON parsing and recursive parsing appear in interviews at large companies including Google and Meta, especially for backend or systems roles. The exact question may vary, but implementing a simplified JSON parser is a known interview-style problem.

Q: What data structure is used in Convert JSON String to Object?

The solution primarily relies on recursion or a stack to manage nested structures. Objects (hash maps) store key-value pairs, arrays store ordered elements, and a stack or call stack tracks the current container during parsing.

Q: What is the time complexity of Convert JSON String to Object?

The optimal implementation runs in O(n) time where n is the length of the JSON string. Every character is scanned once while constructing objects, arrays, or primitive values. Space complexity is O(n) due to recursion depth and the resulting object structure.

The problem

Given a string str, return parsed JSON parsedStr. You may assume the str is a valid JSON string hence it only includes strings, numbers, arrays, objects, booleans, and null. str will not include invisible characters and escape characters.

Please solve it without using the built-in JSON.parse method.

Example 1:

Input: str = '{"a":2,"b":[1,2,3]}'
Output: {"a":2,"b":[1,2,3]}
Explanation: Returns the object represented by the JSON string.

Example 2:

Input: str = 'true'
Output: true
Explanation: Primitive types are valid JSON.

Example 3:

Input: str = '[1,5,"false",{"a":2}]'
Output: [1,5,"false",{"a":2}]
Explanation: Returns the array represented by the JSON string.

Constraints:

str is a valid JSON string
1 <= str.length <= 10⁵

Approach overview

Problem Overview: You receive a JSON string and must convert it into the equivalent JavaScript object or array without using JSON.parse. The parser must correctly interpret nested objects, arrays, numbers, strings, booleans, and null.

Approach 1: Built-in JSON.parse (Baseline) (O(n) time, O(n) space)

The simplest way to convert a JSON string into an object is calling JSON.parse(str). The runtime scans the entire string once and constructs the corresponding structure in memory. Internally this is implemented with a full JSON parser that tokenizes the input and builds nested objects or arrays. This approach is useful as a reference for correctness and performance, but interview versions of the problem usually forbid built-ins because they want you to implement the parser yourself.

Approach 2: Recursive Descent Parsing (Optimal) (O(n) time, O(n) space)

Treat the JSON string as a stream of characters and parse it using recursive functions. Maintain a pointer i that moves through the string. When you encounter {, recursively parse key-value pairs into an object. When you encounter [, recursively parse elements into an array. Strings are parsed by scanning until the closing quote, while numbers and literals (true, false, null) are recognized by reading sequential characters.

The key insight: each JSON structure naturally maps to recursion. Objects contain nested values, and arrays contain elements that may themselves be arrays or objects. Each character is processed once, giving O(n) time complexity. Recursion depth corresponds to nesting depth, so the space complexity is O(n) in the worst case. This technique is a classic example of string parsing combined with recursion.

Approach 3: Iterative Stack-Based Parser (O(n) time, O(n) space)

An alternative implementation replaces recursion with an explicit stack. Iterate through the string character by character. When you see { or [, push a new container onto the stack. When values are parsed, append them to the container at the top of the stack. Encountering closing brackets } or ] pops the container and attaches it to its parent.

This approach simulates the call stack used in recursive parsing but makes control flow explicit. It’s helpful in environments where recursion depth is limited or when you want more control over the parsing state. The algorithm still scans the string once and maintains containers on a stack, so time complexity is O(n) and auxiliary space is O(n). The structure mirrors common techniques used with a stack to process nested expressions.

Recommended for interviews: Recursive descent parsing is what interviewers typically expect. It clearly demonstrates your understanding of parsing nested structures and managing state with a pointer. Mentioning the built-in solution shows practical awareness, while implementing the recursive parser proves you can design the underlying algorithm.

Solution

TypeScript

function jsonParse(str: string): any {
    const n = str.length;
    let i = 0;

    const parseTrue = (): boolean => {
        i += 4;
        return true;
    };

    const parseFalse = (): boolean => {
        i += 5;
        return false;
    };

    const parseNull = (): null => {
        i += 4;
        return null;
    };

    const parseNumber = (): number => {
        let s = '';
        while (i < n) {
            const c = str[i];
            if (c === ',' || c === '}' || c === ']') {
                break;
            }
            s += c;
            i++;
        }
        return Number(s);
    };

    const parseArray = (): any[] => {
        const arr: any[] = [];
        i++;
        while (i < n) {
            const c = str[i];
            if (c === ']') {
                i++;
                break;
            }
            if (c === ',') {
                i++;
                continue;
            }
            const value = parseValue();
            arr.push(value);
        }
        return arr;
    };

    const parseString = (): string => {
        let s = '';
        i++;
        while (i < n) {
            const c = str[i];
            if (c === '"') {
                i++;
                break;
            }
            if (c === '\\') {
                i++;
                s += str[i];
            } else {
                s += c;
            }
            i++;
        }
        return s;
    };

    const parseObject = (): any => {
        const obj: any = {};
        i++;
        while (i < n) {
            const c = str[i];
            if (c === '}') {
                i++;
                break;
            }
            if (c === ',') {
                i++;
                continue;
            }
            const key = parseString();
            i++;
            const value = parseValue();
            obj[key] = value;
        }
        return obj;
    };
    const parseValue = (): any => {
        const c = str[i];
        if (c === '{') {
            return parseObject();
        }
        if (c === '[') {
            return parseArray();
        }
        if (c === '"') {
            return parseString();
        }
        if (c === 't') {
            return parseTrue();
        }
        if (c === 'f') {
            return parseFalse();
        }
        if (c === 'n') {
            return parseNull();
        }
        return parseNumber();
    };
    return parseValue();
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Built-in JSON.parse	O(n)	O(n)	Real-world code where built-ins are allowed
Recursive Descent Parser	O(n)	O(n)	General interview solution for parsing nested JSON
Iterative Stack-Based Parser	O(n)	O(n)	When recursion depth is a concern or iterative control is preferred

Frequently asked questions

Is Convert JSON String to Object easy or hard?

This problem is considered Hard because it requires implementing a full parser for nested data structures. Handling strings, numbers, arrays, objects, and literals while managing indices and recursion makes the implementation complex.

Convert JSON String to Object Python/Java solution

The core algorithm is language independent. In Python you track an index and recursively parse dictionaries and lists, while in Java you build HashMap and ArrayList structures. Both implementations run in O(n) time and O(n) space using recursive parsing.

How to solve Convert JSON String to Object in O(n)?

Maintain a pointer that walks through the string and parse values based on the current character. Use recursion to parse objects and arrays, reading keys, values, and delimiters sequentially. Since each character is processed once and nested values are parsed directly, the overall complexity remains O(n).

What is the best approach for Convert JSON String to Object?

Recursive descent parsing is the most common solution. You iterate through the string with an index pointer and recursively construct arrays and objects when encountering '[' or '{'. Each character is processed once, resulting in O(n) time and O(n) space for nested structures.

Is Convert JSON String to Object asked at Google/Amazon/Meta?

Problems involving JSON parsing and recursive parsing appear in interviews at large companies including Google and Meta, especially for backend or systems roles. The exact question may vary, but implementing a simplified JSON parser is a known interview-style problem.

What data structure is used in Convert JSON String to Object?