Jobs

Interviews

Discussions

Convert JSON String to Object

Hard

MongoDB

4 views

Topics:

StringsRecursion

You are given a valid JSON string jsonString. Your task is to convert it into a JavaScript object.

Example 1:


Input: jsonString = '{"name":"John", "age":30, "city":"New York"}'
Output: {"name":"John", "age":30, "city":"New York"}
Explanation: The JSON string is successfully converted into a JavaScript object.

Example 2:


Input: jsonString = '[1, 2, 3, 4, 5]'
Output: [1, 2, 3, 4, 5]
Explanation: The JSON string representing an array is correctly converted into a JavaScript array.

Example 3:


Input: jsonString = '{"success": true, "message": "Operation completed successfully"}'
Output: {"success": true, "message": "Operation completed successfully"}
Explanation: A more complex JSON with boolean and string values is parsed without issues.

Constraints:

jsonString is a valid JSON string.

Try coding it in LeetCode

Convert JSON String to Object

Hard

MongoDB

4 views

Topics:

StringsRecursion

You are given a valid JSON string jsonString. Your task is to convert it into a JavaScript object.

Example 1:


Input: jsonString = '{"name":"John", "age":30, "city":"New York"}'
Output: {"name":"John", "age":30, "city":"New York"}
Explanation: The JSON string is successfully converted into a JavaScript object.

Example 2:


Input: jsonString = '[1, 2, 3, 4, 5]'
Output: [1, 2, 3, 4, 5]
Explanation: The JSON string representing an array is correctly converted into a JavaScript array.

Example 3:


Input: jsonString = '{"success": true, "message": "Operation completed successfully"}'
Output: {"success": true, "message": "Operation completed successfully"}
Explanation: A more complex JSON with boolean and string values is parsed without issues.

Constraints:

jsonString is a valid JSON string.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What types of values can the JSON object contain (beyond numbers, strings, booleans, null, nested objects, and arrays)? Can I assume all strings are UTF-8 encoded?
Are there any restrictions on the structure of the JSON? For example, can the root be a primitive value (like a number or string) or must it always be an object or array?
What should I do if the jsonString is not a valid JSON? Should I throw an exception, return a specific error code, or something else?
Can the numbers in the JSON string be represented in scientific notation?
Are there any limitations on the depth of nested objects or arrays within the JSON string?

Brute Force Solution

Approach

The brute force approach to converting a JSON string to an object involves trying all possible interpretations of the JSON structure. We explore every potential arrangement of key-value pairs and nested objects until we find one that is valid and represents the data accurately. This is like trying every possible combination until something fits.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the JSON string.
Check if the first character indicates the start of an object or an array. If it doesn't then there is an error.
If it's the start of an object, try to identify the first key by checking for a string followed by a colon.
After you find a potential key, look for its corresponding value. This could be a simple value (like a number or a string) or a nested object/array.
If the value is another object or array, repeat the previous steps to break that smaller section down, working our way deeper.
If the value is simple, store the key and value. Continue processing the rest of the string after that.
Keep doing these steps, working through the JSON string character by character, until you have found the end of the JSON string.
At each step check for syntax errors such as missing colons or incorrect brackets. Report errors when one is found.
The result will be a structured representation (an object) of the JSON data, built up piece by piece after checking every piece of the input.

Code Implementation

def convert_json_to_object_brute_force(json_string):
    index = 0
    json_length = len(json_string)

    def parse_value():
        nonlocal index
        while index < json_length and json_string[index].isspace():
            index += 1

        if index >= json_length:
            return None, False

        current_char = json_string[index]

        if current_char == '"':
            index += 1
            string_start = index
            while index < json_length and json_string[index] != '"':
                index += 1
            string_end = index
            if index >= json_length:
                return None, False
            index += 1
            return json_string[string_start:string_end], True
        elif current_char.isdigit() or current_char == '-':
            number_start = index
            while index < json_length and (json_string[index].isdigit() or json_string[index] == '.' or json_string[index] == '-'):
                index += 1
            number_string = json_string[number_start:index]
            try:
                return int(number_string), True
            except ValueError:
                try:
                    return float(number_string), True
                except ValueError:
                    return None, False
        elif current_char == '{':
            object_value, success = parse_object()
            return object_value, success
        elif current_char == '[':
            array_value, success = parse_array()
            return array_value, success
        elif json_string[index:index+4] == 'true':
            index += 4
            return True, True
        elif json_string[index:index+5] == 'false':
            index += 5
            return False, True
        elif json_string[index:index+4] == 'null':
            index += 4
            return None, True
        else:
            return None, False

    def parse_array():
        nonlocal index
        index += 1
        array_result = []
        while index < json_length:
            value, success = parse_value()
            if not success:
                return None, False
            array_result.append(value)
            while index < json_length and json_string[index].isspace():
                index += 1
            if index < json_length and json_string[index] == ',':
                index += 1
            elif index < json_length and json_string[index] == ']':
                index += 1
                return array_result, True
            else:
                return None, False
        return None, False

    def parse_object():
        nonlocal index
        index += 1
        object_result = {}
        while index < json_length:
            while index < json_length and json_string[index].isspace():
                index += 1

            key, success = parse_value()
            if not success:
                return None, False

            while index < json_length and json_string[index].isspace():
                index += 1

            if index >= json_length or json_string[index] != ':':
                return None, False

            index += 1
            value, success = parse_value()
            if not success:
                return None, False
            object_result[key] = value

            while index < json_length and json_string[index].isspace():
                index += 1

            if index < json_length and json_string[index] == ',':
                index += 1
            elif index < json_length and json_string[index] == '}':
                index += 1
                return object_result, True
            else:
                return None, False
        return None, False

    while index < json_length and json_string[index].isspace():
        index += 1

    if index < json_length and json_string[index] == '{':
        # JSON string starts with an object
        result, success = parse_object()
        if success:
            return result
        else:
            return None
    elif index < json_length and json_string[index] == '[':
        # JSON string starts with an array
        result, success = parse_array()
        if success:
            return result
        else:
            return None
    else:
        # Handle other cases or errors
        return None

