Facebook Pixel

2759. Convert JSON String to Object 🔒

Hard
Leetcode Link

Problem Description

You need to implement a JSON parser that converts a valid JSON string into its corresponding JavaScript object representation. The function should parse the string character by character without using the built-in JSON.parse method.

The input string str is guaranteed to be valid JSON and will only contain:

  • Strings: Text enclosed in double quotes (e.g., "hello")
  • Numbers: Integer or decimal values (e.g., 42, 3.14, -10)
  • Arrays: Ordered lists enclosed in square brackets (e.g., [1, 2, 3])
  • Objects: Key-value pairs enclosed in curly braces (e.g., {"name": "John", "age": 30})
  • Booleans: true or false
  • Null: null

The parser should handle nested structures, meaning arrays and objects can contain other arrays, objects, or any of the primitive types mentioned above. The string won't contain invisible characters or escape sequences that need special handling beyond basic backslash escaping.

For example:

  • Input: "{"a": 1, "b": [2, 3], "c": {"d": true}}"
  • Output: {a: 1, b: [2, 3], c: {d: true}}

The solution uses a recursive descent parsing approach where it identifies the type of value at the current position (by checking the first character) and calls the appropriate parsing function. The parser maintains an index i to track the current position in the string and advances it as characters are consumed during parsing.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When we look at JSON structure, we notice that each value type starts with a distinctive character. A string always starts with ", an object with {, an array with [, true with t, false with f, null with n, and numbers with a digit or minus sign. This observation gives us a natural way to determine what we're parsing just by looking at the current character.

The key insight is that JSON has a recursive structure - objects can contain other objects, arrays can contain arrays, and both can contain any valid JSON value. This naturally leads us to think about a recursive parsing approach where we have a main function that identifies the value type and delegates to specialized parsing functions.

We can think of parsing as "consuming" characters from left to right. As we read each character, we decide what to do based on what we're currently parsing. For instance, when parsing an object and we encounter a }, we know the object is complete. When parsing a string and we see a closing ", the string ends.

The challenge with nested structures becomes manageable when we realize that each parsing function can simply call back to the main value parser when it needs to parse a nested element. For example, when parseArray encounters a non-delimiter character (not ] or ,), it knows there's a value to parse, so it calls parseValue, which will figure out what type of value it is and handle it appropriately.

By maintaining a single index i that tracks our position in the string and advancing it as we consume characters, we ensure that each character is processed exactly once and in the correct order. Each specialized parsing function knows exactly how many characters to consume (like true always being 4 characters) or when to stop (like reading until the closing quote for strings).

This approach mirrors how we mentally parse JSON - we recognize patterns, handle them according to their type, and recursively process nested structures when we encounter them.

Solution Approach

The implementation uses a recursive descent parser with a shared index pointer to traverse the string. Here's how each component works:

Main Structure:

  • We maintain a global index i that tracks our current position in the string
  • The main entry point is parseValue() which examines the current character and delegates to the appropriate parser

Character-based Dispatching: The parseValue() function acts as a dispatcher by checking the first character:

  • { → call parseObject()
  • [ → call parseArray()
  • " → call parseString()
  • t → call parseTrue()
  • f → call parseFalse()
  • n → call parseNull()
  • Any other character (digit or -) → call parseNumber()

Parsing Primitives:

  1. Boolean and Null Parsing: These are the simplest - we know exactly how many characters to skip:

    • parseTrue(): advances index by 4 characters (for "true")
    • parseFalse(): advances index by 5 characters (for "false")
    • parseNull(): advances index by 4 characters (for "null")

  2. Number Parsing:

    • Accumulates characters into a string until hitting a delimiter (,, }, or ])
    • Converts the accumulated string to a number using Number()

  3. String Parsing:

    • Skips the opening quote and reads until the closing quote
    • Handles escaped characters by checking for backslash \ and including the next character as-is

Parsing Complex Structures:

  1. Array Parsing (parseArray()):

    • Skips the opening [
    • Loops until finding ]:
      • Skips commas between elements
      • Calls parseValue() recursively for each element
      • Pushes each parsed value to the result array
    • Skips the closing ]

  2. Object Parsing (parseObject()):

    • Skips the opening {
    • Loops until finding }:
      • Skips commas between key-value pairs
      • Calls parseString() to get the key (keys are always strings in JSON)
      • Skips the colon : separator
      • Calls parseValue() recursively to get the value
      • Assigns the key-value pair to the result object
    • Skips the closing }

