Removing Duplicates from Sorted Array

This problem will help you to master Data Structure & Algorithms and improve your coding skills. Just like any other skills, coding interview is one area where you can greatly improve with consistency and practice. You must always remember that there is no defined answer to interview questions. Most of the classic interview questions have multiple solution approaches.

Therefore, to be able to master the coding interview successfully, make sure you practice more than once. For the best practice result, we strongly advise you to go through this list at least a second and third times.

By the second attempt, you may discover some new tricks or new methods. By the third time, you should find that your code appear to be more concise compared to your first attempt. Never look for answers and memorizing it. This will never help you in the long run. Always remember to solve a problem yourself without any reference to answers.

Today we will focus on arrays.

Arrays Coding Question:

a. Removing Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array using O(1) extra memory.

How to Go About it:

Using the O(1) extra memory and for this to be possible, you will first need to:

  1. Create an auxiliary array temp [ ] to store the unique elements in the array provided
  2. Then you will need to traverse through the input array while copying the unique elements one by one from the nums [ ] to the temp [ ]
  3. While doing step two, remember to keep track of the count of the unique elements and let the count be j
  4. Lastly, copy all the counted j elements from the temp [ ] to the nums [ ] and then return the unique elements as j

General Solution Explanation:

Sorting means putting elements in an ordered sequence. Ordered sequence is any sequence that has an order corresponding to elements, like numeric or alphabetical, ascending or descending.

An array is a collection of items stored at contiguous memory locations. Arrays are used to store multiple values in one single variable, store multiple items of the same type together. This makes it easier to calculate the position of each element. For instance, the memory location of the first element of the array is usually denoted by the name of the array.

The NumPy ndarray object has a function called sort(), that will sort a specified array. Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.

For instance;

  1. numpy.sort() : This function returns a sorted copy of an array. On the other hand,
  2. numpy.argsort() : This function returns the indices that would sort an array.

NumPy or Numeric Python is a package for computation on homogeneous n-dimensional arrays. In NumPy dimensions are called as axes. Example 2D, 3D matrix.

Why NumPy Can Also Be Used to Solve this Problem

A question arises that why do we need NumPy when python lists are already there. The answer to it is we cannot perform operations on all the elements of two list directly. For example we cannot multiply two lists directly we will have to do it element wise. This is where the role of NumPy comes into play.

Final Code is:

import numpy as np

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        a = np.array([0,0,1,1,1,2,2,3,3,4])
        print("original unsorted array is:\n", a)
        

class Solution(object):
    def removeDuplicates(self, nums):
        
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums) == 0:
            return 0
        
        length = 1
        previous = nums[0]
        index = 1
        for i in range(1, len(nums)):
            if nums [i] != previous:
                length += 1
                previous = nums[i]
                nums[index] = nums[i]
                index += 1
        return length
    
input_nums = [0,0,1,1,1,2,2,3,3,4]
output_nums = Solution()
print(output_nums.removeDuplicates(input_nums))

If you have any question or comments, do not hesitate to ask us.

Quote: The moon looks upon many night flowers; the night flowers see but one moon. – Jean Ingelow

Advertisement