Leetcode: Remove Duplicates from Sorted Array

Leetcode — Remove Duplicates from Sorted Array

Leetcode : Remove Duplicates from Sorted Array is an easy question on Leetcode. I will walk through brute-force and optimal solutions in Java and Kotlin. Remove Duplicates from Sorted Array - LeetCode

Problem Statement

Examples

Constraints

Gathering Requirements

1. Our input is a sorted array of integers that will at least have one element (according to the constraints). Since it is sorted, we can possibly use a two-pointers approach to solve this.

2. Our output is the number of unique elements in the array.

3. We are not allowed to allocate extra space by using another array to solve this.

4. We need an integer variable to keep count of the number of unique elements ( int count = 0 ).

We can solve this problem in numerous ways. I will show you a brute force and optimal approach.

Brute Force Approach

One brute force approach would be to use extra space ( which the problem statement doesn’t recommend) (int[] duplicate = new int[nums.length]).

1. Create another array of size nums.length.

2. Since our constraints tells us we will always have at least one element in the array we can assign the first element in the nums array to the first element in the duplicate array.

3. Loop through the nums array starting at index 1.

4. Check if the current and previous integers are the same. If they are not the same increment our count variable and add the current integer to our duplicate array.

5. We will loop through the nums array a second time and assign replace every element in the nums array with every element in the duplicate array.

Check out the brute force solution below: {% gist https://gist.github.com/cmcoffeedev/9490fc7e95888b40f0b590a4f7cfb0b0.js %}

Optimal Solution

An optimal solution would use the suggestion not to use an extra array to save space. This is a two-pointer approach that uses a slow-fast pointer approach. The left pointer will stay the same until we find an element that is not a duplicate. We will then set the next element after nums[count] to nums[right].

1. Create an integer variable, count, which will be our left pointer and also keep a count of non-duplicate values

2. Loop through the array starting at index 1 (the right pointer starts at index 1, left pointer starts at index 0)

3. If the left and right values are not equal, we have found a duplicate and can replace the next index after count with the value of the right pointer.

4. Increment count

5. nums[count] = right

6. Return count + 1. We need to add one because the “grader” for this problem loops through the array using count as the length to count up to {% gist https://gist.github.com/cmcoffeedev/cff19d96468de00476e19078f7a70505.js %}

I will also show the Kotlin optimal solution below {% gist https://gist.github.com/cmcoffeedev/f47c9411798573d80b5483aa5320febf.js %}