JSON Deep Equal solution and explanation
2 more videos on this problem
JSON Deep Equal - Leetcode 2628 - JavaScript 30-Day ChallengeNeetCodeIO · 13:53 · 5K views
2628. JSON Deep Equal - Day 17/30 Leetcode Javascript ChallengeProgramming Live with Larry · 15:31 · 106 views
JSON Deep Equal - LeetCode 2628 - JavaScript - JS 30 Day Challenge Day 17Alpha-Code · 17:11 · 92 views
The 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
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 <= 1051 <= JSON.stringify(o2).length <= 105maxNestingDepth <= 1000
Approach overview
Problem Overview: You’re given two JSON values and must determine if they are deeply equal. Equality means primitives match exactly, arrays contain equal elements in the same order, and objects contain identical keys with recursively equal values.
Approach 1: JSON.stringify Comparison (O(n) time, O(n) space)
A quick idea is converting both JSON values into strings using JSON.stringify() and comparing the results. If the serialized strings match, the structures appear equal. This works for many simple cases because the entire structure is flattened into a string representation. However, object key order can differ while still representing the same JSON structure. Since JSON.stringify() preserves insertion order, two logically equal objects may serialize differently and produce a false negative.
This approach is occasionally useful for quick checks or controlled environments where object key order is guaranteed. It’s not reliable for a general deep equality check.
Approach 2: Recursive Deep Comparison (DFS) (O(n) time, O(n) space)
The correct solution walks both JSON structures simultaneously using recursion. Start by checking primitive values with strict equality. If both values are arrays, verify their lengths match and recursively compare each element at the same index. If both are objects, compare their key sets first; differing key counts immediately indicate inequality.
After confirming both objects contain the same keys, recursively compare the value for each key. This forms a depth‑first traversal across the entire JSON structure. Every nested value is checked exactly once, producing O(n) time complexity where n is the total number of elements and properties. Recursion depth contributes up to O(n) space in the worst case for deeply nested data.
This pattern is essentially a DFS over a tree-like structure and mirrors problems involving recursion and depth-first search. Objects behave similarly to key-value maps, conceptually related to hash map comparisons.
Approach 3: Iterative Stack Traversal (O(n) time, O(n) space)
The recursive approach can be rewritten using an explicit stack. Push pairs of values that must be compared. Pop a pair, check their types, and push nested elements or key-value pairs when necessary. Arrays push element pairs by index, while objects push pairs for each shared key.
This version avoids recursion depth limits and makes the traversal logic explicit. Complexity remains identical because every node in the JSON structure is processed once.
Recommended for interviews: Recursive deep comparison is the expected solution. It clearly demonstrates understanding of structural equality, recursion, and careful handling of arrays versus objects. Mentioning the JSON.stringify shortcut shows awareness of edge cases, but implementing the recursive comparison shows real problem-solving skill.
Solution
function areDeeplyEqual(o1: any, o2: any): boolean {
if (o1 === null || typeof o1 !== 'object') {
return o1 === o2;
}
if (typeof o1 !== typeof o2) {
return false;
}
if (Array.isArray(o1) !== Array.isArray(o2)) {
return false;
}
if (Array.isArray(o1)) {
if (o1.length !== o2.length) {
return false;
}
for (let i = 0; i < o1.length; i++) {
if (!areDeeplyEqual(o1[i], o2[i])) {
return false;
}
}
return true;
} else {
const keys1 = Object.keys(o1);
const keys2 = Object.keys(o2);
if (keys1.length !== keys2.length) {
return false;
}
for (const key of keys1) {
if (!areDeeplyEqual(o1[key], o2[key])) {
return false;
}
}
return true;
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| JSON.stringify Comparison | O(n) | O(n) | Quick checks where object key order is guaranteed and structures are simple |
| Recursive Deep Comparison (DFS) | O(n) | O(n) | General case; safest and most common interview solution |
| Iterative Stack Traversal | O(n) | O(n) | When avoiding recursion depth limits or implementing explicit traversal |
Frequently asked questions
Is JSON Deep Equal easy or hard?
JSON Deep Equal is generally considered a medium-level problem. The core idea is straightforward, but careful handling of arrays, objects, key comparisons, and recursion makes it slightly tricky. Edge cases like null values and mismatched types are where many implementations fail.
JSON Deep Equal Python/Java solution
The same recursive logic works across languages. In Python, dictionaries and lists are compared recursively. In Java, maps and lists can be traversed with recursion or a stack while checking key sets and element positions. The complexity remains O(n) time and O(n) space.
How to solve JSON Deep Equal in O(n)?
Traverse both JSON values using depth-first search. Compare primitives directly, check array lengths and recursively compare each index, and verify objects have identical key sets before comparing their values. Since each node in the JSON structure is processed once, the algorithm achieves O(n) time complexity.
What is the best approach for JSON Deep Equal?
Recursive deep comparison is the most reliable approach. It walks both JSON structures simultaneously, comparing primitives directly and recursively checking arrays and objects. This guarantees correctness regardless of key ordering or nesting depth. The approach runs in O(n) time where n is the number of elements and properties in the JSON structure.
Is JSON Deep Equal asked at Google/Amazon/Meta?
Deep equality checks appear in frontend and JavaScript-focused interviews, particularly for companies that test practical language knowledge. Variants of this problem are common in frontend roles at companies like Meta, Amazon, and startups where understanding JavaScript objects and recursion is essential.
What data structure is used in JSON Deep Equal?
The algorithm treats JSON as a tree-like structure composed of primitives, arrays, and objects. Recursion or an explicit stack is used to perform depth-first traversal. Objects behave like hash maps where keys must match before comparing values recursively.
What is the time complexity of JSON Deep Equal?
The optimal solution runs in O(n) time because each value, array element, or object property is visited exactly once during traversal. Space complexity is O(n) in the worst case due to recursion depth or an explicit stack when handling deeply nested structures.