LeetCode - Remove Duplicates from Sorted Array Fastest Solution

Hello Code Recipian! Welcome back to another article on leetcode problem solutions. Today we will be solving leetcode problem no. 26, Remove Duplicates from Sorted Array.

Problem Statement: Remove Duplicates from Sorted Array

Given an integer array nums sorted in ascending order, move all single occurrences of elements in it to the beginning of the nums array in-place. The original order of the numbers in the final result array must be maintained for all the moved single occurrences.

If there are k unique elements in nums, your final output must be computed by taking into account the following considerations:

1. Modify nums array such that the first k elements in nums are all unique numbers and in the same order as in the original nums array.

2. Return k.

Example 1:

Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: The final array after moving the unique elements will be [2, 3, 6, 9, _, _, _].

Example 2:

Input: [2, 2, 2, 11]
Output: 2
Explanation: The first two elements after moving elements will be [2, 11, _, _].

Constraints:

• 1 <= nums.length <= 3 * 10^4

• -100 <= nums[i] <= 100

• nums is sorted in non-decreasing order.

Solution

The problem statement is pretty straightforward. We are asked to modify the given nums array by grouping every single occurrence of each element (one copy of each element) at the beginning of the array and in the same order as in the original array. We don't care about the position of the rest of the elements and they can be in any order. Also, we have to do this in-place, meaning we must arrive at the final result just by manipulating the nums array, we cannot use any extra space.

This problem can be solved using the two pointer technique. The idea is to make use of two pointers: uniqueIdx and i. uniqueIdx is used to keep track of the last unique element index in nums. i is used to iterate through the nums array. As and when we find a unique number we move it to the beginning of the nums array (pointed by uniqueIdx) and increment uniqueIdx.

Let's see how this works in detail.

Algorithm

Below is a step by step explanation for the working of the algorithm:

1. Initialization:

   As mentioned earlier, we will be using two pointer technique. Initialize two variables representing two pointers: uniqueIdx, i.

   1. uniqueIdx is used to keep track of the last unique number index in nums array. uniqueIdx is initially set to zero (points to 0th index of nums array).

   2. i is used to iterate through the nums array. i starts from the 1st index.

2. Modify nums array in-place:

   Using i, start iterating through the nums array from 2nd element. In each iteration, compare current element (ith element) with the last unique element (represented by uniqueIdx):

   1. If current element is equal to the last unique element, no operation, continue iterating.

   2. If current element is not equal to the last unique element, that means we have found a unique element (first occurrence for that element). Therefore, increment uniqueIdx and copy the current element to the uniqueIdx index.

3. Return result:

   Finally, return uniqueIdx + 1 as result (+1 because we need to return the total number of unique elements, but uniqueIdx is an index which starts from 0).

Simulation

Below is a pictorial depiction of the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

C Solution

Rust Solution

Complexity Analysis

Time Complexity

Time complexity of this algorithm is O(n) as we iterate through the entire array once to find the result. Apart from this we only perform constant time operations which have no impact on the overall time complexity.

Space Complexity

Space complexity is O(1) since we modify nums array in-place and do not use any extra space which is dependent on the input size.

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.