Skip to main content

Arrays Hands-On: Warming Up

2 pointers - 1

In the previous section, you must've seen that we were mostly traversing through the array and doing some if-else during each iteration. Essentially, we just had 1 pointer (namely, i). That was just the beginning xD

In this section, the problems will be such that, to solve them efficiently, there will be an involvement of 2 pointers in some way or another.

Remove Duplicates from Sorted Array

In this problem, we'll be given a sorted array (e.g. input = [1, 3, 3, 5, 10, 10, 10, 15, 18]), and our target is to remove the duplicates from the given array (e.g. resultant = [1, 3, 5, 10, 15, 18]) in-place.

If you don't remember what in-place means, read this again.

How to solve?

The first approach that comes to my mind is a brute force one that also uses extra space. I won't explain it in a lot of depth, will just give a brief overview and the code for it. If you feel the need for a detailed one, please use the feedback form, I'll add it then.

The Approach

As given in the problem, the input array is already sorted. What if we create an auxiliary array, only add the first occurance of each number in that array?

If you think carefully, the auxiliary array will contain unique numbers, and that also, in a sorted order, because the original array was sorted.

Now, we'll just copy the elements from the auxiliary array to the original array, and we're done.

Implementation 
int removeDuplicates(vector<int>& nums) {
	// create an aux array (initially empty)
	vector<int> aux;

	// put all unique elements to the aux array
	for(int i = 0; i < nums.size(); ++i) {
		bool already_added = false;
		for(int j = 0; j < i; ++j) {
			// if nums[i] is found on the left, then it's already added to aux.
			if(nums[j] == nums[i]) {
				already_added = true;
				break;
			}
		}
		if(!already_added)
			aux.push_back(nums[i]);
	}

	// put the elements of aux back to the 'nums' array
	for(int i = 0; i < aux.size(); ++i)
		nums[i] = aux[i];

	return aux.size();
}
Time and Space Complexity
  • Time Complexity: O(N2) - Bad
  • Space Complexity: O(N) - Bad

Let's improve the time complexity

In the earlier implementation, we were taking O(N) time for each element to check if the current element has already been added to the auxiliary array or not. The hint is to utilise the fact that the given array is sorted. Now, think a bit about it and then only read the approach below.

The Approach Since we've established that the array is sorted, try to observe that there's a better way to figure out if an element has already been added to the auxiliary array or not.
The Way

The way is to simply check if the last element of the auxiliary array is equal to the current element or not.

If the last element is equal of the aux array is equal to the current element of num array, that means it has already been added, otherwise if the aux array is empty, or the elements are not equal, that means it's the first occurance of the current element.

Implementation 
int removeDuplicates(vector<int>& nums) {
	// create an aux array (initially empty)
	vector<int> aux;

	// put all unique elements to the aux array
	for(int num : nums)
		if(aux.empty() or num != aux.back())
			aux.push_back(num);

	// put the elements of aux back to the 'nums' array
	for(int i = 0; i < aux.size(); ++i)
		nums[i] = aux[i];

	return aux.size();
}
Time and Space Complexity
  • Time Complexity: O(N2) - Bad
  • Space Complexity: O(1) - Good

Let's improve the space complexity as well

The catch here is that instead of storing the elements to an auxiliary array and then copying them to the original array, we need to directly place the different unique elements to appropriate places in the original array.

The Approach

We know that the first element is going to remain there only. (ie. index = 0). Now, as soon as we get a new element that's not equal to the first element, it'll go to the next available place, i.e. index = 1 in this case, and this process will go on.

We'll simply let the 0th element as it is, and start our process from index 1. We'll have a variable unique_i, initially equal to 1, and this variable basically represents that where should the next unique element go to, in the final array.

Now, we'll iterate over the array starting from i = 1, and do the following:

  1. If nums[i] == nums[i-1], then do nothing and continue, because it means that the current element isn't a new unique element.
  2. Otherwise, we'll do nums[unique_i] = nums[i]. Here, we're basically placing the current element to the index unique_i.
  3. Just after doing nums[unique_i] = nums[i], also increment the value of unique_i by 1, because the next unique element will go to 1 place towards the right now.

Implementation 
int removeDuplicates(vector<int>& nums) {
	// the 0th element is going to remain there only, so let's start with 1.
	int unique_i = 1;

	for(int i = 1;  i < nums.size(); ++i) {
		if(nums[i] != nums[i - 1]) {
			nums[unique_i] = nums[i];
			unique_i++;
		}
	}

	return unique_i;
}
Time and Space Complexity
  • Time Complexity: O(N) - Good
  • Space Complexity: O(1) - Good