We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

JSON Deep Equal

Number: 2735

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Determine whether two JSON-parsed values, o1 and o2, are deeply equal. Two values are considered deeply equal if:

  • They are primitive values (number, string, boolean, null) that pass the === equality check.
  • They are arrays having the same length and every corresponding element is deeply equal.
  • They are objects with the same set of keys, and for each key, the associated values are deeply equal.

Key Insights

  • Use recursion to compare nested structures.
  • For primitive types, a simple equality check (=== in JavaScript, == in Python, etc.) suffices.
  • For arrays, verify both have the same length and compare each element recursively.
  • For objects, ensure both have the same keys (order does not matter) then recursively compare the corresponding values.
  • Handle cases where one operand is null or differs by type early to avoid unnecessary recursion.

Space and Time Complexity

Time Complexity: O(N) in the worst-case, where N is the total number of elements/values in the JSON structure. Space Complexity: O(N) due to the recursion call stack in the worst-case scenario of deeply nested objects or arrays.

Solution

We solve this problem using a recursive approach. The algorithm first checks if both values are strictly equal, which handles primitives immediately. For arrays and objects, it verifies that the sizes (length for arrays and number of keys for objects) match. Then it recurses into each element (for arrays) or checks each key-value pair (for objects) to ensure that they are also deeply equal. For objects, the order of keys is irrelevant, so we compare key sets. This method naturally handles nested structures by delegating equality checks to the same function.

Code Solutions

def deep_equal(o1, o2):
    # If both are exactly equal, return True
    if o1 == o2:
        return True
    # If types differ, they are not equal
    if type(o1) != type(o2):
        return False
    # If both are lists, check length and recursively compare each element
    if isinstance(o1, list):
        if len(o1) != len(o2):
            return False
        for item1, item2 in zip(o1, o2):
            if not deep_equal(item1, item2):
                return False
        return True
    # If both are dictionaries, check that they have the same keys and values
    if isinstance(o1, dict):
        if set(o1.keys()) != set(o2.keys()):
            return False
        for key in o1:
            if not deep_equal(o1[key], o2[key]):
                return False
        return True
    # Fallback for other types (should not reach here for valid JSON)
    return False

# Example usage:
# print(deep_equal({"x": 1, "y": 2}, {"y": 2, "x": 1}))
← Back to All Questions