2633. Convert Object to JSON String


Problem Description

The challenge here is to implement a function that mimics the behavior of JSON's stringify method, which converts a JavaScript value into a valid JSON string. You need to handle all basic JSON types: strings, numbers, booleans, arrays, objects, and null. You must ensure that when you're converting these values to a JSON string, there are no extra spaces -- the string should be as concise as possible. The order in which object keys are inserted is important, and it should reflect the order provided by the Object.keys() method in JavaScript. Crucially, the use of the built-in JSON.stringify function is not allowed for this challenge.

Intuition

The solution involves recursively converting JavaScript values to JSON strings according to the JSON format specification. The approach taken follows the principles of serialization, handling each data type according to JSON's representation rules.

  • For null, we straightforwardly return the string "null".
  • For strings, we encase them in double quotes (as JSON strings are double-quoted).
  • For numbers and booleans, we simply convert them to their string representations using toString method.
  • Arrays are trickier since they can contain elements of any type, including nested arrays and objects. We handle this by mapping over the array and applying our jsonStringify function to each element, then joining the results with commas and enclosing with square brackets.
  • Objects require us to map over their entries (key-value pairs), stringify each key and value using our function, join these pairs with commas, and wrap the result with curly braces.
  • Finally, if an object is not serializable (like a function or undefined), we'll return an empty string, although in a more robust implementation we might handle this differently (for example, by throwing an exception).

This recursive design allows the function to properly nest arrays and objects within each other, resulting in a valid JSON string of the input value.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Solution Approach

To implement the jsonStringify function, we use recursion and the built-in types and methods of JavaScript. Here's a closer look at how each type of value is handled:

  • Null: If the object is null, we return the string literal "null", as this is its JSON representation.
  • String: We return the string enclosed in double quotes. Any string passed to the function will be surrounded by " characters to comply with the JSON format.
  • Number and Boolean: Both of these data types are directly converted to their string representation using the .toString() method without any additional formatting.
  • Array: Array handling is recursive. We use the Array.map() method which invokes the jsonStringify function on each element of the array. This call will handle any level of nested arrays or objects properly. The results are joined together with commas, and square brackets are added to the start and end of the string to form a proper JSON array. Therefore, the algorithm takes care of arrays within arrays, objects within arrays, and other complex structures.
  • Object: Objects are dealt with by first transforming them into an array of [key, value] pairs using Object.entries(). Each key and value in these pairs is then passed through the jsonStringify function. The keys and values are concatenated with : to form a valid JSON object property. The resulting strings are joined with commas, and the entire string is enclosed in curly braces. Because JavaScript objects are unordered collections of properties, we do not need to sort the keys; we rely on the order provided by Object.keys() as per the problem description.

The constructed solution checks the type of the input value and applies the appropriate handling mechanism. The use of recursion enables the function to handle nested objects or arrays seamlessly. Each recursive call processes a smaller part of the data until the entire object is serialized into a JSON string. The function seamlessly switches between these cases without using additional data structures or complex patterns, adhering strictly to JavaScript's native representations of these data types and JSON format rules.

This custom implementation of a jsonStringify function is a good exercise in understanding serialization and the JSON format rules.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Example Walkthrough

Let's walk through an example to illustrate how the solution approach handles different types of JavaScript values and converts them into a valid JSON string using our custom jsonStringify function.

Assume we have the following JavaScript object:

1const person = {
2  name: "Jane",
3  age: 32,
4  isStudent: false,
5  courses: ["Math", "English", { courseName: "Science" }],
6  nullValue: null,
7};

Here's how jsonStringify(person) would process this object:

  1. Object: Since our input is an object, we initiate the serialization process by getting all [key, value] pairs using Object.entries(person). The algorithm will then recursively process each key and value.

  2. String (Key): Each key, such as "name", is transformed into a string by enclosing it in double quotes to become "\"name\"".

  3. String (Value): The name property's value, "Jane", is also enclosed in double quotes to become "\"Jane\"".

  4. Number: The age property's value 32 is converted to a string by simply doing 32.toString() to become "32".

  5. Boolean: The isStudent boolean value false is serialized directly to its string representation to become "false".

  6. Array: The courses array is where recursion comes into play. The array contains two strings and an object, so each element is serialized separately:

    • The strings "Math" and "English" are enclosed in quotes to become "\"Math\"" and "\"English\"".
    • The object { courseName: "Science" } is itself serialized recursively to become "{"courseName":"Science"}".

    The elements are joined with commas to form the string representation of the array: "[\"Math\",\"English\",{\"courseName\":\"Science\"}]".

  7. Null: The nullValue key leads to a simple translation where null is directly translated to "null".

  8. Combining: Finally, the serialized key-value pairs are concatenated with a colon between them and joined with commas to form the full object, all enclosed in curly braces:

