algoadvance

Given a sorted array nums, remove the duplicates in-place such that duplicates are allowed at most twice and return 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.

Example 1:

Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3,_]

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3] Output: 7, nums = [0,0,1,1,2,3,3,_,_]

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

Clarifying Questions

1. Is the input array always non-empty?
   • Yes, based on the constraints (1 <= nums.length).
2. Can the values in the array be negative?
   • Yes, the values range from -10^4 to 10^4.
3. Can I use Python’s list slicing?
   • Yes, but remember that you can’t allocate extra space for another array; modifications need to be done in-place.

Strategy

We’ll use a two-pointer approach to efficiently manage the in-place updates:

1. Initialization:
   • Create a pointer insert_pos starting at index 0.
   • Loop through the list using another pointer.
2. Traversal:
   • Traverse the nums array.
   • For each element, check if it is allowed to be inserted based on the previous element at insert_pos-2.
3. Insertion Check:
   • If insert_pos is less than 2, directly insert the element as we need at least two items to compare.
   • Otherwise, check if the current element is the same as the element at insert_pos-2.
     • If not, insert the current element at insert_pos and increment insert_pos.
4. End Result:
   • After the loop, insert_pos will be the new length of the modified array.

Code

def removeDuplicates(nums):
    if not nums:
        return 0

    insert_pos = 0

    for num in nums:
        if insert_pos < 2 or num != nums[insert_pos - 2]:
            nums[insert_pos] = num
            insert_pos += 1

    return insert_pos

Explanation

1. Edge Case Handling:
   • If the input list nums is empty, immediately return 0.
2. Two-Pointer Mechanism:
   • insert_pos serves as the place to insert the next valid element for the modified array.
   • Traverse each element in nums:
     • If insert_pos is less than 2: Directly insert the element, as there are fewer than 2 elements to compare.
     • If the current element num is not equal to the element located at insert_pos - 2, insert num at position insert_pos and increment insert_pos.

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the input array nums. This is because we iterate through each element exactly once.
• Space Complexity: O(1), as we do not use any extra space proportional to the input size; the modifications are done in-place.

This solution leverages the sorted property of the array and uses constant space for efficient in-place modifications.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?