Problem Description

This problem asks you to implement a function that converts JavaScript values into their JSON string representation without using the built-in JSON.stringify method.

The function should handle the following data types:

• null: Should return the string "null"
• string: Should be wrapped in double quotes, e.g., "hello" becomes "\"hello\""
• number: Should be converted to its string representation, e.g., 42 becomes "42"
• boolean: Should return "true" or "false"
• array: Should return elements wrapped in square brackets separated by commas, e.g., [1, 2, 3] becomes "[1,2,3]"
• object: Should return key-value pairs wrapped in curly braces, with keys as strings and separated by commas, e.g., {a: 1, b: 2} becomes "{"a":1,"b":2}"

Key requirements:

1. The output string should not contain extra spaces
2. For objects, the order of keys in the output should match the order returned by Object.keys()
3. The function should recursively handle nested structures (arrays within objects, objects within arrays, etc.)

The solution uses a recursive approach where:

• Base cases handle primitives (null, strings, numbers, booleans)
• For arrays, it maps each element through the same function recursively and joins them with commas
• For objects, it uses Object.entries() to get key-value pairs, converts both keys and values to JSON strings recursively, and formats them as "key":value pairs joined by commas

Intuition

The key insight is that JSON stringification is inherently a recursive process - we need to handle each data type according to its JSON representation rules, and for composite types (arrays and objects), we need to recursively process their contents.

We can think of this problem as a tree traversal where:

• Leaf nodes are primitive values (null, strings, numbers, booleans)
• Internal nodes are containers (arrays and objects) that hold other values

Starting from the simplest cases, we handle each JavaScript type:

1. Primitives first: These are our base cases that don't require recursion. null becomes "null", strings get wrapped in quotes, numbers and booleans just need .toString()

2. Arrays: Once we know how to stringify individual elements, an array is just those stringified elements joined with commas and wrapped in brackets. The pattern [element1,element2,...] naturally emerges.

3. Objects: Similar to arrays, but we need to handle key-value pairs. Since JSON requires keys to be strings, we stringify the key, add a colon, then stringify the value. The pattern {"key1":value1,"key2":value2,...} follows naturally.

The recursive nature becomes clear when we realize that arrays can contain objects, objects can contain arrays, and both can be nested to any depth. By having our function call itself for each element or value, we automatically handle any level of nesting.

Using Object.entries() for objects is a natural choice because it gives us key-value pairs in the correct order, and we can easily transform each pair into the required "key":value format. Similarly, Array.map() is perfect for arrays since we need to transform each element individually before joining them together.

Solution Approach

The implementation uses a recursive function that performs type checking and applies the appropriate conversion for each data type:

1. Handle null case:

if (object === null) {
    return 'null';
}

Since null is technically an object in JavaScript but has special JSON representation, we check it first.

2. Handle string values:

if (typeof object === 'string') {
    return `"${object}"`;
}

Strings are wrapped in double quotes using template literals.

3. Handle numbers and booleans:

if (typeof object === 'number' || typeof object === 'boolean') {
    return object.toString();
}

These primitives are converted directly to strings using .toString().

4. Handle arrays:

if (Array.isArray(object)) {
    return `[${object.map(jsonStringify).join(',')}]`;
}

• Use Array.isArray() to identify arrays (important since arrays are objects in JavaScript)
• Map each element through jsonStringify recursively
• Join the stringified elements with commas
• Wrap the result in square brackets

5. Handle objects:

if (typeof object === 'object') {
    return `{${Object.entries(object)
        .map(([key, value]) => `${jsonStringify(key)}:${jsonStringify(value)}`)
        .join(',')}}`;
}

