algoadvance

The problem is to remove all instances of a specific value in a given array in-place and return the new length of the array. The order of elements can be changed, and the elements beyond the new length do not matter.

Example:

Input: nums = [3, 2, 2, 3], val = 3
Output: 2, nums = [2, 2, _, _]

Note: The underscore (_) represents irrelevant values beyond the desired new length.

Clarifying Questions

  1. Is it guaranteed that the array contains the value to be removed?
    • Not necessarily. The array can have zero or more instances of the value.
  2. What should be the return type?
    • An integer representing the new length of the array.
  3. Can we use extra space?
    • The problem specifies that the removal should be done in-place, so we should not use extra space.

Strategy

  1. Initialize a variable i as the index where the next non-val element should be placed.
  2. Iterate over each element in the array using a for-loop.
    • If the current element is not equal to val, place it at the index i and increment i.
  3. The final value of i will be the new length of the array.
  4. Modify the array in-place to reflect this change (although the problem does not strictly require this, it ensures correctness).

Code

Here’s the Python implementation based on the strategy:

def removeElement(nums, val):
    i = 0
    for j in range(len(nums)):
        if nums[j] != val:
            nums[i] = nums[j]
            i += 1
    return i

# Example usage:
nums = [3, 2, 2, 3]
val = 3
new_length = removeElement(nums, val)
print("New length:", new_length)  # Output: 2
print("Modified array:", nums[:new_length])  # Output: [2, 2]

Time Complexity

Try our interview co-pilot at AlgoAdvance.com