Key Design Patterns:

  1. Mutual Recursion: parseValue() calls specific parsers, which in turn call parseValue() for nested structures
  2. Lookahead Pattern: Each parser examines the current character to decide what to do next
  3. State Management: The shared index i maintains parsing state across all functions
  4. Incremental Consumption: Each parser advances the index only for characters it processes

The algorithm's time complexity is O(n) where n is the length of the input string, as each character is visited exactly once. The space complexity is O(d) where d is the maximum depth of nesting in the JSON structure, due to the recursive call stack.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through parsing the JSON string: {"a":1,"b":[2,true]}

Initial State: i = 0, string = {"a":1,"b":[2,true]}

Step 1: Call parseValue()

  • Current character at index 0 is {
  • Dispatch to parseObject()

Step 2: Inside parseObject()

  • Skip opening {, now i = 1
  • Create empty object result = {}
  • Current character is ", not }, so continue

Step 3: Parse first key-value pair

  • Call parseString() for the key
    • Skip opening ", now i = 2
    • Read character a
    • Hit closing " at index 3
    • Skip closing quote, now i = 4
    • Return key = "a"
  • Skip colon :, now i = 5
  • Call parseValue() for the value
    • Current character is 1
    • Dispatch to parseNumber()
    • Accumulate 1 until hitting , at index 6
    • Return value = 1
  • Set result["a"] = 1
  • Current character is ,, skip it, now i = 7

Step 4: Parse second key-value pair

  • Call parseString() for the key
    • Skip opening ", now i = 8
    • Read character b
    • Hit closing " at index 9
    • Skip closing quote, now i = 10
    • Return key = "b"
  • Skip colon :, now i = 11
  • Call parseValue() for the value
    • Current character is [
    • Dispatch to parseArray()

Step 5: Inside parseArray()

  • Skip opening [, now i = 12
  • Create empty array arr = []
  • Current character is 2, not ], so continue
  • Call parseValue()
    • Current character is 2
    • Dispatch to parseNumber()
    • Accumulate 2 until hitting , at index 13
    • Return 2
  • Push 2 to array: arr = [2]
  • Skip comma ,, now i = 14
  • Call parseValue()
    • Current character is t
    • Dispatch to parseTrue()
    • Skip 4 characters ("true"), now i = 18
    • Return true
  • Push true to array: arr = [2, true]
  • Current character is ]
  • Skip closing ], now i = 19
  • Return arr = [2, true]

Step 6: Back in parseObject()

  • Set result["b"] = [2, true]
  • Current character is }
  • Skip closing }, now i = 20
  • Return result = {a: 1, b: [2, true]}

Final Result: {a: 1, b: [2, true]}

The parser successfully navigated through the nested structure by:

  1. Recognizing each value type by its first character
  2. Recursively calling parseValue() for nested elements
  3. Maintaining a single index that advances through the string
  4. Each specialized parser knowing exactly when to stop (delimiters or fixed lengths)

Solution Implementation

