How to remove the key and return the new length of the array without using extra space ?

How to remove the key and return the new length of the array without using extra space ?

Two-pointer method

Muthya Varshith Vankamamidi's photo
Muthya Varshith Vankamamidi
·Aug 19, 2021·

3 min read

Today we shall solve another Two-Pointer problem where you are given an unsorted array of numbers and a target ‘key’, remove all instances of ‘key’ in-place and return the new length of the array.

This is similar to the last problem we solved on this blog on day one !. Try it on your own for some time before you look into the solution. Just think outside the box before writing the code. The perfect way to think of a solution is thinking , what would be an easy way for you to explain to a 5-Year-old how to do it. I think this is the trick for effortlessly writing a code for most of the problems .

So let's get started ... !

Problem 1: Given an unsorted array of numbers and a target ‘key’, remove all instances of ‘key’ in-place and return the new length of the array.

Test cases !

Example 1:

Input: [3, 2, 3, 6, 3, 10, 9, 3], Key=3
Output: 4
Explanation: The first four elements after removing every 'Key' will be [2, 6, 10, 9].

Example 2:

Input: [2, 11, 2, 2, 1], Key=2
Output: 2
Explanation: The first two elements after removing every 'Key' will be [11, 1].

So what do you think ! how should one solve this problem ?

As it is clear we are using two pointers to solve this. So for this case, the objective is to remove the key which is a duplicate element in the given array say arr. If you see in the first case the given key is 3. And at the 0th index, we have the 3 ! So in this case, we have to replace it with the next non-key element. that in this case, is '2'.

  • So what we can do is take a pointer and point it to the 0th index value of an array. Say index_arr
  • Now take another pointer that increments for every iteration. Say next
  • Once we have these two pointers. We can make the next iterate and find the elements that are not equal to the KEY.
  • And then replace the found element of index arr[next] with arr[index_arr]
  • And then increment the index_arr by one
  • And return the index_arr which is the new length of the substring !

So let's see the code !

def remove_duplicates_given(arr, key):
    key_element = 0

    for index in range(len(arr)):
        if arr[index] != key:
            arr[key_element] = arr[index]
            key_element += 1
    return key_element


print(remove_duplicates_given([3, 2, 3, 6, 3, 10, 9, 3], 3))
print(remove_duplicates_given([2, 11, 2, 2, 1], 2))

which give us the desired result

4
2

See you tomorrow with a new and interesting problem 😊😊🙌👍

Did you find this article valuable?

Support Muthya Varshith Vankamamidi by becoming a sponsor. Any amount is appreciated!

See recent sponsors Learn more about Hashnode Sponsors
 
Share this