Big(O) Analysis

Time Complexity

O(n!) – The described brute force approach attempts all possible interpretations of the JSON string. In the worst-case scenario, for each character in the input string of size n, the algorithm explores numerous possibilities for key-value pairs and nested objects. This leads to a factorial number of potential arrangements that must be evaluated before a valid interpretation is found or all options are exhausted. Therefore, the number of operations grows proportional to n!, resulting in a time complexity of O(n!).

Space Complexity

O(N) – The primary driver of space complexity in this brute-force JSON parsing approach is the potential depth of nested objects or arrays. In the worst-case scenario, the JSON string could represent a deeply nested structure, requiring the creation of a call stack frame for each level of nesting during the recursive parsing process. Thus, the maximum depth of the recursion, and therefore the size of the call stack, is proportional to the number of nested levels, which in the worst case can be linearly related to the length of the input string (N). Therefore the space complexity is O(N).

Optimal Solution

Approach

The best way to turn a text-based JSON into a usable object is to carefully read it piece by piece. We analyze each character and use that to build the structure of the object step by step, recognizing data types and relationships as we go.

Here's how the algorithm would work step-by-step:

First, confirm you have a valid JSON string to work with.
Start reading the JSON string from the beginning.
When you find the beginning of a structure (like an object or an array), prepare to create that type of data structure.
Identify key-value pairs within objects by looking for names enclosed in quotes followed by a colon.
Determine the type of value: Is it text, a number, another object, or an array? This will tell you how to store the information.
If you encounter a nested object or array, repeat the process inside it.
Carefully handle special characters, like escape sequences, so that the strings are correctly interpreted.
Continue until you have processed the entire JSON string and constructed the complete object.

Code Implementation

import re

class Solution:
    def convert_json_string_to_object(self, json_string: str):
        if json_string is None or json_string.strip() == "":
            return {}

        json_string = json_string.strip()

        if json_string.startswith("{"):
            return self.parse_json_object(json_string)
        elif json_string.startswith("["):
            return self.parse_json_array(json_string)
        else:
            return self.parse_json_primitive(json_string)

    def parse_json_object(self, json_string: str):
        obj = {}
        json_string = json_string[1:-1].strip()  # remove { }

        if not json_string:
            return obj

        # Split key-value pairs by commas not inside quotes
        key_value_pairs = re.split(r',(?=(?:[^"]*"[^"]*")*[^"]*$)', json_string)

        for pair in key_value_pairs:
            parts = pair.split(":", 1)
            key = parts[0].replace('"', '').strip()
            value = parts[1].strip()

            # Recursively convert the value
            obj[key] = self.convert_json_string_to_object(value)

        return obj

    def parse_json_array(self, json_string: str):
        arr = []
        json_string = json_string[1:-1].strip()  # remove [ ]

        if not json_string:
            return arr

        # Split elements by commas not inside quotes
        elements = re.split(r',(?=(?:[^"]*"[^"]*")*[^"]*$)', json_string)

        for element in elements:
            arr.append(self.convert_json_string_to_object(element.strip()))

        return arr

    def parse_json_primitive(self, json_string: str):
        if json_string == "null":
            return None
        if json_string == "true":
            return True
        if json_string == "false":
            return False
        if json_string.startswith('"') and json_string.endswith('"'):
            return json_string[1:-1]

        # Try parsing as number
        try:
            if "." in json_string or "e" in json_string or "E" in json_string:
                return float(json_string)
            return int(json_string)
        except ValueError:
            return json_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the JSON string character by character, where n is the length of the JSON string. Each character is examined a fixed number of times to determine its role (e.g., start of object, key, value, delimiter). Nested objects or arrays are processed recursively, but each character is still visited only once during the entire parsing process. Therefore, the time complexity is directly proportional to the length of the input string, resulting in O(n) complexity.

