old_contents: # Time:  O(n)
  # Space: O(1)
  #
  # Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
  #
  # Do not allocate extra space for another array, you must do this in place with constant memory.
  #
  # For example,
  # Given input array A = [1,1,2],
  #
  # Your function should return length = 2, and A is now [1,2].
  #
  
  class Solution:
      # @param a list of integers
      # @return an integer
      def removeDuplicates(self, A):
          if not A:
              return 0
  
          last, i = 0, 1
          while i < len(A):
              if A[last] != A[i]:
                  last += 1
                  A[last] = A[i]
              i += 1
  
          return last + 1
  
  if __name__ == "__main__":
      print Solution().removeDuplicates([1, 1, 2])
  
new_contents: # Time:  O(n)
  # Space: O(1)
  #
  # Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
  #
  # Do not allocate extra space for another array, you must do this in place with constant memory.
  #
  # For example,
  # Given input array A = [1,1,2],
  #
  # Your function should return length = 2, and A is now [1,2].
  #
  
  
  class Solution(object):
      # @param a list of integers
      # @return an integer
      def removeDuplicates(self, A):
          if not A:
              return 0
  
          last = 0
          for i in xrange(len(A)):
              if A[last] != A[i]:
                  last += 1
                  A[last] = A[i]
          return last + 1
  
subject: Update remove-duplicates-from-sorted-array.py