1{"name":"Jane","age":32,"isStudent":false,"courses":["Math","English",{"courseName":"Science"}],"nullValue":null}

This JSON string is the output of our jsonStringify function when given the person object. It has been created without using the built-in JSON.stringify and follows JSON's format specifications closely for each data type.

Solution Implementation

1def json_stringify(obj):
2    """
3    This function takes any value and attempts to convert it to a JSON string.
4    """
5    # Handle the None case explicitly.
6    if obj is None:
7        return 'null'
8
9    # Strings need to be wrapped in quotes.
10    if isinstance(obj, str):
11        return f'"{obj}"'
12
13    # Numbers and Booleans can be converted to string directly.
14    if isinstance(obj, (int, float, bool)):
15        return str(obj)
16
17    # Lists are processed recursively, with each element being converted and joined by commas.
18    if isinstance(obj, list):
19        list_elements = [json_stringify(element) for element in obj]
20        return '[' + ','.join(list_elements) + ']'
21
22    # Dictionaries are processed by converting each key-value pair and joining them by commas.
23    if isinstance(obj, dict):
24        dict_entries = [f'{json_stringify(key)}:{json_stringify(value)}' for key, value in obj.items()]
25        return '{' + ','.join(dict_entries) + '}'
26
27    # Fallback for unsupported types: return an empty string.
28    return ''
29
1import java.util.Map;
2
3public class JsonStringify {
4  
5    /**
6     * This method converts an Object to a JSON string.
7     *
8     * @param object The object to be converted to JSON string.
9     * @return A JSON string representation of the object.
10     */
11    public static String jsonStringify(Object object) {
12        // Explicit handling for null case
13        if (object == null) {
14            return "null";
15        }
16
17        // Handle String objects, wrapping them in quotes
18        if (object instanceof String) {
19            return "\"" + object + "\"";
20        }
21
22        // Handle Number and Boolean objects by using toString method
23        if (object instanceof Number || object instanceof Boolean) {
24            return object.toString();
25        }
26
27        // Handle arrays recursively. Assuming it's an array of Objects for simplicity
28        if (object instanceof Object[]) {
29            Object[] array = (Object[]) object;
30            StringBuilder arrayElementsStringBuilder = new StringBuilder();
31            arrayElementsStringBuilder.append("[");
32            for(int i = 0; i < array.length; i++) {
33                arrayElementsStringBuilder.append(jsonStringify(array[i]));
34                if (i < array.length - 1) {
35                    arrayElementsStringBuilder.append(",");
36                }
37            }
38            arrayElementsStringBuilder.append("]");
39            return arrayElementsStringBuilder.toString();
40        }
41
42        // Handle Map objects (used to represent objects in Java)
43        if (object instanceof Map) {
44            Map<?, ?> map = (Map<?, ?>) object;
45            StringBuilder objectEntriesStringBuilder = new StringBuilder();
46            objectEntriesStringBuilder.append("{");
47            int i = 0;
48            for (Map.Entry<?, ?> entry : map.entrySet()) {
49                // Convert each key-value pair to JSON string
50                objectEntriesStringBuilder.append(jsonStringify(entry.getKey()));
51                objectEntriesStringBuilder.append(":");
52                objectEntriesStringBuilder.append(jsonStringify(entry.getValue()));
53              
54                if (i < map.size() - 1) {
55                    objectEntriesStringBuilder.append(",");
56                }
57                i++;
58            }
59            objectEntriesStringBuilder.append("}");
60            return objectEntriesStringBuilder.toString();
61        }
62
63        // Fallback for unsupported types, returning an empty string
64        return "";
65    }
66
67    // Additional main method for demonstration purposes (optional)
68    public static void main(String[] args) {
69        // You can test the method here by passing various types to the jsonStringify method
70        // Example:
71        String jsonString = jsonStringify("Hello World!");
72        System.out.println(jsonString);  // Outputs: "Hello World!"
73    }
74}
75
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5#include <variant>
6#include <sstream>
7
8// Define a variant type that can hold any of the acceptable JSON types.
9using JsonValue = std::variant<std::monostate, std::nullptr_t, std::string, double, bool, 
10                               std::vector<JsonValue>, std::unordered_map<std::string, JsonValue>>;
11
12// Forward declaration necessary for recursive calls.
13std::string jsonStringify(const JsonValue& value);
14
15// Helper function to convert a std::string to a JSON string (adds quotes around the string).
16std::string jsonStringifyString(const std::string& value) {
17    return "\"" + value + "\"";
18}
19
20// Function to convert JsonValue to a JSON string.
21std::string jsonStringify(const JsonValue& value) {
22
23    // Handle different types using std::visit and a lambda function.
24    return std::visit([](auto&& arg) -> std::string {
25        using T = std::decay_t<decltype(arg)>;
26        if constexpr (std::is_same_v<T, std::nullptr_t>) { // Handle null explicitly.
27            return "null";
28        } else if constexpr (std::is_same_v<T, std::string>) { // Handle strings explicitly.
29            return jsonStringifyString(arg);
30        } else if constexpr (std::is_same_v<T, double> || std::is_same_v<T, bool>) { // Handle numbers and booleans.
31            std::ostringstream ss;
32            ss << arg;
33            return ss.str();
34        } else if constexpr (std::is_same_v<T, std::vector<JsonValue>>) { // Handle arrays recursively.
35            std::string elements;
36            for (const auto& elem : arg) {
37                if (!elements.empty()) elements += ",";
38                elements += jsonStringify(elem);
39            }
40            return "[" + elements + "]";
41        } else if constexpr (std::is_same_v<T, std::unordered_map<std::string, JsonValue>>) { // Handle objects.
42            std::string entries;
43            for (const auto& [key, value] : arg) {
44                if (!entries.empty()) entries += ",";
45                entries += jsonStringifyString(key) + ":" + jsonStringify(value);
46            }
47            return "{" + entries + "}";
48        } else { // Fallback for monostate (the uninitialized state of std::variant).
49            return "";
50        }
51    }, value);
52}
53
1// This function takes any value and attempts to convert it to a JSON string.
2function jsonStringify(object: any): string {
3    // Handle the null case explicitly.
4    if (object === null) {
5        return 'null';
6    }
7
8    // Strings need to be wrapped in quotes.
9    if (typeof object === 'string') {
10        return `"${object}"`;
11    }
12
13    // Numbers and Booleans can be converted to string directly.
14    if (typeof object === 'number' || typeof object === 'boolean') {
15        return object.toString();
16    }
17
18    // Arrays are processed recursively, with each element being converted and joined by commas.
19    if (Array.isArray(object)) {
20        const arrayElementsString = object.map(jsonStringify).join(',');
21        return `[${arrayElementsString}]`;
22    }
23
24    // Objects are processed by converting each key-value pair and joining them by commas.
25    if (typeof object === 'object') {
26        const objectEntriesString = Object.entries(object)
27            .map(([key, value]) => `${jsonStringify(key)}:${jsonStringify(value)}`)
28            .join(',');
29        return `{${objectEntriesString}}`;
30    }
31
32    // Fallback for unsupported types: return an empty string.
33    return '';
34}
35
Not Sure What to Study? Take the 2-min Quiz:

Which of the following is a good use case for backtracking?

Time and Space Complexity

The given jsonStringify function takes an input object and recursively converts it into a JSON string. Analyzing the complexity depends upon the structure of the input object.

Time Complexity

The time complexity of this function is difficult to state definitively without considering the specific structure and size of the input object. However, we can describe the time complexity in terms of the input size.

  1. Primitive Types (null, string, number, boolean): The complexity is O(1) for null, numbers, and boolean values, and O(n) for strings, where n is the length of the string.

  2. Arrays: Time complexity would be O(n * m), where n is the number of elements in the array and m is the size of the largest element (in terms of the time complexity to stringify it). This accounts for mapping over the array (n elements) and the recursive calls for each element which can vary in complexity.

  3. Objects: The complexity would be O(k * m), where k is the number of keys in the object and m is the complexity of the largest value to stringify. This involves the Object.entries() call and mapping over k key-value pairs, with recursion happening depending on the structure and size of value m.

Given these aspects, the overall time complexity has a recursive nature and in the worst case (deeply nested objects or large arrays), it could approach O(n^2) or worse, depending on the complexity of recursion at each level.

Space Complexity

The space complexity will also depend on the input object:

  1. Primitive Types: Space complexity is O(1) for null, numbers, and boolean values, and O(n) for strings, where n is the length of the string.

  2. Arrays: Space complexity is O(n * m), where n is the number of elements in the array and m is the space complexity to stringify the largest element, since each element's JSON string is accumulated into a new array string.

  3. Objects: Space complexity is similar to arrays, O(k * m), where k is the number of keys and m is the space needed for the largest value.

The recursive calls add to the call stack, which also increases the space complexity. For deeply nested structures, the space complexity could be significant due to the recursive stack. Therefore, we can consider the space complexity to be O(n) in less complex cases, scaling to O(n * m) in worse scenarios, with n accounting for depth/number of elements and m accounting for the size of elements.

Considering that JSON stringification typically involves creating new strings (immutable in JavaScript), these strings are likely to consume space linearly with respect to the size and depth of the input.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