We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Duplicates from Sorted Array

Number: 26

Difficulty: Easy

Paid? No

Companies: Google, Meta, Amazon, Bloomberg, Microsoft, Infosys, Apple, Adobe, Qualcomm, Morgan Stanley, Zoho, Accenture, tcs, Yahoo, Capgemini, Yandex, Oracle, Akamai, EPAM Systems, Ozon, Wipro

Problem Description

Given a sorted integer array, remove the duplicates in-place such that each unique element appears only once. The relative order must be maintained. Return the number of unique elements (k) with the guarantee that the first k elements in the array contain the unique elements.

Key Insights

  • The array is sorted in non-decreasing order, meaning duplicate values appear consecutively.
  • Use a two-pointer approach:
    • One pointer to iterate through the array.
    • Another pointer to track the position to place the next unique element.
  • The solution modifies the array in place with O(1) extra space.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(1) since the modification is done in-place.

Solution

The approach uses two pointers. The first pointer (uniqueIndex) tracks the position for the next unique element, starting from index 1. The second pointer iterates over the array from index 1 to the end. Whenever a new element (different from the previous element) is encountered, it is placed at uniqueIndex, and uniqueIndex is incremented. Finally, uniqueIndex represents the count of unique elements and denotes how many elements are valid in the modified array.

Code Solutions

# Function to remove duplicates and return count of unique elements.
def removeDuplicates(nums):
    if not nums:
        return 0
    unique_index = 1  # Pointer for the next unique element.
    # Iterate over the array starting from the second element.
    for i in range(1, len(nums)):
        # If the current element is different from the previous.
        if nums[i] != nums[i - 1]:
            nums[unique_index] = nums[i]  # Place the unique element at the unique_index.
            unique_index += 1
    return unique_index

# Example usage:
# nums = [0,0,1,1,1,2,2,3,3,4]
# k = removeDuplicates(nums)
# print(k, nums[:k])
← Back to All Questions