2628. JSON Deep Equal

Problem Description

The problem requires developing a function to check if two values, o1 and o2, are deeply equal. This concept of deep equality extends beyond surface-level comparison (e.g., simply checking if two numbers are the same) and delves into structured data such as arrays and objects. Here, the comparison must be thorough:

• For primitive values (like numbers or strings), they are deeply equal if they are strictly equal (===).
• For arrays, they are deeply equal if they have the same number of elements, each element is in the same order, and each corresponding pair of elements is also deeply equal.
• For objects (ignoring those that are instances of classes), they are deeply equal if they have the same set of keys and each corresponding value pair is deeply equal.

An additional constraint is that we must not use any external deep comparison function like lodash's _.isEqual().

Intuition

To determine if two given values are deeply equal, the solution takes a recursive approach:

• A straightforward comparison is made for primitive values and null.
• If the values are arrays, it checks if they are the same length and then compares each corresponding pair of elements recursively.
• If the values are objects, it gets a list of keys for each, checks if those are the same length (to quickly rule out objects with different sets of keys), and then recursively checks deeply equality for each value associated with each key in the lists.

This approach works by systematically breaking down complex structures (arrays and objects) into simpler problems that are essentially similar to the base case: comparing primitives. Recursion is used to apply the same logic at every level of nested structures, allowing for a consistent method of comparison throughout the entire depth of the data.

Solution Approach

The solution provided above employs recursion to implement deep equality checking between two values, o1 and o2. The recursion acts as a control flow mechanism that allows the function to traverse deeper into arrays and object properties if necessary. Here are the key parts of the algorithm with explanations:

1. Base Case for Primitives and null: Primitive values and null can be checked with a strict equality === comparison. If o1 is null or not an object, the function returns the result of o1 === o2.

2. Type Checking: The algorithm quickly rules out different types by checking whether o1 and o2 are of the same type. This is done using the typeof operator.

3. Array Check and Comparison: The function needs to identify if the values being compared are arrays, which is achieved using Array.isArray(o1) and Array.isArray(o2). If one is an array and the other is not, they can't be deeply equal, so the function returns false.

4. Deep Array Equality: Once it's determined that both o1 and o2 are arrays, the lengths are compared. If the lengths don't match, the arrays can't be deeply equal. If the lengths are the same, the function iteratively compares each element pair using a for-loop while recursively calling areDeeplyEqual to check the deep equality of each pair.

5. Object Property Equality: If o1 and o2 are not arrays, the code treats them as objects. It retrieves the keys from both objects with Object.keys and compares the lengths of these keys arrays. If they're unequal, it can immediately return false. Otherwise, it iterates over the keys of one object, calling areDeeplyEqual recursively for each corresponding value pair.

6. Recursive Descent: The recursion is essential to the algorithm, allowing the equality check to be valid no matter how deeply nested the arrays or objects are. Each call to areDeeplyEqual within the loops ensures arrays and objects nested within other arrays and objects are also subjected to this thorough checking.

Given the recursive nature of the function, it implicitly utilizes the call stack as its data structure, each frame holding context for a comparison at a particular level of depth. The patterns here are typical for recursive tree/graph traversal, though simplified because the inputs are limited to arrays and objects without cycles (thanks to the JSON restriction).

No additional data structures are utilized since the structure of the original inputs is directly traversed without the need for transformation or storage of intermediate results beyond what the recursive calls do inherently.

This implementation ensures a full deep equality check in line with the requirements outlined in the problem description.

Example Walkthrough

Let's consider an example where we have two values that we want to compare using the solution approach described above. Our first value o1 is an object, and the second value o2 is another object. We want to determine if they are deeply equal.

1let o1 = {
2  a: 1,
3  b: [1, 2, {c: 3}],
4  d: {e: {f: 4}}
5};
6
7let o2 = {
8  a: 1,
9  b: [1, 2, {c: 3}],
10  d: {e: {f: 4}}
11};

Both o1 and o2 look the same at first glance, but we need to check each element in detail.

1. Base Case for Primitives and null:

   • The algorithm starts by checking o1.a and o2.a, which are both primitive values.
   • Using the === operator, we get that 1 === 1, which is true.

2. Type Checking:

   • Next, o1.b and o2.b are both arrays, so their types match (typeof o1.b returns "object", as it does for o2.b because arrays are objects in JavaScript).

3. Array Check and Comparison:

   • Since both are arrays, we use Array.isArray(o1.b) and Array.isArray(o2.b) to confirm.

4. Deep Array Equality:

   • We compare the lengths of o1.b and o2.b which are both 3, so we move forward.
   • Then we check each element at the corresponding indexes:
     • First pair: o1.b[0] === o2.b[0] (1 === 1 is true).
     • Second pair: o1.b[1] === o2.b[1] (2 === 2 is true).
     • Third pair: They are objects {c: 3}, so the algorithm checks them recursively.
     • During this recursive step, the third pair passes the base case for primitives (o1.b[2].c === o2.b[2].c which is true).

5. Object Property Equality:

   • Lastly, o1.d and o2.d are objects, not arrays. The keys ("e") and their lengths match, so we proceed to their values.
   • o1.d.e and o2.d.e are also objects, triggering another recursion. They have the same set of keys "f", and their values are primitive, so o1.d.e.f === o2.d.e.f (4 === 4 is true).

6. Recursive Descent:

   • Throughout the comparison, the areDeeplyEqual function calls itself for each pair of values that aren't strictly equal primitives, which includes objects and arrays regardless of their nesting level.

Since all checks passed without returning false, o1 and o2 are determined to be deeply equal by the implementation.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the areDeeplyEqual function is O(N), where N represents the total number of elements or properties within the objects (or arrays) being compared. This analysis is based on the fact that each element or property must be visited once to compare them. In the case of arrays, the comparison happens sequentially through iteration, and for objects, it happens by cycling through all the keys.

However, the worst-case time complexity can be more accurately described as O(N * K), where N is the number of elements or properties in the objects and K is the average depth of nested structures within those objects. Each recursive call to areDeeplyEqual for nested objects or arrays adds an additional layer of complexity that is linear to the depth K of the objects.

Space Complexity

The space complexity can also be seen as O(K), due to the recursion stack that grows in proportion to the depth of the nested structures (arrays or objects). Each recursive call takes up some space on the call stack, and in the case of deeply nested objects or arrays, the number of recursive calls corresponds to the depth of those structures.