Jobs

Interviews

Discussions

Array Prototype Last

Easy

Asked by:

More companies

27 views

Topics:

Arrays

Write code that enhances all arrays such that you can call the array.last() method on any array and it will return the last element. If there are no elements in the array, it should return -1.

You may assume the array is the output of JSON.parse.

Example 1:

Input: nums = [null, {}, 3]
Output: 3
Explanation: Calling nums.last() should return the last element: 3.

Example 2:

Input: nums = []
Output: -1
Explanation: Because there are no elements, return -1.

Constraints:

arr is a valid JSON array
0 <= arr.length <= 1000

Try coding it in LeetCode

Array Prototype Last

Easy

Asked by:

27 views

Topics:

Arrays

Write code that enhances all arrays such that you can call the array.last() method on any array and it will return the last element. If there are no elements in the array, it should return -1.

You may assume the array is the output of JSON.parse.

Example 1:

Input: nums = [null, {}, 3]
Output: 3
Explanation: Calling nums.last() should return the last element: 3.

Example 2:

Input: nums = []
Output: -1
Explanation: Because there are no elements, return -1.

Constraints:

arr is a valid JSON array
0 <= arr.length <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data types can the array elements be?
Can the input array ever be null or undefined?
Is modifying the Array prototype globally acceptable, or should I consider a more localized approach?
Besides returning -1 for an empty array, are there any other error conditions I should handle, such as non-array input?
Are there any restrictions on the type of the 'last' method that I'm adding to the Array prototype?

Brute Force Solution

Approach

The brute force approach to finding the last element is simple: check every element in the sequence one at a time. Stop only when you reach the very end, and then you have found the last element. It is similar to manually looking at each item until you find the very last one.

Here's how the algorithm would work step-by-step:

Start at the beginning of the sequence.
Keep going through the sequence, element by element.
Continue until you get to the very end of the sequence.
The element at the very end is the last element.

Code Implementation

def find_last_element_brute_force(sequence_of_items):    last_element = None
    # Start at the beginning of the sequence and go element by element
    for current_index in range(len(sequence_of_items)):
        # This loop finds the last element by iterating to the end
        last_element = sequence_of_items[current_index]

    # Return the last element found at the end of the sequence
    return last_element

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the array once, examining each element sequentially to reach the end. The number of operations is directly proportional to the number of elements in the array, which we denote as 'n'. Therefore, the time complexity is linear with respect to the input size 'n', resulting in O(n).

Space Complexity

O(1) – The provided algorithm iterates through the array to find the last element. It does not use any auxiliary data structures like temporary arrays or hash maps to store intermediate results. The algorithm only requires a constant amount of extra memory to keep track of its current position while iterating. Therefore, the space complexity is O(1) because the auxiliary space used does not depend on the input size N.

Optimal Solution

Approach

We want to add a new capability that gets the last item of a collection directly from the collection itself. Instead of picking values one by one, we need to access this last item directly through an extension.

Here's how the algorithm would work step-by-step:

Think of the collection as a toolbox, and we want to add a button to it that always gives you the last tool.
Add this button to the toolbox that, when pressed, finds the last tool in the box.
Make sure this new button works for any toolbox, no matter how many tools it contains.
If the toolbox is empty, indicate that there are no tools present.

Code Implementation

def array_prototype_last(input_array):
    # Handle empty arrays, prevents index errors.
    if not input_array:
        return None

    # Access the last element, ensuring correctness.
    last_element_index = len(input_array) - 1

    # Return the element at the calculated last index.
    return input_array[last_element_index]

Big(O) Analysis

Time Complexity

O(1) – The 'last' function accesses the array's last element directly using its index. Accessing an array element by its index takes constant time, regardless of the array's size. Therefore, the operation requires only a single step, independent of the number of elements (n) in the array. Thus, the time complexity is O(1).

Space Complexity

O(1) – The provided solution aims to add a 'last' function to the Array prototype. It does not involve creating any new data structures or temporary storage. The operation solely accesses the last element of the existing array. Therefore, the auxiliary space complexity is constant, independent of the array's size (N).

Edge Cases

Case	How to Handle
Empty array	Return -1 immediately when the array's length is zero.
Array with one element	Return the single element in the array.
Array with a large number of elements (performance)	The solution has O(1) time complexity and O(1) space complexity, making it efficient regardless of the array size.
Array containing only null or undefined values	The last element of the array, even if null or undefined, should be returned as is.
Array containing mixed data types (numbers, strings, objects)	The solution should return the last element regardless of its data type without causing errors.
Array with extreme numeric values (very large or very small numbers)	The solution is designed to work with any valid number type, without being affected by numerical limits (within Javascript limitations).
Modifying the array prototype should not affect other parts of the program negatively.	Adding a method to Array.prototype can affect enumeration so consider potential problems when iterating.
What if 'last' property already exists on the Array prototype?	The solution needs to check if 'last' exists before overriding it to prevent unintended side effects; if it exists, either return an error or rename the method.