1def jsonParse(str_input: str):
2    """
3    Custom JSON parser implementation
4    Parses a JSON string and returns the corresponding Python value
5  
6    Args:
7        str_input: The JSON string to parse
8  
9    Returns:
10        The parsed Python value
11    """
12    length = len(str_input)
13    current_index = [0]  # Using list to maintain reference in nested functions
14  
15    def parse_true():
16        """
17        Parses the boolean value 'true'
18        Advances the index by 4 characters
19      
20        Returns:
21            The boolean value True
22        """
23        current_index[0] += 4  # Skip 'true'
24        return True
25  
26    def parse_false():
27        """
28        Parses the boolean value 'false'
29        Advances the index by 5 characters
30      
31        Returns:
32            The boolean value False
33        """
34        current_index[0] += 5  # Skip 'false'
35        return False
36  
37    def parse_null():
38        """
39        Parses the null value
40        Advances the index by 4 characters
41      
42        Returns:
43            None
44        """
45        current_index[0] += 4  # Skip 'null'
46        return None
47  
48    def parse_number():
49        """
50        Parses a numeric value from the string
51        Continues reading until a delimiter (comma, closing brace, or closing bracket) is found
52      
53        Returns:
54            The parsed number
55        """
56        number_string = ''
57      
58        # Read characters until we hit a delimiter
59        while current_index[0] < length:
60            current_char = str_input[current_index[0]]
61          
62            # Check for delimiters that indicate end of number
63            if current_char in [',', '}', ']']:
64                break
65          
66            number_string += current_char
67            current_index[0] += 1
68      
69        # Convert string to number (handles both int and float)
70        return float(number_string) if '.' in number_string else int(number_string)
71  
72    def parse_array():
73        """
74        Parses an array from the string
75        Handles nested values recursively
76      
77        Returns:
78            The parsed array (list)
79        """
80        result_array = []
81        current_index[0] += 1  # Skip opening '['
82      
83        while current_index[0] < length:
84            current_char = str_input[current_index[0]]
85          
86            # Check for array end
87            if current_char == ']':
88                current_index[0] += 1  # Skip closing ']'
89                break
90          
91            # Skip commas between elements
92            if current_char == ',':
93                current_index[0] += 1
94                continue
95          
96            # Parse the next value and add to array
97            parsed_value = parse_value()
98            result_array.append(parsed_value)
99      
100        return result_array
101  
102    def parse_string():
103        """
104        Parses a string value from the JSON
105        Handles escape sequences with backslash
106      
107        Returns:
108            The parsed string
109        """
110        result_string = ''
111        current_index[0] += 1  # Skip opening '"'
112      
113        while current_index[0] < length:
114            current_char = str_input[current_index[0]]
115          
116            # Check for string end
117            if current_char == '"':
118                current_index[0] += 1  # Skip closing '"'
119                break
120          
121            # Handle escape sequences
122            if current_char == '\\':
123                current_index[0] += 1  # Skip the backslash
124                result_string += str_input[current_index[0]]  # Add the escaped character
125            else:
126                result_string += current_char
127          
128            current_index[0] += 1
129      
130        return result_string
131  
132    def parse_object():
133        """
134        Parses an object from the JSON string
135        Extracts key-value pairs recursively
136      
137        Returns:
138            The parsed object (dictionary)
139        """
140        result_object = {}
141        current_index[0] += 1  # Skip opening '{'
142      
143        while current_index[0] < length:
144            current_char = str_input[current_index[0]]
145          
146            # Check for object end
147            if current_char == '}':
148                current_index[0] += 1  # Skip closing '}'
149                break
150          
151            # Skip commas between key-value pairs
152            if current_char == ',':
153                current_index[0] += 1
154                continue
155          
156            # Parse key (always a string)
157            key = parse_string()
158            current_index[0] += 1  # Skip the ':' separator
159          
160            # Parse the corresponding value
161            value = parse_value()
162            result_object[key] = value
163      
164        return result_object
165  
166    def parse_value():
167        """
168        Main parsing function that determines the type of value to parse
169        Based on the first character encountered
170      
171        Returns:
172            The parsed value of appropriate type
173        """
174        current_char = str_input[current_index[0]]
175      
176        # Determine parsing strategy based on first character
177        if current_char == '{':
178            return parse_object()
179        if current_char == '[':
180            return parse_array()
181        if current_char == '"':
182            return parse_string()
183        if current_char == 't':
184            return parse_true()
185        if current_char == 'f':
186            return parse_false()
187        if current_char == 'n':
188            return parse_null()
189      
190        # Default to parsing as number
191        return parse_number()
192  
193    # Start parsing from the beginning
194    return parse_value()
195
1/**
2 * Custom JSON parser implementation
3 * Parses a JSON string and returns the corresponding Java Object
4 */
5public class JsonParser {
6    private String str;
7    private int length;
8    private int currentIndex;
9  
10    /**
11     * Main parsing method that accepts a JSON string
12     * @param str The JSON string to parse
13     * @return The parsed Java Object
14     */
15    public Object jsonParse(String str) {
16        this.str = str;
17        this.length = str.length();
18        this.currentIndex = 0;
19      
20        // Start parsing from the beginning
21        return parseValue();
22    }
23  
24    /**
25     * Parses the boolean value 'true'
26     * Advances the index by 4 characters
27     * @return The boolean value true
28     */
29    private boolean parseTrue() {
30        currentIndex += 4; // Skip 'true'
31        return true;
32    }
33  
34    /**
35     * Parses the boolean value 'false'
36     * Advances the index by 5 characters
37     * @return The boolean value false
38     */
39    private boolean parseFalse() {
40        currentIndex += 5; // Skip 'false'
41        return false;
42    }
43  
44    /**
45     * Parses the null value
46     * Advances the index by 4 characters
47     * @return null
48     */
49    private Object parseNull() {
50        currentIndex += 4; // Skip 'null'
51        return null;
52    }
53  
54    /**
55     * Parses a numeric value from the string
56     * Continues reading until a delimiter (comma, closing brace, or closing bracket) is found
57     * @return The parsed number as Double
58     */
59    private Double parseNumber() {
60        StringBuilder numberString = new StringBuilder();
61      
62        // Read characters until we hit a delimiter
63        while (currentIndex < length) {
64            char currentChar = str.charAt(currentIndex);
65          
66            // Check for delimiters that indicate end of number
67            if (currentChar == ',' || currentChar == '}' || currentChar == ']') {
68                break;
69            }
70          
71            numberString.append(currentChar);
72            currentIndex++;
73        }
74      
75        return Double.valueOf(numberString.toString());
76    }
77  
78    /**
79     * Parses an array from the string
80     * Handles nested values recursively
81     * @return The parsed array as ArrayList
82     */
83    private List<Object> parseArray() {
84        List<Object> resultArray = new ArrayList<>();
85        currentIndex++; // Skip opening '['
86      
87        while (currentIndex < length) {
88            char currentChar = str.charAt(currentIndex);
89          
90            // Check for array end
91            if (currentChar == ']') {
92                currentIndex++; // Skip closing ']'
93                break;
94            }
95          
96            // Skip commas between elements
97            if (currentChar == ',') {
98                currentIndex++;
99                continue;
100            }
101          
102            // Parse the next value and add to array
103            Object parsedValue = parseValue();
104            resultArray.add(parsedValue);
105        }
106      
107        return resultArray;
108    }
109  
110    /**
111     * Parses a string value from the JSON
112     * Handles escape sequences with backslash
113     * @return The parsed string
114     */
115    private String parseString() {
116        StringBuilder resultString = new StringBuilder();
117        currentIndex++; // Skip opening '"'
118      
119        while (currentIndex < length) {
120            char currentChar = str.charAt(currentIndex);
121          
122            // Check for string end
123            if (currentChar == '"') {
124                currentIndex++; // Skip closing '"'
125                break;
126            }
127          
128            // Handle escape sequences
129            if (currentChar == '\\') {
130                currentIndex++; // Skip the backslash
131                resultString.append(str.charAt(currentIndex)); // Add the escaped character
132            } else {
133                resultString.append(currentChar);
134            }
135          
136            currentIndex++;
137        }
138      
139        return resultString.toString();
140    }
141  
142    /**
143     * Parses an object from the JSON string
144     * Extracts key-value pairs recursively
145     * @return The parsed object as HashMap
146     */
147    private Map<String, Object> parseObject() {
148        Map<String, Object> resultObject = new HashMap<>();
149        currentIndex++; // Skip opening '{'
150      
151        while (currentIndex < length) {
152            char currentChar = str.charAt(currentIndex);
153          
154            // Check for object end
155            if (currentChar == '}') {
156                currentIndex++; // Skip closing '}'
157                break;
158            }
159          
160            // Skip commas between key-value pairs
161            if (currentChar == ',') {
162                currentIndex++;
163                continue;
164            }
165          
166            // Parse key (always a string)
167            String key = parseString();
168            currentIndex++; // Skip the ':' separator
169          
170            // Parse the corresponding value
171            Object value = parseValue();
172            resultObject.put(key, value);
173        }
174      
175        return resultObject;
176    }
177  
178    /**
179     * Main parsing function that determines the type of value to parse
180     * Based on the first character encountered
181     * @return The parsed value of appropriate type
182     */
183    private Object parseValue() {
184        char currentChar = str.charAt(currentIndex);
185      
186        // Determine parsing strategy based on first character
187        if (currentChar == '{') {
188            return parseObject();
189        }
190        if (currentChar == '[') {
191            return parseArray();
192        }
193        if (currentChar == '"') {
194            return parseString();
195        }
196        if (currentChar == 't') {
197            return parseTrue();
198        }
199        if (currentChar == 'f') {
200            return parseFalse();
201        }
202        if (currentChar == 'n') {
203            return parseNull();
204        }
205      
206        // Default to parsing as number
207        return parseNumber();
208    }
209}
210
1#include <string>
2#include <unordered_map>
3#include <vector>
4#include <any>
5#include <cctype>
6
7class JsonParser {
8private:
9    std::string str;
10    size_t length;
11    size_t currentIndex;
12  
13public:
14    /**
15     * Constructor to initialize the parser with a JSON string
16     * @param jsonString - The JSON string to parse
17     */
18    JsonParser(const std::string& jsonString) : str(jsonString), length(jsonString.length()), currentIndex(0) {}
19  
20    /**
21     * Parses the boolean value 'true'
22     * Advances the index by 4 characters
23     * @returns The boolean value true wrapped in std::any
24     */
25    std::any parseTrue() {
26        currentIndex += 4; // Skip 'true'
27        return true;
28    }
29  
30    /**
31     * Parses the boolean value 'false'
32     * Advances the index by 5 characters
33     * @returns The boolean value false wrapped in std::any
34     */
35    std::any parseFalse() {
36        currentIndex += 5; // Skip 'false'
37        return false;
38    }
39  
40    /**
41     * Parses the null value
42     * Advances the index by 4 characters
43     * @returns nullptr wrapped in std::any
44     */
45    std::any parseNull() {
46        currentIndex += 4; // Skip 'null'
47        return nullptr;
48    }
49  
50    /**
51     * Parses a numeric value from the string
52     * Continues reading until a delimiter (comma, closing brace, or closing bracket) is found
53     * @returns The parsed number wrapped in std::any
54     */
55    std::any parseNumber() {
56        std::string numberString = "";
57      
58        // Read characters until we hit a delimiter
59        while (currentIndex < length) {
60            char currentChar = str[currentIndex];
61          
62            // Check for delimiters that indicate end of number
63            if (currentChar == ',' || currentChar == '}' || currentChar == ']') {
64                break;
65            }
66          
67            numberString += currentChar;
68            currentIndex++;
69        }
70      
71        // Convert string to double for floating point support
72        return std::stod(numberString);
73    }
74  
75    /**
76     * Parses an array from the string
77     * Handles nested values recursively
78     * @returns The parsed array wrapped in std::any
79     */
80    std::any parseArray() {
81        std::vector<std::any> resultArray;
82        currentIndex++; // Skip opening '['
83      
84        while (currentIndex < length) {
85            char currentChar = str[currentIndex];
86          
87            // Check for array end
88            if (currentChar == ']') {
89                currentIndex++; // Skip closing ']'
90                break;
91            }
92          
93            // Skip commas between elements
94            if (currentChar == ',') {
95                currentIndex++;
96                continue;
97            }
98          
99            // Parse the next value and add to array
100            std::any parsedValue = parseValue();
101            resultArray.push_back(parsedValue);
102        }
103      
104        return resultArray;
105    }
106  
107    /**
108     * Parses a string value from the JSON
109     * Handles escape sequences with backslash
110     * @returns The parsed string wrapped in std::any
111     */
112    std::any parseString() {
113        std::string resultString = "";
114        currentIndex++; // Skip opening '"'
115      
116        while (currentIndex < length) {
117            char currentChar = str[currentIndex];
118          
119            // Check for string end
120            if (currentChar == '"') {
121                currentIndex++; // Skip closing '"'
122                break;
123            }
124          
125            // Handle escape sequences
126            if (currentChar == '\\') {
127                currentIndex++; // Skip the backslash
128                resultString += str[currentIndex]; // Add the escaped character
129            } else {
130                resultString += currentChar;
131            }
132          
133            currentIndex++;
134        }
135      
136        return resultString;
137    }
138  
139    /**
140     * Parses an object from the JSON string
141     * Extracts key-value pairs recursively
142     * @returns The parsed object wrapped in std::any
143     */
144    std::any parseObject() {
145        std::unordered_map<std::string, std::any> resultObject;
146        currentIndex++; // Skip opening '{'
147      
148        while (currentIndex < length) {
149            char currentChar = str[currentIndex];
150          
151            // Check for object end
152            if (currentChar == '}') {
153                currentIndex++; // Skip closing '}'
154                break;
155            }
156          
157            // Skip commas between key-value pairs
158            if (currentChar == ',') {
159                currentIndex++;
160                continue;
161            }
162          
163            // Parse key (always a string)
164            std::string key = std::any_cast<std::string>(parseString());
165            currentIndex++; // Skip the ':' separator
166          
167            // Parse the corresponding value
168            std::any value = parseValue();
169            resultObject[key] = value;
170        }
171      
172        return resultObject;
173    }
174  
175    /**
176     * Main parsing function that determines the type of value to parse
177     * Based on the first character encountered
178     * @returns The parsed value of appropriate type wrapped in std::any
179     */
180    std::any parseValue() {
181        char currentChar = str[currentIndex];
182      
183        // Determine parsing strategy based on first character
184        if (currentChar == '{') {
185            return parseObject();
186        }
187        if (currentChar == '[') {
188            return parseArray();
189        }
190        if (currentChar == '"') {
191            return parseString();
192        }
193        if (currentChar == 't') {
194            return parseTrue();
195        }
196        if (currentChar == 'f') {
197            return parseFalse();
198        }
199        if (currentChar == 'n') {
200            return parseNull();
201        }
202      
203        // Default to parsing as number
204        return parseNumber();
205    }
206};
207
208/**
209 * Custom JSON parser implementation
210 * Parses a JSON string and returns the corresponding value
211 * @param str - The JSON string to parse
212 * @returns The parsed value wrapped in std::any
213 */
214std::any jsonParse(const std::string& str) {
215    JsonParser parser(str);
216    return parser.parseValue();
217}
218
1/**
2 * Custom JSON parser implementation
3 * Parses a JSON string and returns the corresponding JavaScript value
4 * @param str - The JSON string to parse
5 * @returns The parsed JavaScript value
6 */
7function jsonParse(str: string): any {
8    const length: number = str.length;
9    let currentIndex: number = 0;
10
11    /**
12     * Parses the boolean value 'true'
13     * Advances the index by 4 characters
14     * @returns The boolean value true
15     */
16    const parseTrue = (): boolean => {
17        currentIndex += 4; // Skip 'true'
18        return true;
19    };
20
21    /**
22     * Parses the boolean value 'false'
23     * Advances the index by 5 characters
24     * @returns The boolean value false
25     */
26    const parseFalse = (): boolean => {
27        currentIndex += 5; // Skip 'false'
28        return false;
29    };
30
31    /**
32     * Parses the null value
33     * Advances the index by 4 characters
34     * @returns null
35     */
36    const parseNull = (): null => {
37        currentIndex += 4; // Skip 'null'
38        return null;
39    };
40
41    /**
42     * Parses a numeric value from the string
43     * Continues reading until a delimiter (comma, closing brace, or closing bracket) is found
44     * @returns The parsed number
45     */
46    const parseNumber = (): number => {
47        let numberString: string = '';
48      
49        // Read characters until we hit a delimiter
50        while (currentIndex < length) {
51            const currentChar: string = str[currentIndex];
52          
53            // Check for delimiters that indicate end of number
54            if (currentChar === ',' || currentChar === '}' || currentChar === ']') {
55                break;
56            }
57          
58            numberString += currentChar;
59            currentIndex++;
60        }
61      
62        return Number(numberString);
63    };
64
65    /**
66     * Parses an array from the string
67     * Handles nested values recursively
68     * @returns The parsed array
69     */
70    const parseArray = (): any[] => {
71        const resultArray: any[] = [];
72        currentIndex++; // Skip opening '['
73      
74        while (currentIndex < length) {
75            const currentChar: string = str[currentIndex];
76          
77            // Check for array end
78            if (currentChar === ']') {
79                currentIndex++; // Skip closing ']'
80                break;
81            }
82          
83            // Skip commas between elements
84            if (currentChar === ',') {
85                currentIndex++;
86                continue;
87            }
88          
89            // Parse the next value and add to array
90            const parsedValue: any = parseValue();
91            resultArray.push(parsedValue);
92        }
93      
94        return resultArray;
95    };
96
97    /**
98     * Parses a string value from the JSON
99     * Handles escape sequences with backslash
100     * @returns The parsed string
101     */
102    const parseString = (): string => {
103        let resultString: string = '';
104        currentIndex++; // Skip opening '"'
105      
106        while (currentIndex < length) {
107            const currentChar: string = str[currentIndex];
108          
109            // Check for string end
110            if (currentChar === '"') {
111                currentIndex++; // Skip closing '"'
112                break;
113            }
114          
115            // Handle escape sequences
116            if (currentChar === '\\') {
117                currentIndex++; // Skip the backslash
118                resultString += str[currentIndex]; // Add the escaped character
119            } else {
120                resultString += currentChar;
121            }
122          
123            currentIndex++;
124        }
125      
126        return resultString;
127    };
128
129    /**
130     * Parses an object from the JSON string
131     * Extracts key-value pairs recursively
132     * @returns The parsed object
133     */
134    const parseObject = (): any => {
135        const resultObject: any = {};
136        currentIndex++; // Skip opening '{'
137      
138        while (currentIndex < length) {
139            const currentChar: string = str[currentIndex];
140          
141            // Check for object end
142            if (currentChar === '}') {
143                currentIndex++; // Skip closing '}'
144                break;
145            }
146          
147            // Skip commas between key-value pairs
148            if (currentChar === ',') {
149                currentIndex++;
150                continue;
151            }
152          
153            // Parse key (always a string)
154            const key: string = parseString();
155            currentIndex++; // Skip the ':' separator
156          
157            // Parse the corresponding value
158            const value: any = parseValue();
159            resultObject[key] = value;
160        }
161      
162        return resultObject;
163    };
164
165    /**
166     * Main parsing function that determines the type of value to parse
167     * Based on the first character encountered
168     * @returns The parsed value of appropriate type
169     */
170    const parseValue = (): any => {
171        const currentChar: string = str[currentIndex];
172      
173        // Determine parsing strategy based on first character
174        if (currentChar === '{') {
175            return parseObject();
176        }
177        if (currentChar === '[') {
178            return parseArray();
179        }
180        if (currentChar === '"') {
181            return parseString();
182        }
183        if (currentChar === 't') {
184            return parseTrue();
185        }
186        if (currentChar === 'f') {
187            return parseFalse();
188        }
189        if (currentChar === 'n') {
190            return parseNull();
191        }
192      
193        // Default to parsing as number
194        return parseNumber();
195    };
196
197    // Start parsing from the beginning
198    return parseValue();
199}
200

