JSON Deep Equal

Problem Statement

Given two values o1 and o2, you are tasked to determine if these two values are deeply equal. The term "deeply equal" necessitates adherence to specific conditions based on the type and structure of the inputs:

• When o1 and o2 are primitive values, they are deeply equal if they are strictly equal (using the === operator in programming terms).
• In the case that o1 and o2 are arrays, they must have identical elements arranged in the same sequence, and each of these elements must recursively meet the deep equality conditions.
• If o1 and o2 are objects, they are considered deeply equal if they possess identical sets of keys, with values for each key recursively satisfying the deep equality conditions.

The provided values o1 and o2 are assumed to be valid JSON objects, meaning they are structured data that can be represented as stringified JSON. This problem must be solved without utilizing any external library functions like lodash's _.isEqual() to compare the objects or arrays deeply.

Examples

Example 1

Input:

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

Output:

true

Explanation:

The keys and values match exactly.

Example 2

Input:

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

Output:

true

Explanation:

Although the keys are in a different order, they still match exactly.

Example 3

Input:

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

Output:

false

Explanation:

The array of numbers is different from the array of strings.

Example 4

Input:

o1 = true, o2 = false

Output:

false

Explanation:

true !== false

Constraints

• 1 <= JSON.stringify(o1).length <= 10^5
• 1 <= JSON.stringify(o2).length <= 10^5
• maxNestingDepth <= 1000

Approach and Intuition

To address this challenge, a recursive approach can be very effective. Employing recursion makes it viable to determine deep equality across nested structures like arrays and objects, which can have other arrays or objects as their elements or properties.

Understanding Required Conditions

1. Primitive Type Comparison: Use strict equality === to compare both value and type.

2. Array Comparison: Check both are arrays with the same length. Recursively verify each element.

3. Object Comparison: Ensure both are objects (and not null). Verify they have the same set of keys. Recursively validate each key-value pair.

Step-by-Step Recursive Approach

1. If both are null, return true.

2. If types differ, return false.

3. If both are arrays:

   • Compare lengths.
   • Recursively compare corresponding elements.

4. If both are objects:

   • Check keys for equality in both length and content.
   • Recursively compare values for each key.

5. For all other types (primitives), use ===.

This recursive strategy is optimal given the constraints, and handles deeply nested structures effectively up to the maximum allowed depth.

Solutions

function sortObjectFields(key, val) {
    if (val && typeof val === "object" && !Array.isArray(val))
        return Object.fromEntries(Object.entries(val).sort());
    else
        return val;
}
    
var deepEqualityCheck = function(obj1, obj2) {
    const obj1Stringified = JSON.stringify(obj1, sortObjectFields);
    const obj2Stringified = JSON.stringify(obj2, sortObjectFields);
    
    return obj1Stringified === obj2Stringified;
};