Remove Element and Move Zeros in Array: using two pointers

These are simple questions asked in Facebook interview.

Part I

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

My Solution

The idea is to keep pointer to position index and store here if we found element that is not zero. The time complexity is O(n).

def remove(nums):
  """
  :type nums: List[int]
  :type val: int
  :rtype: int
  """
  if not nums:
    return 0
  i = 0
  for n in nums:
    if n != val:
      nums[i] = n
      i += 1
  return i
  

Part II

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

My Solution

The idea is similar to the first one. Keep a pointer to indicate the position of array to store to. The time complexity is O(n).

def move_zero(nums):
  i = 0
  for n in nums:
    if n != 0:
      nums[i] = n
      i += 1
  while i<len(nums):
    nums[i] = 0
    i += 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s