We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Element

Number: 27

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft, Bloomberg, Meta, Uber, Apple, Adobe, Yahoo, Yandex

Problem Description

Given an integer array and a value, remove all occurrences of that value in-place so that the first k elements of the array are the remaining elements that are not equal to the given value. Return k, the count of these elements. The order of the elements can be changed and it does not matter what you leave beyond the first k elements.

Key Insights

  • Use a two-pointer approach: one pointer iterates through the array while the other keeps track of the position for the next valid element.
  • Modify the array in-place, which ensures constant extra space usage.
  • The order of elements is not preserved, which allows swapping elements or simply overwriting the unwanted ones.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

The idea is to maintain a write pointer that indicates where the next valid element (not equal to val) should be placed. Iterate through the array with a read pointer. For every element that is not equal to val, write it to the position indicated by the write pointer and increment the write pointer. Once the loop completes, the write pointer will represent the number of valid elements (k) and the array's first k elements will be the desired result.

Code Solutions

def removeElement(nums, val):
    # Pointer for the position of the next valid element
    valid_index = 0
    # Iterate through each element in the array
    for num in nums:
        # If the current element is not equal to val, it is valid
        if num != val:
            # Write it to the position indicated by valid_index
            nums[valid_index] = num
            # Move the valid_index to the next position
            valid_index += 1
    # Return the count of valid elements
    return valid_index

# Example usage
nums = [3,2,2,3]
val = 3
k = removeElement(nums, val)
print(k, nums[:k])
← Back to All Questions