Introduction

In this blog post, we will explore how to solve the LeetCode problem "80" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. Return k after placing the final result in the first k slots of nums. Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory. Custom Judge: The judge will test your solution with the following code: int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length int k = removeDuplicates(nums); // Calls your implementation assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; } If all assertions pass, then your solution will be accepted. Example 1: Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3,] Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 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,1,2,3,3] Output: 7, nums = [0,0,1,1,2,3,3,,_] Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores). Constraints: 1 <= nums.length <= 3 * 104 -104 <= nums[i] <= 104 nums is sorted in non-decreasing order.

Explanation

• We maintain a slow pointer k that points to the next available position in the modified array.
  • We iterate through the array with a fast pointer i. If the current element nums[i] is different from the element two positions before k (i.e., nums[k-2]), we copy nums[i] to nums[k] and increment k. This ensures that each unique element appears at most twice.
  • The key idea is to efficiently determine when an element should be copied based on its relationship to elements already in the result section.

• Runtime Complexity: O(n), Storage Complexity: O(1)

Code

    def removeDuplicates(nums):
    """
    Removes duplicates from a sorted array in-place, such that each unique element appears at most twice.

    Args:
        nums: A list of integers sorted in non-decreasing order.

    Returns:
        The new length of the array after removing duplicates.
    """
    n = len(nums)
    if n <= 2:
        return n

    k = 2  # Index to track the position to insert the next unique element

    for i in range(2, n):
        if nums[i] != nums[k - 2]:
            nums[k] = nums[i]
            k += 1

    return k