Remove Duplicates from Sorted Array – Solutions

May 26, 2024

Table of Contents

Description:

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.

Examples:

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).

Solution in Python:

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # If the list is empty, return 0 as there are no unique elements
        if not nums:
            return 0

        # Initialize the index to place the next unique element
        # Since the first element is always unique, we start from the second element
        unique_index = 1

        # Iterate through the list starting from the second element
        for i in range(1, len(nums)):
            # If the current element is different from the previous element, it's unique
            if nums[i] != nums[i - 1]:
                # Place the unique element at the current unique_index
                nums[unique_index] = nums[i]
                # Increment the unique_index
                unique_index += 1

        # The unique_index now represents the number of unique elements
        return unique_index

# Example usage:
# nums = [1, 1, 2]
# solution = Solution()
# k = solution.removeDuplicates(nums)
# print(k)  # Output: 2
# print(nums[:k])  # Output: [1, 2]

# nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
# solution = Solution()
# k = solution.removeDuplicates(nums)
# print(k)  # Output: 5
# print(nums[:k])  # Output: [0, 1, 2, 3, 4]

Explanation:

Initial Check:
- If the input list nums is empty, return 0 since there are no elements to process.
Initialization:
- We initialize unique_index to 1 because the first element is always unique and will be placed in the first position.
Iterating through the List:
- We start iterating from the second element (index 1) to the end of the list.
- For each element, we check if it is different from the previous element. If it is, this means it’s a unique element.
Placing Unique Elements:
- When we find a unique element, we place it at the position indicated by unique_index.
- After placing the unique element, we increment unique_index.
Returning the Result:
- After finishing the iteration, unique_index will indicate the number of unique elements in the list.
- This is the value we return, and the first unique_index elements of nums will contain the unique elements in their original order.

Solution in Javascript:

JavaScript

/**

@param {number[]} nums

@return {number}
*/
var removeDuplicates = function(nums) {
// If the list is empty, return 0 as there are no unique elements
if (nums.length === 0) {
return 0;
}

// Initialize the index to place the next unique element
// Since the first element is always unique, we start from the second element
let uniqueIndex = 1;

// Iterate through the list starting from the second element
for (let i = 1; i < nums.length; i++) {
// If the current element is different from the previous element, it's unique
if (nums[i] !== nums[i - 1]) {
// Place the unique element at the current uniqueIndex
nums[uniqueIndex] = nums[i];
// Increment the uniqueIndex
uniqueIndex++;
}
}

// The uniqueIndex now represents the number of unique elements
return uniqueIndex;
};

// Example usage:
let nums1 = [1, 1, 2];
let k1 = removeDuplicates(nums1);
console.log(k1); // Output: 2
console.log(nums1.slice(0, k1)); // Output: [1, 2]

let nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
let k2 = removeDuplicates(nums2);
console.log(k2); // Output: 5
console.log(nums2.slice(0, k2)); // Output: [0, 1, 2, 3, 4]

Solution in Java:

Java

class Solution {
    public int removeDuplicates(int[] nums) {
        // If the list is empty, return 0 as there are no unique elements
        if (nums.length == 0) {
            return 0;
        }

        // Initialize the index to place the next unique element
        // Since the first element is always unique, we start from the second element
        int uniqueIndex = 1;

        // Iterate through the list starting from the second element
        for (int i = 1; i < nums.length; i++) {
            // If the current element is different from the previous element, it's unique
            if (nums[i] != nums[i - 1]) {
                // Place the unique element at the current uniqueIndex
                nums[uniqueIndex] = nums[i];
                // Increment the uniqueIndex
                uniqueIndex++;
            }
        }

        // The uniqueIndex now represents the number of unique elements
        return uniqueIndex;
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] nums1 = {1, 1, 2};
        int k1 = solution.removeDuplicates(nums1);
        System.out.println(k1);  // Output: 2
        for (int i = 0; i < k1; i++) {
            System.out.print(nums1[i] + " ");  // Output: 1 2
        }
        System.out.println();

        int[] nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int k2 = solution.removeDuplicates(nums2);
        System.out.println(k2);  // Output: 5
        for (int i = 0; i < k2; i++) {
            System.out.print(nums2[i] + " ");  // Output: 0 1 2 3 4
        }
        System.out.println();
    }
}

Solution in C#:

C#

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        // If the array is empty, return 0 as there are no unique elements
        if (nums.Length == 0) {
            return 0;
        }

        // Initialize the index to place the next unique element
        // Since the first element is always unique, we start from the second element
        int uniqueIndex = 1;

        // Iterate through the array starting from the second element
        for (int i = 1; i < nums.Length; i++) {
            // If the current element is different from the previous element, it's unique
            if (nums[i] != nums[i - 1]) {
                // Place the unique element at the current uniqueIndex
                nums[uniqueIndex] = nums[i];
                // Increment the uniqueIndex
                uniqueIndex++;
            }
        }

        // The uniqueIndex now represents the number of unique elements
        return uniqueIndex;
    }
}

Remove Duplicates from Sorted Array – Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

388. Longest Absolute File Path – Leetcode Solutions

44. Wildcard Matching – Leetcode Solutions

53. Maximum Subarray – Leetcode Solutions

How to Add to a List in Python

350. Intersection of Two Arrays II – Leetcode Solutions

106. Construct Binary Tree from Inorder and Postorder Traversal – Leetcode Solutions

199. Binary Tree Right Side View – Leetcode Solutions

Remove Duplicates from Sorted Array – Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular