Remove Duplicates from Sorted Array in Java

Good day. Hope you are doing well. Seems like many companies, businesses and schools are starting to plan on how to conduct business after the COVID-19 pandemic in the USA. It seems like we are getting closer to be able to return to a new normal. I believe that use of masks in public will be required until we achieve herd immunity in different locations. Hope the same is happening in your neck of the woods.

Today I decided to tackle LeetCode problem 26 Remove Duplicates from Sorted Array. This is part of a set of problems in the Explore tab in the LeetCode main page.

Given a sorted array nums, 
remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, 
you must do this by modifying the input array in-place with O(1) extra memory.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, 
which means a modification to the input array will be known to the caller as well.

Constraints:

o 0 <= nums.length <= 3 * 104
o -104 <= nums[i] <= 104
o nums is sorted in ascending order.

The requirement is very well explained. As you can see it explains what the function juts needs to return the size of the updated array. The caller can see the results in the array. They just need to be sure that the new array is of the proper length. Of course the length needs to match the number of distinct elements and they must be in ascending order.

I will solve the problem using the Java programming language and the VSCode IDE on a Windows 10 machine. It is simpler to solve it directly on the on-line IDE provided by LeetCode. You will not require writing a test scaffold. In my case I will develop a simple test scaffold to collect the input data, call the method of interest and display the result.

LeetCode provides two test cases.

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation:
Your function should return length = 2, 
with the first two elements of nums being 1 and 2 respectively. 
It doesn't matter what you leave beyond the returned length.


1,1,2
main <<<   nums: [1, 1, 2]
main <<< output: 2
main <<<   nums: [1, 1, 2]
main <<< output: 2


Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation:
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.


0,0,1,1,1,2,2,3,3,4
main <<<   nums: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
main <<< output: 5
main <<<   nums: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
main <<< output: 5

As you can see from the screen capture, the values for the array are ingested. The int[] nums array is initialized with the data. The nums array is displayed to make sure all is well so far.

We then call the method in question and display the result.

In our case we have a second version which is called with the same array and the output is displayed. On both cases the outputs match and you can display the state of the final array to verify the order of the values and the length.

class Solution {
    public int removeDuplicates(int[] nums) {
        
    }
}

The signature for the method of interest is provided. We just need to pass the nums int[] and the result should be returned.

    /**
     * Test scaffold.
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
     
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read int[] array ****
        int[] nums = Arrays.stream(br.readLine().trim().split(","))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        // **** close buffered reader ****
        br.close();
        
        // ????? ????
        System.out.println("main <<<   nums: " + Arrays.toString(nums));
        
        // **** make a copy of nums ****
        int[] tmp = nums.clone();

        // **** invoke method and display results ****
        System.out.println("main <<< output: " + removeDuplicates1(nums));

        // **** restore nums ****
        nums = tmp.clone();

        // ????? ????
        System.out.println("main <<<   nums: " + Arrays.toString(nums));      

        // **** invoke method and display results ****
        System.out.println("main <<< output: " + removeDuplicates(nums));
    }

Our test code is quite dimple. We read the input data and populate the nums[] array.

Since we are going to use the same array on the second implementation we will make a copy of the array before we call the first implementation.

We call the method of interest and display the output.

We then restore the nums array and make the call to the second approach. The result is also displayed.

    /**
     * Given a sorted array nums, 
     * remove the duplicates in-place such that each element appears only once 
     * and returns the new length.
     * 
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 40.9 MB, less than 43.42% of Java online submissions.
     */
    static int removeDuplicates1(int[] nums) {
       
        // **** sanity checks ****
        if (nums == null || nums.length <= 1)
            return nums.length;
        
        // **** initialization ****
        int i = 0;
        int j = 1;

        // **** traverse array swapping elements ****
        while (i < (nums.length - 1) && j < nums.length) {

            // **** compare elements ****
            for ( ; j < nums.length; j++) {

                // **** swap elements (if needed) ****
                if (nums[i] < nums[j]) {

                    // **** swap elements ****
                    // swap(nums, i + 1, j);
                    int tmp = nums[i + 1];
                    nums[i + 1] = nums[j];
                    nums[j] = tmp;

                    // **** increment index ****
                    i++;
                }
            }
        }

        // **** return new length ****
        return i + 1;
    }

The implementation has two loops. I decided to swap elements as we made progress traversing the nums array. When we encounter an element that is larger than the last element in our updated array, we swap values and update indices.

When done we return the size of the new sorted array without duplicates. As you can see to gain some execution time I swapped the swap() method for in-line code. That gave us the values in the comment section of this method. Not bad.

    /**
     * Auxiliary method to swap values in array.
     * Switched to in-line code for performance.
     * 
     * !!! NO LONGER USED !!!
     */
    static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

This is the swap() auxiliary method. We do not use it. I just left it as a reference.

    /**
     * Given a sorted array nums, 
     * remove the duplicates in-place such that each element appears only once 
     * and returns the new length.
     * 
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 41.2 MB, less than 13.42% of Java online submissions.
     */
    static int removeDuplicates(int[] nums) {

        // **** sanity checks ****
        if (nums == null || nums.length <= 1)
            return nums.length;

        // **** initialization ****
        int i = 1;

        // **** traverse nums array O(n) ****
        for (int j = 0; j < nums.length - 1; j++) {

            // **** update nums[i] and i (if needed) ****
            if (nums[j] != nums[j + 1])
                nums[i++] = nums[j + 1];

            // ???? ????
            // System.out.println("<<< j: " + j + " nums: " + Arrays.toString(nums));
        }

        // **** return new length ****
        return i;
    }

This is the second implementation of the method of interest. Note that the loop is simpler. The idea is to traverse the nums array and just move any larger value as the next element. Recall that the values are in ascending order. Note that the index ‘I’ is incremented when the previous value is overwritten.

When all is said and done the value of the index is return since it reflects the length of the updated array.

The execution statistics are included as part of the comment section in this method. We saved some memory and the execution time was the same.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all subscribers to this blog!!!

Regards;

John

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.