Space Complexity

O(N) – The space complexity is primarily determined by the depth of nested objects and arrays within the JSON string, which can lead to recursive calls building up on the call stack and the creation of temporary data structures to hold intermediate results. As the algorithm parses deeper into the JSON structure, the memory needed to manage these nested structures increases, creating a call stack that grows proportionally to the maximum nesting depth. In the worst-case scenario, the JSON has N levels of nesting or N key-value pairs stored, where N is the length of the input JSON string. Thus, the auxiliary space grows linearly with the depth of nesting, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty JSON string input	Return None or raise a ValueError indicating invalid input, depending on the desired behavior.
JSON string contains only whitespace	Remove whitespace and check if the resulting string is empty; handle as null input.
JSON string with invalid syntax (e.g., missing quotes, unmatched brackets)	Raise a ValueError or SyntaxError during parsing to indicate an invalid JSON format.
JSON string contains numbers exceeding maximum integer value or floating point precision.	The Python interpreter will automatically handle integers and floats without specific intervention, potentially losing precision on extremely large numbers.
JSON string with deeply nested objects and arrays causing recursion depth issues.	Consider iterative parsing or increase recursion limit if needed, but also limit allowed depth to prevent stack overflow.
JSON string contains duplicate keys in objects	The parser should use the last occurrence of the key, overwriting previous values (standard JSON behavior).
JSON string with non-ASCII characters in strings.	Ensure the string is decoded using UTF-8 or appropriate encoding to handle unicode correctly.
JSON string representing a single primitive value (e.g., '123', 'true', 'null', '"hello"')	Return the corresponding Python primitive value directly without requiring a top-level object or array.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What types of values can the JSON object contain (beyond numbers, strings, booleans, null, nested objects, and arrays)? Can I assume all strings are UTF-8 encoded?
Are there any restrictions on the structure of the JSON? For example, can the root be a primitive value (like a number or string) or must it always be an object or array?
What should I do if the jsonString is not a valid JSON? Should I throw an exception, return a specific error code, or something else?
Can the numbers in the JSON string be represented in scientific notation?
Are there any limitations on the depth of nested objects or arrays within the JSON string?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very beginning of the JSON string.
Check if the first character indicates the start of an object or an array. If it doesn't then there is an error.
If it's the start of an object, try to identify the first key by checking for a string followed by a colon.
After you find a potential key, look for its corresponding value. This could be a simple value (like a number or a string) or a nested object/array.
If the value is another object or array, repeat the previous steps to break that smaller section down, working our way deeper.
If the value is simple, store the key and value. Continue processing the rest of the string after that.
Keep doing these steps, working through the JSON string character by character, until you have found the end of the JSON string.
At each step check for syntax errors such as missing colons or incorrect brackets. Report errors when one is found.
The result will be a structured representation (an object) of the JSON data, built up piece by piece after checking every piece of the input.

Code Implementation

def convert_json_to_object_brute_force(json_string):
    index = 0
    json_length = len(json_string)

    def parse_value():
        nonlocal index
        while index < json_length and json_string[index].isspace():
            index += 1

        if index >= json_length:
            return None, False

        current_char = json_string[index]

        if current_char == '"':
            index += 1
            string_start = index
            while index < json_length and json_string[index] != '"':
                index += 1
            string_end = index
            if index >= json_length:
                return None, False
            index += 1
            return json_string[string_start:string_end], True
        elif current_char.isdigit() or current_char == '-':
            number_start = index
            while index < json_length and (json_string[index].isdigit() or json_string[index] == '.' or json_string[index] == '-'):
                index += 1
            number_string = json_string[number_start:index]
            try:
                return int(number_string), True
            except ValueError:
                try:
                    return float(number_string), True
                except ValueError:
                    return None, False
        elif current_char == '{':
            object_value, success = parse_object()
            return object_value, success
        elif current_char == '[':
            array_value, success = parse_array()
            return array_value, success
        elif json_string[index:index+4] == 'true':
            index += 4
            return True, True
        elif json_string[index:index+5] == 'false':
            index += 5
            return False, True
        elif json_string[index:index+4] == 'null':
            index += 4
            return None, True
        else:
            return None, False

    def parse_array():
        nonlocal index
        index += 1
        array_result = []
        while index < json_length:
            value, success = parse_value()
            if not success:
                return None, False
            array_result.append(value)
            while index < json_length and json_string[index].isspace():
                index += 1
            if index < json_length and json_string[index] == ',':
                index += 1
            elif index < json_length and json_string[index] == ']':
                index += 1
                return array_result, True
            else:
                return None, False
        return None, False

    def parse_object():
        nonlocal index
        index += 1
        object_result = {}
        while index < json_length:
            while index < json_length and json_string[index].isspace():
                index += 1

            key, success = parse_value()
            if not success:
                return None, False

            while index < json_length and json_string[index].isspace():
                index += 1

            if index >= json_length or json_string[index] != ':':
                return None, False

            index += 1
            value, success = parse_value()
            if not success:
                return None, False
            object_result[key] = value

            while index < json_length and json_string[index].isspace():
                index += 1

            if index < json_length and json_string[index] == ',':
                index += 1
            elif index < json_length and json_string[index] == '}':
                index += 1
                return object_result, True
            else:
                return None, False
        return None, False

    while index < json_length and json_string[index].isspace():
        index += 1

    if index < json_length and json_string[index] == '{':
        # JSON string starts with an object
        result, success = parse_object()
        if success:
            return result
        else:
            return None
    elif index < json_length and json_string[index] == '[':
        # JSON string starts with an array
        result, success = parse_array()
        if success:
            return result
        else:
            return None
    else:
        # Handle other cases or errors
        return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, confirm you have a valid JSON string to work with.
Start reading the JSON string from the beginning.
When you find the beginning of a structure (like an object or an array), prepare to create that type of data structure.
Identify key-value pairs within objects by looking for names enclosed in quotes followed by a colon.
Determine the type of value: Is it text, a number, another object, or an array? This will tell you how to store the information.
If you encounter a nested object or array, repeat the process inside it.
Carefully handle special characters, like escape sequences, so that the strings are correctly interpreted.
Continue until you have processed the entire JSON string and constructed the complete object.

Code Implementation

import re

class Solution:
    def convert_json_string_to_object(self, json_string: str):
        if json_string is None or json_string.strip() == "":
            return {}

        json_string = json_string.strip()

        if json_string.startswith("{"):
            return self.parse_json_object(json_string)
        elif json_string.startswith("["):
            return self.parse_json_array(json_string)
        else:
            return self.parse_json_primitive(json_string)

    def parse_json_object(self, json_string: str):
        obj = {}
        json_string = json_string[1:-1].strip()  # remove { }

        if not json_string:
            return obj

        # Split key-value pairs by commas not inside quotes
        key_value_pairs = re.split(r',(?=(?:[^"]*"[^"]*")*[^"]*$)', json_string)

        for pair in key_value_pairs:
            parts = pair.split(":", 1)
            key = parts[0].replace('"', '').strip()
            value = parts[1].strip()

            # Recursively convert the value
            obj[key] = self.convert_json_string_to_object(value)

        return obj

    def parse_json_array(self, json_string: str):
        arr = []
        json_string = json_string[1:-1].strip()  # remove [ ]

        if not json_string:
            return arr

        # Split elements by commas not inside quotes
        elements = re.split(r',(?=(?:[^"]*"[^"]*")*[^"]*$)', json_string)

        for element in elements:
            arr.append(self.convert_json_string_to_object(element.strip()))

        return arr

    def parse_json_primitive(self, json_string: str):
        if json_string == "null":
            return None
        if json_string == "true":
            return True
        if json_string == "false":
            return False
        if json_string.startswith('"') and json_string.endswith('"'):
            return json_string[1:-1]

        # Try parsing as number
        try:
            if "." in json_string or "e" in json_string or "E" in json_string:
                return float(json_string)
            return int(json_string)
        except ValueError:
            return json_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty JSON string input	Return None or raise a ValueError indicating invalid input, depending on the desired behavior.
JSON string contains only whitespace	Remove whitespace and check if the resulting string is empty; handle as null input.
JSON string with invalid syntax (e.g., missing quotes, unmatched brackets)	Raise a ValueError or SyntaxError during parsing to indicate an invalid JSON format.
JSON string contains numbers exceeding maximum integer value or floating point precision.	The Python interpreter will automatically handle integers and floats without specific intervention, potentially losing precision on extremely large numbers.
JSON string with deeply nested objects and arrays causing recursion depth issues.	Consider iterative parsing or increase recursion limit if needed, but also limit allowed depth to prevent stack overflow.
JSON string contains duplicate keys in objects	The parser should use the last occurrence of the key, overwriting previous values (standard JSON behavior).
JSON string with non-ASCII characters in strings.	Ensure the string is decoded using UTF-8 or appropriate encoding to handle unicode correctly.
JSON string representing a single primitive value (e.g., '123', 'true', 'null', '"hello"')	Return the corresponding Python primitive value directly without requiring a top-level object or array.