Problem

Given two values o1 and o2, return a boolean value indicating whether two values, o1 and o2, are deeply equal.

For two values to be deeply equal , the following conditions must be met:

  • If both values are primitive types, they are deeply equal if they pass the === equality check.

  • If both values are arrays, they are deeply equal if they have the same elements in the same order, and each element is also deeply equal according to these conditions.

  • If both values are objects, they are deeply equal if they have the same keys, and the associated values for each key are also deeply equal according to these conditions.

You may assume both values are the output of JSON.parse. In other words, they are valid JSON.

Please solve it without using lodash’s _.isEqual() function

Examples

Example 1:

1
2
3

Input: o1 = {"x":1,"y":2}, o2 = {"x":1,"y":2}
Output: true
Explanation: The keys and values match exactly.

Example 2:

1
2
3

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:

1
2
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:

1
2
3

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

Solution

Method 1 – Recursive Deep Comparison

Intuition

To check if two JSON values are deeply equal, we need to recursively compare their types and contents. For primitives, use strict equality. For arrays, compare lengths and each element. For objects, compare keys and recursively compare values.

Approach

  1. If both values are strictly equal, return true.
  2. If types differ, return false.
  3. If both are arrays:
    • Check lengths. If not equal, return false.
    • Recursively compare each element.
  4. If both are objects (not null):
    • Check that both have the same set of keys.
    • Recursively compare values for each key.
  5. Otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function deepEqual(o1, o2) {
  if (o1 === o2) return true;
  if (typeof o1 !== typeof o2) return false;
  if (Array.isArray(o1) && Array.isArray(o2)) {
    if (o1.length !== o2.length) return false;
    for (let i = 0; i < o1.length; ++i) {
      if (!deepEqual(o1[i], o2[i])) return false;
    }
    return true;
  }
  if (o1 && o2 && typeof o1 === 'object') {
    const k1 = Object.keys(o1), k2 = Object.keys(o2);
    if (k1.length !== k2.length) return false;
    k1.sort(); k2.sort();
    for (let i = 0; i < k1.length; ++i) if (k1[i] !== k2[i]) return false;
    for (const k of k1) {
      if (!deepEqual(o1[k], o2[k])) return false;
    }
    return true;
  }
  return false;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function deepEqual(o1: any, o2: any): boolean {
  if (o1 === o2) return true;
  if (typeof o1 !== typeof o2) return false;
  if (Array.isArray(o1) && Array.isArray(o2)) {
    if (o1.length !== o2.length) return false;
    for (let i = 0; i < o1.length; ++i) {
      if (!deepEqual(o1[i], o2[i])) return false;
    }
    return true;
  }
  if (o1 && o2 && typeof o1 === 'object') {
    const k1 = Object.keys(o1), k2 = Object.keys(o2);
    if (k1.length !== k2.length) return false;
    k1.sort(); k2.sort();
    for (let i = 0; i < k1.length; ++i) if (k1[i] !== k2[i]) return false;
    for (const k of k1) {
      if (!deepEqual(o1[k], o2[k])) return false;
    }
    return true;
  }
  return false;
}

Complexity

  • ⏰ Time complexity: O(n) — n is the total number of keys and elements in the objects/arrays (in the worst case, all elements are compared).
  • 🧺 Space complexity: O(h) — h is the maximum depth of the nested structure (for recursion stack).