Remove Element

Easy

Uber

2 views

Topics:

ArraysTwo Pointers

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Remove Element

Easy

Uber

2 views

Topics:

ArraysTwo Pointers

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

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 is the range of possible values for elements within the `nums` array and for the `val` itself?
What should be returned if the input array `nums` is null or empty?
Since the order of remaining elements can be changed, can I overwrite the elements after the resulting 'valid' section of the array without affecting the returned count?
Are there any memory constraints to be aware of, or is using O(1) space strictly required?
Can I modify the input array directly, or should I create a copy?

Brute Force Solution

Approach

The brute force method for removing a specific item from a collection of items involves checking each item individually. When we find the item to remove, we figure out a way to get rid of it and then continue looking for other occurrences.

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

Start by looking at the very first item in the collection.
Is this the item we want to remove? If yes, remove it.
If it wasn't the item we wanted to remove, move on to the next item.
Repeat steps 2 and 3 for every single item in the collection.
Once you have examined every item, you are done. The item will be removed from the collection if it was there.

Code Implementation

def remove_element_brute_force(numbers, value_to_remove):
    index = 0
    while index < len(numbers):
        # Check if the current element should be removed
        if numbers[index] == value_to_remove:

            # Remove the element by shifting elements to the left
            for sub_index in range(index, len(numbers) - 1):
                numbers[sub_index] = numbers[sub_index + 1]
            
            numbers.pop()

            # Do not increment index after removal; check current index again

        else:
            # Move to the next element in the list
            index += 1

    return len(numbers)

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach iterates through the input array of size n. When the target value is found, it needs to be removed, and the remaining elements shifted. Shifting elements takes O(n) time in the worst case (when the element to be removed is at the beginning of the array). Since we iterate through the array of size n and potentially perform the shifting operation in O(n) time for each element, the overall time complexity becomes O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The provided plain English explanation outlines a brute-force approach that iterates through the input collection and potentially removes elements. No auxiliary data structures like temporary lists, hash maps, or recursion are mentioned. The algorithm operates directly on the input, modifying it in place, and only requires a constant amount of extra space for loop counters or temporary variables used in element comparison and removal. Thus, the space complexity is constant and independent of the input size N.

Optimal Solution

Approach

The most efficient way to remove specific items from a collection involves strategically shifting elements. Instead of creating a new collection or repeatedly resizing the original, we overwrite unwanted values with those we want to keep, essentially compressing the collection in place.

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

Start by looking at each item in the collection, one by one.
If the current item is something we want to remove, don't do anything yet.
If the current item is something we want to keep, move it to the next available spot at the beginning of the collection that's reserved for items we want to keep.
Keep track of how many items we've decided to keep.
Once we've looked at all the items, the first part of the collection (up to the number of items we want to keep) will contain all the items we decided to keep in their original order.
The remaining part of the collection beyond that number can be ignored because we've effectively compressed the good items into the beginning of the collection.
The number of items we decided to keep represents the new size of the collection after removing the unwanted items.

Code Implementation

def remove_element(numbers, value_to_remove):
    index_to_fill = 0

    for i in range(len(numbers)):
        if numbers[i] != value_to_remove:
            # Overwrite the element at index_to_fill with the current element.
            numbers[index_to_fill] = numbers[i]

            index_to_fill += 1

    # The new length is the number of elements that were kept.
    return index_to_fill

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input array of size n exactly once. For each element, it performs a constant amount of work: checking if the element needs to be removed and, if not, moving it to the correct position. Since the amount of work done for each element is constant and independent of n, the total time complexity is directly proportional to the size of the input array, n.

Space Complexity

O(1) – The algorithm operates in-place, modifying the input array directly. It uses a variable to track the number of elements to keep, which is a constant amount of extra space. No auxiliary data structures like temporary arrays or hash maps are created. Therefore, the auxiliary space used is independent of the input size N and remains constant.

Edge Cases

Case	How to Handle
Empty input array (nums is null or has zero length)	Return 0 since there are no elements to process.
All elements in the array are equal to val	The function should return 0 and the array should effectively be empty (first 0 elements are the result).
No elements in the array are equal to val	The function should return the original length of the array, and the array should remain unchanged.
Array contains a single element which is equal to val	The function should return 0 and the first element is what is left in the array up to position 0.
Array contains a single element which is not equal to val	The function should return 1 and the array remains as is.
Array contains many occurrences of val scattered throughout	The two-pointer approach correctly compacts the array, moving non-val elements to the beginning.
Large input array (e.g., exceeding available memory)	The in-place nature of the algorithm avoids excessive memory usage and scales efficiently.
Array contains negative numbers, zeros, and positive numbers, all mixed with val	The algorithm should treat each element the same regardless of its value (positive, negative, or zero).