LeetCode 2628 - JSON Deep Equal

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

The problem asks us to determine whether two JSON values, o1 and o2, are deeply equal. Deep equality goes beyond simple reference or shallow equality. For primitive values such as numbers, strings, booleans, or null, equality is straightforward using strict comparison (===). For arrays, the two arrays are deeply equal if they have the same length, same order, and each corresponding element is deeply equal. For objects, the two objects are deeply equal if they have the exact same set of keys (order does not matter), and the values for each key are also deeply equal recursively.

The input consists of two valid JSON values, which could be primitives, arrays, or objects, and can be nested to a maximum depth of 1000. The total serialized length of each JSON input can be up to 105 characters, which means we cannot rely on inefficient solutions that repeatedly traverse the structure multiple times.

Important edge cases to consider include: comparing null with other values, empty arrays or objects, arrays containing different types (e.g., numbers vs strings), objects with the same keys but different value types, and deeply nested structures that approach the recursion limit.

Approaches

The brute-force approach is to recursively compare values without any optimization. For primitives, we check strict equality. For arrays, we iterate over all elements and recursively compare each pair. For objects, we check that all keys match and recursively compare each corresponding value. This is correct, but for deeply nested structures, recursion depth could be an issue, and repeated key lookups in large objects could increase runtime.

The optimal approach leverages the same recursive strategy but ensures that object keys are compared efficiently by sorting or using hash maps, and arrays are traversed in a single pass. This avoids redundant operations and ensures the comparison is done in a single recursive traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + m)	O(d)	Recursive comparison for every node, d = max nesting depth
Optimal	O(n + m)	O(d)	Single-pass recursive traversal with efficient object key handling, handles nested arrays and objects properly

Algorithm Walkthrough

Check if both values are primitives (number, string, boolean, null). If so, return the result of strict equality.
If both values are arrays, first compare their lengths. If lengths differ, return false.
Recursively iterate through the arrays, comparing corresponding elements using the same deep equality function. If any pair fails, return false.
If both values are objects, extract their keys. If the number of keys differs, return false.
Ensure both objects have the exact same set of keys. For each key, recursively compare the values associated with that key. If any comparison fails, return false.
If all previous checks pass, return true as the two values are deeply equal.

Why it works: At each recursive call, the function guarantees that every corresponding primitive, array element, and object value is compared for exact equality. By checking array lengths and object keys upfront, it eliminates false positives early. The recursion ensures that nested structures are properly validated.

Python Solution

class Solution:
    def areDeeplyEqual(self, o1: any, o2: any) -> bool:
        if type(o1) != type(o2):
            return False
        
        if isinstance(o1, (int, float, str, bool)) or o1 is None:
            return o1 == o2
        
        if isinstance(o1, list):
            if len(o1) != len(o2):
                return False
            return all(self.areDeeplyEqual(a, b) for a, b in zip(o1, o2))
        
        if isinstance(o1, dict):
            if set(o1.keys()) != set(o2.keys()):
                return False
            return all(self.areDeeplyEqual(o1[k], o2[k]) for k in o1)
        
        return False

The Python implementation first checks for type mismatches, ensuring we do not compare incompatible types. Primitive types are compared directly. For lists, we verify length equality and then recursively compare each element. For dictionaries, we check that both have the exact same set of keys and then recursively compare each corresponding value. This implementation naturally handles nested structures through recursion.

Go Solution

func areDeeplyEqual(o1, o2 any) bool {
    switch v1 := o1.(type) {
    case nil:
        return o2 == nil
    case bool, float64, string:
        return o1 == o2
    case []any:
        v2, ok := o2.([]any)
        if !ok || len(v1) != len(v2) {
            return false
        }
        for i := range v1 {
            if !areDeeplyEqual(v1[i], v2[i]) {
                return false
            }
        }
        return true
    case map[string]any:
        v2, ok := o2.(map[string]any)
        if !ok || len(v1) != len(v2) {
            return false
        }
        for k, val1 := range v1 {
            val2, exists := v2[k]
            if !exists || !areDeeplyEqual(val1, val2) {
                return false
            }
        }
        return true
    default:
        return false
    }
}

In Go, we use type assertions to identify the underlying type of each any value. Primitive types are compared directly. Arrays ([]any) and maps (map[string]any) are recursively compared element by element or key by key. Nil checks handle JSON null values correctly.

Worked Examples

Example 1: o1 = {"x":1,"y":2}, o2 = {"x":1,"y":2}

Step	Operation	Result
1	Both are dicts	Compare keys `["x","y"]`
2	Keys match	Compare `o1["x"]` vs `o2["x"]` → 1==1
3	Compare `o1["y"]` vs `o2["y"]` → 2==2	True
4	All checks pass	Return True

Example 2: o1 = {"x":null,"L":[1,2,3]}, o2 = {"x":null,"L":["1","2","3"]}

Step	Operation	Result
1	Both are dicts	Compare keys `["x","L"]`
2	Keys match	Compare `o1["x"]` vs `o2["x"]` → None==None
3	Compare `o1["L"]` vs `o2["L"]` → [1,2,3] vs ["1","2","3"]
4	Compare first elements 1 vs "1" → different types	Return False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each element of arrays or objects is visited once. n, m are the total number of elements in o1 and o2
Space	O(d)	Recursion stack depth is proportional to the maximum nesting depth d, up to 1000

The algorithm traverses each element exactly once, avoiding repeated comparisons. The recursion stack tracks the nested structure, giving linear space in terms of depth rather than total elements.

Test Cases

# Basic examples
assert Solution().areDeeplyEqual({"x":1,"y":2}, {"x":1,"y":2}) == True  # same dict
assert Solution().areDeeplyEqual({"y":2,"x":1}, {"x":1,"y":2}) == True  # keys out of order
assert Solution().areDeeplyEqual({"x":None,"L":[1,2,3]}, {"x":None,"L":["1","2","3"]}) == False  # different array types
assert Solution().areDeeplyEqual(True, False) == False  # boolean mismatch

# Edge cases
assert Solution().areDeeplyEqual([], []) == True  # empty arrays
assert Solution().areDeeplyEqual({}, {}) == True  # empty objects
assert Solution().areDeeplyEqual([1, [2, 3]], [1, [2, 3]]) == True  # nested arrays
assert Solution().areDeeplyEqual([1, [2, 3]], [1, [3, 2]]) == False  # nested array order mismatch
assert Solution().areDeeplyEqual({"a":1,"b":{"c":2}}, {"a":1,"b":{"c":2}}) == True  # nested objects
assert Solution().areDeeplyEqual({"a":1,"b":{"c":2}}, {"a":1,"b":{"c":"2"}}) == False  # nested type mismatch
assert Solution().areDeeplyEqual(None, None) == True  # null equality

Test	Why
Basic dicts	Validates simple key-value equality
Keys out of order	Tests object key order does not matter
Array type mismatch	Ensures type-sensitive comparison
Boolean mismatch	Primitive type inequality
Empty arrays/objects	Validates edge of no elements
Nested arrays/objects	Checks recursion correctness
Nested type mismatch	Confirms type-sensitive deep equality
Null comparison	Ensures JSON null handled

Edge Cases

One