Time and Space Complexity

Time Complexity: O(n)

The algorithm processes each character in the input string exactly once. The variable i serves as a pointer that moves forward through the string without backtracking. Each parsing function (parseTrue, parseFalse, parseNull, parseNumber, parseString, parseArray, parseObject) advances the pointer i by the number of characters it consumes. Since every character is visited at most once during the entire parsing process, the time complexity is linear with respect to the length of the input string n.

Space Complexity: O(d + m)

The space complexity consists of two main components:

  1. Recursion Stack Space: O(d) - The parser uses recursive calls for nested structures (objects and arrays). The maximum depth of recursion equals the maximum nesting depth d of the JSON structure. Each recursive call adds a new frame to the call stack.

  2. Output Space: O(m) - The parsed result requires space proportional to the size of the data being stored. This includes:

    • All primitive values (numbers, booleans, null)
    • All string values stored in the output
    • All object and array containers

    Where m represents the total size of the parsed output structure.

The temporary string variables used in parseNumber and parseString contribute O(k) space where k is the length of the longest individual string or number, but this is bounded by O(n) and typically much smaller than the output space.

Therefore, the total space complexity is O(d + m), where d is the maximum nesting depth and m is the size of the output data structure.

Common Pitfalls

1. Index Management with Nested Functions