Empty array

How to Handle:

Return -1 immediately when the array's length is zero.

Array with one element

How to Handle:

Return the single element in the array.

Array with a large number of elements (performance)

How to Handle:

The solution has O(1) time complexity and O(1) space complexity, making it efficient regardless of the array size.

Array containing only null or undefined values

How to Handle:

The last element of the array, even if null or undefined, should be returned as is.

Array containing mixed data types (numbers, strings, objects)

How to Handle:

The solution should return the last element regardless of its data type without causing errors.

Array with extreme numeric values (very large or very small numbers)

How to Handle:

The solution is designed to work with any valid number type, without being affected by numerical limits (within Javascript limitations).

Modifying the array prototype should not affect other parts of the program negatively.

How to Handle:

Adding a method to Array.prototype can affect enumeration so consider potential problems when iterating.

What if 'last' property already exists on the Array prototype?

How to Handle:

The solution needs to check if 'last' exists before overriding it to prevent unintended side effects; if it exists, either return an error or rename the method.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data types can the array elements be?
Can the input array ever be null or undefined?
Is modifying the Array prototype globally acceptable, or should I consider a more localized approach?
Besides returning -1 for an empty array, are there any other error conditions I should handle, such as non-array input?
Are there any restrictions on the type of the 'last' method that I'm adding to the Array prototype?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the sequence.
Keep going through the sequence, element by element.
Continue until you get to the very end of the sequence.
The element at the very end is the last element.

Code Implementation

def find_last_element_brute_force(sequence_of_items):    last_element = None
    # Start at the beginning of the sequence and go element by element
    for current_index in range(len(sequence_of_items)):
        # This loop finds the last element by iterating to the end
        last_element = sequence_of_items[current_index]

    # Return the last element found at the end of the sequence
    return last_element

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of the collection as a toolbox, and we want to add a button to it that always gives you the last tool.
Add this button to the toolbox that, when pressed, finds the last tool in the box.
Make sure this new button works for any toolbox, no matter how many tools it contains.
If the toolbox is empty, indicate that there are no tools present.

Code Implementation

def array_prototype_last(input_array):
    # Handle empty arrays, prevents index errors.
    if not input_array:
        return None

    # Access the last element, ensuring correctness.
    last_element_index = len(input_array) - 1

    # Return the element at the calculated last index.
    return input_array[last_element_index]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array	Return -1 immediately when the array's length is zero.
Array with one element	Return the single element in the array.
Array with a large number of elements (performance)	The solution has O(1) time complexity and O(1) space complexity, making it efficient regardless of the array size.
Array containing only null or undefined values	The last element of the array, even if null or undefined, should be returned as is.
Array containing mixed data types (numbers, strings, objects)	The solution should return the last element regardless of its data type without causing errors.
Array with extreme numeric values (very large or very small numbers)	The solution is designed to work with any valid number type, without being affected by numerical limits (within Javascript limitations).
Modifying the array prototype should not affect other parts of the program negatively.	Adding a method to Array.prototype can affect enumeration so consider potential problems when iterating.
What if 'last' property already exists on the Array prototype?	The solution needs to check if 'last' exists before overriding it to prevent unintended side effects; if it exists, either return an error or rename the method.

Empty array

How to Handle:

Return -1 immediately when the array's length is zero.

Array with one element

How to Handle:

Return the single element in the array.

Array with a large number of elements (performance)

How to Handle:

The solution has O(1) time complexity and O(1) space complexity, making it efficient regardless of the array size.

Array containing only null or undefined values

How to Handle:

The last element of the array, even if null or undefined, should be returned as is.

Array containing mixed data types (numbers, strings, objects)

How to Handle:

The solution should return the last element regardless of its data type without causing errors.

Array with extreme numeric values (very large or very small numbers)

How to Handle:

The solution is designed to work with any valid number type, without being affected by numerical limits (within Javascript limitations).

Modifying the array prototype should not affect other parts of the program negatively.

How to Handle:

Adding a method to Array.prototype can affect enumeration so consider potential problems when iterating.

What if 'last' property already exists on the Array prototype?

How to Handle:

The solution needs to check if 'last' exists before overriding it to prevent unintended side effects; if it exists, either return an error or rename the method.