2618. Check if Object Instance of Class

Problem Description

The problem requires writing a function that checks if a certain value (referred to as obj) is an instance of a specified class or one of its superclasses. An object is deemed an instance of a class if it has access to the methods defined by that class. This means we need to determine if obj inherits from the prototype of the given class (let's call this classFunction). It's necessary to account for different types of inputs, including cases where the obj or classFunction might be undefined.

Intuition

The intuition behind the solution involves understanding JavaScript's prototypal inheritance. An object in JavaScript inherits properties and methods from its prototype. The prototype chain is a series of linked prototypes; an object has a prototype, that prototype has its own prototype, and so on, until an object's prototype is null.

Knowing this, we must check whether the prototype of the given object is the same as, or linked through a series of prototypes to, the prototype property of the class function (constructor).

The approach can be broken down into several steps:

1. Test if the classFunction is null or undefined. If it is, then definitely obj isn't an instance of it, so we return false.

2. Loop through the prototype chain of obj using Object.getPrototypeOf(). At each step, we:

   a. Compare the prototype of obj with the prototype property of classFunction.

   b. If a match is found, obj is an instance of classFunction or one of the classes in its prototype chain, and we return true.

   c. If a match isn't found, update obj to its own prototype and keep checking up the chain.

3. If we reach the end of the prototype chain (obj's prototype is null), obj is not an instance of classFunction or a superclass, and we return false.

This approach does full justice to the problem by checking the entire inheritance chain, ensuring that the result is accurate even if inheritance spans multiple levels.

Solution Approach

The implementation of the solution involves a fundamental understanding of JavaScript prototypes and iteration. Here is a more detailed walkthrough of the approach taken in the reference solution:

1. Check if classFunction is null or undefined. If so, return false immediately. This is because in JavaScript, null and undefined do not have a prototype chain, and thus, they are not a valid constructor that can create instances.

2. Initiate a loop to traverse the prototype chain of the obj. The loop continues until obj itself is null or undefined. The condition that breaks the loop indicates that we have reached the end of the prototype chain (since the prototype of the last object in a chain is null).

3. Use Object.getPrototypeOf(obj) to access the prototype of obj. This function returns the prototype ([[Prototype]]) or null of the given object.

4. Compare the current prototype of obj to the prototype property of classFunction using proto === classFunction.prototype. If they are equal, this means that the classFunction is in the prototype chain of obj, and therefore obj is an instance of classFunction or one of its ancestors. Return true in this case.

5. If the current prototype does not match, the loop continues. To do so, set obj to its prototype for the next iteration: obj = proto;. This step effectively moves up the prototype chain.

6. If the loop exits without returning true, this means that classFunction.prototype was not found in the prototype chain of obj. Therefore, we return false.

This solution uses a while loop to check the prototype chain, a fundamental pattern used in prototype-based languages like JavaScript for inheritance checks. It takes advantage of the Object.getPrototypeOf() function to access the prototype chain of objects.

The solution doesn't use any additional data structures. The time complexity is O(n), where n is the length of the prototype chain of the obj. This is because in the worst case, the loop will traverse the entire chain. The space complexity is O(1) because no additional space is used besides the variables for iteration and comparison.

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have a class hierarchy where we have a class Animal, a subclass Mammal that extends Animal, and another subclass Dog that extends Mammal. We're interested in checking if an instance of Dog is also an instance of Animal using the solution approach described.

1function Animal() {}
2function Mammal() {}
3Mammal.prototype = Object.create(Animal.prototype);
4function Dog() {}
5Dog.prototype = Object.create(Mammal.prototype);
6
7const myDog = new Dog();

In this setup, Animal is the superclass, Mammal is a subclass that inherits from Animal, and Dog is a subclass that inherits from Mammal. We create an instance of Dog called myDog. We expect that myDog is an instance of Dog, Mammal, and Animal.

Now, let's walk through the solution approach to check if myDog is an instance of Animal:

1. We call our hypothetical function to check: isInstanceOf(myDog, Animal).

2. Inside the function, we first check if Animal is null or undefined. In our case, it's not, so we continue.

3. We start a loop where obj is initially myDog. We will loop through its prototype chain to check if any prototype along the way is the prototype of Animal.

4. We use Object.getPrototypeOf(obj) to get the prototype of myDog, which will be Dog.prototype.

5. We compare Dog.prototype with Animal.prototype using ===. They are not the same, so we move up the prototype chain.

6. We set obj to its own prototype with obj = Object.getPrototypeOf(obj), now obj refers to Mammal.prototype.

7. We compare Mammal.prototype with Animal.prototype. Again, they are not the same, so we continue up the prototype chain.

8. We update obj again with obj = Object.getPrototypeOf(obj), and obj now refers to Animal.prototype.

9. This time, when we compare Animal.prototype with Animal.prototype, we find them to be the same.

10. Since we found a match, our function returns true, correctly identifying that myDog is an instance of Animal based on the prototype chain.

This walkthrough demonstrates the solution's ability to traverse the entire inheritance chain to identify the relationship between an object and a potential superclass, checking each link in the prototype chain until a match is found or until it reaches the end.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the checkIfInstanceOf function is primarily determined by the while loop that traverses the prototype chain of the obj parameter. In the worst-case scenario, this loop will execute once for each link in the prototype chain until it either finds the prototype of classFunction or until it reaches the end of the chain (null). If n represents the number of prototypes in the chain, then the time complexity would be O(n), as each prototype is visited at most once.

Space Complexity

The space complexity of the function is O(1), primarily because it uses a fixed amount of space. Apart from the space used for the parameters and the loop variable proto, the function does not allocate any additional space that grows with the input size. The space required for the function call does not depend on the size of the prototype chain, hence it's constant.