• Use Object.entries() to get an array of [key, value] pairs
• For each pair, stringify both the key and value recursively
• Format as "key":value (note the key is stringified to ensure it's wrapped in quotes)
• Join all pairs with commas
• Wrap the result in curly braces

6. Default case:

return '';

Returns an empty string for any unexpected types (though in practice, the above cases should cover all valid JSON types).

The recursion naturally handles nested structures - when processing an array containing objects, the function calls itself on each object, which in turn may call itself on nested values, creating a depth-first traversal of the data structure.

Example Walkthrough

Let's walk through converting the object {name: "Alice", scores: [95, 87], active: true} to its JSON string representation.

Step 1: Start with the root object

• Input: {name: "Alice", scores: [95, 87], active: true}
• Type check: It's an object (not null, not an array)
• Use Object.entries() to get: [["name", "Alice"], ["scores", [95, 87]], ["active", true]]

Step 2: Process first key-value pair ["name", "Alice"]

• Stringify key "name":
  • Type: string → wrap in quotes → "\"name\""
• Stringify value "Alice":
  • Type: string → wrap in quotes → "\"Alice\""
• Combine: "\"name\":\"Alice\""

Step 3: Process second key-value pair ["scores", [95, 87]]

• Stringify key "scores":
  • Type: string → wrap in quotes → "\"scores\""
• Stringify value [95, 87]:
  • Type: array → recursively process each element
  • Element 95: Type number → .toString() → "95"
  • Element 87: Type number → .toString() → "87"
  • Join with comma and wrap in brackets → "[95,87]"
• Combine: "\"scores\":[95,87]"

Step 4: Process third key-value pair ["active", true]

• Stringify key "active":
  • Type: string → wrap in quotes → "\"active\""
• Stringify value true:
  • Type: boolean → .toString() → "true"
• Combine: "\"active\":true"

Step 5: Combine all pairs

• Join the three formatted pairs with commas:
  • "\"name\":\"Alice\",\"scores\":[95,87],\"active\":true"
• Wrap in curly braces:
  • "{\"name\":\"Alice\",\"scores\":[95,87],\"active\":true}"

Final Result: "{\"name\":\"Alice\",\"scores\":[95,87],\"active\":true}"

The recursion depth in this example goes two levels deep: the root object contains an array, which contains numbers. Each level applies the appropriate formatting rules, and the recursive calls ensure that nested structures are properly converted regardless of their depth.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the total number of primitive values (strings, numbers, booleans, null) in the entire object structure.

The analysis breaks down as follows:

• For primitive types (null, string, number, boolean): O(1) operations
• For arrays: O(m) where m is the array length, as we recursively process each element
• For objects: O(k) where k is the number of key-value pairs, as we recursively process each entry
• Each primitive value in the nested structure is visited exactly once
• String concatenation and array joining operations are O(n) in total for all the characters/elements being joined

Space Complexity: O(d + n) where d is the maximum depth of the object/array nesting and n is the total size of the output string.

The space complexity consists of:

• Call stack space: O(d) for the recursive calls, where d is the maximum depth of nested objects/arrays
• Output string space: O(n) where n is the length of the final JSON string representation
• Intermediate strings and arrays created during map() and join() operations: O(n) in total
• The dominant factor is typically O(n) for the output string size, but in deeply nested structures with small data, O(d) could be significant

Common Pitfalls

1. Boolean Handling Order in Python

The most critical pitfall in the Python implementation is the order of type checking for booleans. In Python, bool is a subclass of int, so isinstance(True, int) returns True. This means if you check for integers before booleans, boolean values will be incorrectly converted to "1" or "0" instead of "true" or "false".

Incorrect Implementation:

# Wrong order - this will treat booleans as numbers
if isinstance(object, (int, float)):
    return str(object)
if isinstance(object, bool):
    return 'true' if object else 'false'

Correct Implementation:

# Check boolean BEFORE checking for numbers
if isinstance(object, bool):
    return 'true' if object else 'false'
if isinstance(object, (int, float)):
    return str(object)

2. String Escaping for Special Characters

The current implementation doesn't handle special characters in strings that need escaping in JSON, such as quotes, backslashes, newlines, tabs, etc.

Problem Example:

jsonStringify('Hello "World"')  # Returns: "Hello "World"" (invalid JSON)
jsonStringify('Line1\nLine2')   # Returns: "Line1
Line2" (invalid JSON)

Solution:

def escape_string(s):
    """Escape special characters in strings for JSON"""
    escape_dict = {
        '"': '\\"',
        '\\': '\\\\',
        '\n': '\\n',
        '\r': '\\r',
        '\t': '\\t',
        '\b': '\\b',
        '\f': '\\f'
    }
    result = ''
    for char in s:
        if char in escape_dict:
            result += escape_dict[char]
        elif ord(char) < 0x20:
            # Handle other control characters
            result += f'\\u{ord(char):04x}'
        else:
            result += char
    return result

# Then in jsonStringify:
if isinstance(object, str):
    return f'"{escape_string(object)}"'

3. Circular Reference Handling

The recursive implementation doesn't detect circular references, which will cause infinite recursion and a stack overflow.

Problem Example:

obj = {'a': 1}
obj['self'] = obj  # Circular reference
jsonStringify(obj)  # RecursionError: maximum recursion depth exceeded

Solution:

def jsonStringify(object, visited=None):
    if visited is None:
        visited = set()
  
    # Check for circular references in objects and lists
    if isinstance(object, (dict, list)):
        obj_id = id(object)
        if obj_id in visited:
            raise ValueError("Circular reference detected")
        visited.add(obj_id)
  
    # ... rest of the implementation ...
  
    # Remember to pass visited to recursive calls
    if isinstance(object, list):
        array_elements = [jsonStringify(element, visited.copy()) for element in object]
        return f"[{','.join(array_elements)}]"
  
    if isinstance(object, dict):
        key_value_pairs = []
        visited_copy = visited.copy()
        for key, value in object.items():
            stringified_pair = f'{jsonStringify(str(key), visited_copy)}:{jsonStringify(value, visited_copy)}'
            key_value_pairs.append(stringified_pair)
        return f"{{{','.join(key_value_pairs)}}}"

4. Special Numeric Values

JSON doesn't support special numeric values like NaN, Infinity, or -Infinity, but Python's float type does. The current implementation would incorrectly convert these to their string representations.

Problem Example:

jsonStringify(float('nan'))   # Returns: "nan" (invalid JSON)
jsonStringify(float('inf'))   # Returns: "inf" (invalid JSON)

Solution:

import math

if isinstance(object, (int, float)):
    if math.isnan(object) or math.isinf(object):
        return 'null'  # Standard JSON practice
    return str(object)