Problem 32 - Remove Duplicates from Sorted Array

Explore our archive for previous posts.

Problem 31 - Sort Characters By Frequency

Problem 30 - Merge Intervals

Ethical Dilemmas in Coding Interviews: Should You Reveal Prior Knowledge?

What's the best programming language for coding interviews?

Question

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. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.

• Return k.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 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 k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

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

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

• nums is sorted in non-decreasing order.

Approach

The approach involves iterating through the sorted array while maintaining a pointer to the last known unique element. Starting from the second element, at each step, we compare the current element with the element at the position of the last unique element. If they are different, it indicates a new unique element. We then place this new unique element in the array at the next position after the last known unique element, essentially overwriting any duplicate. By doing this, we modify the array in-place, ensuring that after the iteration, the array contains only unique elements up to the index of the last known unique element. The process continues until the end of the array. The returned count is essentially the position of the last unique element plus one.

Solution

Solve it here

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int uniqueCount = 1; // Count of unique elements
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[uniqueCount - 1]) {
                nums[uniqueCount] = nums[i];
                uniqueCount++;
            }
        }
        
        return uniqueCount;
    }
}

Time and space complexity

Time Complexity: The time complexity is O(n), where 'n' is the length of the input array. The algorithm iterates through the array once.

Space Complexity: The space complexity is O(1) as the solution modifies the input array in-place and uses a constant amount of additional space.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Want free mock interviews?

Simply share our newsletter with your friends, colleagues, or anyone you think would love our coding insights.

When your friends use your referral link to subscribe, you’ll receive special benefits.

• Get a free mock coding interview for 10 referrals

• Get a 1:1 coding Q&A session for 15 referrals

• Get a guest post opportunity for 25 referrals