LeetCode 2727 - Is Object Empty

LeetCode Problem 2727

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

This problem asks us to determine if a given object or array is empty. In JavaScript terms, an object is empty if it has no key-value pairs, while an array is empty if it has no elements. The input is guaranteed to be valid JSON parsed into a JavaScript object or array, which could be represented in Python as a dict or list.

The expected output is a boolean: true if the object or array has no elements, and false otherwise. For example, an object {} or an array [] should return true, while { "x": 1 } or [1,2] should return false.

The constraints tell us that the input can be fairly large in string length (2 <= JSON.stringify(obj).length <= 105), so a naive approach that iterates over every key or element could be unnecessary if we can leverage the built-in properties of objects and arrays.

Important edge cases include empty objects {} and empty arrays [], as well as objects or arrays with elements that are falsy in JavaScript (like null, false, 0). These should not be considered empty because the structure itself contains elements.

The problem also asks if this can be solved in O(1) time. This is possible because in most programming languages, getting the length of an array or counting the number of keys in an object is an O(1) operation internally.

Approaches

A brute-force approach would iterate through all keys of the object or all elements of the array to check if there is any item present. While this works, it is unnecessary because modern languages provide built-in properties (len in Python, Object.keys().length in JavaScript) that give us the answer without iteration.

The optimal approach leverages these built-in properties. For an array, we check its length. For an object, we check the number of keys. Both operations are O(1) because they are computed properties in most implementations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through every key or element to check presence
Optimal	O(1)	O(1)	Use built-in length or key count properties to check emptiness

Algorithm Walkthrough

1. Check the type of the input to determine whether it is an object or array.
2. If the input is an array, return True if its length is zero, otherwise False.
3. If the input is an object, return True if it has no keys, otherwise False.
4. Since the input is guaranteed to be valid JSON, no additional validation is needed.

Why it works: The algorithm works because the length of an array or the number of keys in an object is sufficient to determine emptiness. The guarantee that the input is valid JSON ensures we do not need to handle unexpected types or malformed structures.

Python Solution

class Solution:
    def isEmpty(self, obj: object) -> bool:
        if isinstance(obj, list):
            return len(obj) == 0
        elif isinstance(obj, dict):
            return len(obj) == 0
        return False

The implementation first checks if the input is a list, which corresponds to an array in JSON. If so, it returns True if the list is empty. If the input is a dictionary (JSON object), it returns True if the dictionary has no keys. This directly follows the algorithm steps above and ensures O(1) access for length checks.

Go Solution

func isEmpty(obj interface{}) bool {
    switch v := obj.(type) {
    case []interface{}:
        return len(v) == 0
    case map[string]interface{}:
        return len(v) == 0
    default:
        return false
    }
}

In Go, we use a type switch to determine whether the input is a slice (array) or a map (object). For both slices and maps, checking the length is an O(1) operation. We return false for any unexpected type, though the problem guarantees valid JSON input.

Worked Examples

Example 1: obj = {"x": 5, "y": 42}

Step	Operation	Result
1	Check type	dict
2	Check number of keys	2 keys
3	Compare to 0	Not empty → return False

Example 2: obj = {}

Step	Operation	Result
1	Check type	dict
2	Check number of keys	0 keys
3	Compare to 0	Empty → return True

Example 3: obj = [null, false, 0]

Step	Operation	Result
1	Check type	list
2	Check length	3 elements
3	Compare to 0	Not empty → return False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Checking the length of a list or the number of keys in a dict is an O(1) operation
Space	O(1)	No additional space is used beyond the input

The algorithm leverages built-in properties, so it avoids iteration over the entire input, making it constant time and space.

Test Cases

# Provided examples
assert Solution().isEmpty({"x": 5, "y": 42}) == False  # object with elements
assert Solution().isEmpty({}) == True                   # empty object
assert Solution().isEmpty([None, False, 0]) == False   # array with elements

# Additional test cases
assert Solution().isEmpty([]) == True                   # empty array
assert Solution().isEmpty([1]) == False                # array with one element
assert Solution().isEmpty({"a": {}}) == False          # object with nested empty object
assert Solution().isEmpty({"a": []}) == False          # object with nested empty array

Test	Why
{"x": 5, "y": 42}	Non-empty object
{}	Empty object
[None, False, 0]	Non-empty array with falsy values
[]	Empty array
[1]	Single-element array
{"a": {}}	Nested empty object, still non-empty at top level
{"a": []}	Nested empty array, still non-empty at top level

Edge Cases

First, an object containing only nested empty structures, like {"a": {}} or {"b": []}, might seem empty at first glance. However, the top-level object itself contains keys, so the function correctly returns False.

Second, an array containing falsy values, such as [None, 0, False], could be mistakenly considered empty by a naive implementation that checks truthiness. Our solution checks length, not truthiness, so it handles this case correctly.

Third, extremely large objects or arrays (up to 10^5 in JSON string length) are guaranteed by the constraints, but our O(1) approach does not depend on input size, avoiding performance issues entirely.