One of the most common mistakes is incorrectly managing the shared index across nested functions. Using a simple integer variable won't work because integers are immutable in Python, and nested functions would create local copies instead of modifying the shared state.

Incorrect approach:

def jsonParse(str_input: str):
    current_index = 0  # This won't work!
  
    def parse_string():
        current_index += 1  # UnboundLocalError!
        # ...

Solution: Use a mutable container (list) to maintain the reference:

current_index = [0]  # Mutable list
current_index[0] += 1  # Modify the shared value

2. Whitespace Handling

The current implementation assumes no whitespace in the JSON string. Real JSON often contains spaces, tabs, and newlines that need to be skipped.

Problem scenario:

input_str = '{ "key" : "value" }'  # Spaces around colon
# Parser will fail trying to parse the space as a value

Solution: Add a helper function to skip whitespace:

def skip_whitespace():
    while current_index[0] < length and str_input[current_index[0]] in ' \t\n\r':
        current_index[0] += 1

# Call it before parsing values and after structural characters
def parse_object():
    result_object = {}
    current_index[0] += 1  # Skip '{'
    skip_whitespace()  # Skip any whitespace after '{'
  
    while current_index[0] < length:
        skip_whitespace()  # Skip whitespace before checking character
        current_char = str_input[current_index[0]]
        # ...

