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 II

Number: 80

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Meta, Bloomberg, Microsoft, TikTok, Accolite, tcs, Adobe, Apple, Zoho

Problem Description

Given a sorted integer array, modify it in-place such that each unique element appears at most twice, while preserving the relative order of the elements. After processing, return the new length k of the array, where the first k elements contain the final result. No extra space for another array can be allocated.

Key Insights

  • The array is already sorted, which allows for efficient duplicate detection.
  • Use a two-pointer technique: one pointer (slow) to track the position for the next valid element and another pointer (fast) to iterate through the array.
  • Since each element is allowed up to two occurrences, compare the current element with the element two positions before in the processed section.
  • In-place modifications ensure O(1) extra space usage.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, as we traverse the array once.
Space Complexity: O(1), because the modifications are done in-place with constant extra space.

Solution

We use two pointers to solve the problem in one pass. The slow pointer holds the index where the next valid element should be placed. The fast pointer scans each element in the array.

  • For indices less than 2, we simply copy them, since they are automatically valid.
  • For each subsequent element at index i, we compare it with the element at index (slow - 2). If they are not equal, it means adding the current element will not exceed the allowed two occurrences.
  • We then update the array in-place by writing the element at the slow pointer and incrementing the slow pointer.
  • Finally, all valid elements are stored in the first part of the array, and the slow pointer's value represents the new length.

Code Solutions

# Python solution for removing duplicates allowing at most two occurrences.
def removeDuplicates(nums):
    # slow pointer for the placement of the element
    slow = 0
    # iterate through each element using fast pointer
    for num in nums:
        # if less than two elements have been placed or the current number
        # is greater than the element at slow-2 (which ensures it is allowed)
        if slow < 2 or num > nums[slow - 2]:
            nums[slow] = num  # place the current number at the slow pointer index
            slow += 1        # increment the slow pointer
    return slow  # slow is the length of the valid array

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