3. Number Parsing Edge Cases

The current number parser doesn't validate the number format and might incorrectly parse invalid JSON numbers.

Problem scenarios:

  • Leading zeros: "01" (invalid in JSON)
  • Multiple decimal points: "1.2.3"
  • Incomplete numbers: "1e" (scientific notation without exponent)

Solution: Use a more robust number parsing approach:

def parse_number():
    start = current_index[0]
  
    # Handle negative sign
    if str_input[current_index[0]] == '-':
        current_index[0] += 1
  
    # Parse integer part
    if str_input[current_index[0]] == '0':
        current_index[0] += 1
    else:
        while current_index[0] < length and str_input[current_index[0]].isdigit():
            current_index[0] += 1
  
    # Parse decimal part if exists
    if current_index[0] < length and str_input[current_index[0]] == '.':
        current_index[0] += 1
        while current_index[0] < length and str_input[current_index[0]].isdigit():
            current_index[0] += 1
  
    # Parse exponent if exists
    if current_index[0] < length and str_input[current_index[0]] in 'eE':
        current_index[0] += 1
        if current_index[0] < length and str_input[current_index[0]] in '+-':
            current_index[0] += 1
        while current_index[0] < length and str_input[current_index[0]].isdigit():
            current_index[0] += 1
  
    number_str = str_input[start:current_index[0]]
    return float(number_str) if '.' in number_str or 'e' in number_str.lower() else int(number_str)

4. Empty Container Handling

The parser might fail on empty arrays [] or objects {} because it doesn't check for immediate closing brackets.

Solution: Check for empty containers before attempting to parse elements:

def parse_array():
    result_array = []
    current_index[0] += 1  # Skip '['
  
    # Check for empty array
    if current_index[0] < length and str_input[current_index[0]] == ']':
        current_index[0] += 1
        return result_array
  
    # Continue with regular parsing...

5. String Escape Sequences

The current implementation only handles basic backslash escaping but doesn't properly handle all JSON escape sequences like \n, \t, \", \\, etc.

Solution: Implement proper escape sequence handling:

def parse_string():
    result_string = ''
    current_index[0] += 1  # Skip opening '"'
  
    escape_map = {
        'n': '\n',
        't': '\t',
        'r': '\r',
        'b': '\b',
        'f': '\f',
        '"': '"',
        '\\': '\\',
        '/': '/'
    }
  
    while current_index[0] < length:
        current_char = str_input[current_index[0]]
      
        if current_char == '"':
            current_index[0] += 1
            break
      
        if current_char == '\\':
            current_index[0] += 1
            next_char = str_input[current_index[0]]
            result_string += escape_map.get(next_char, next_char)
        else:
            result_string += current_char
      
        current_index[0] += 1
  
    return result_string
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More