Practice/Amazon/Leetcode 80. Remove Duplicates from Sorted Array II

Leetcode 80. Remove Duplicates from Sorted Array II

CodingOptional

Problem

You are given an integer array that is sorted in non-decreasing order. Your task is to modify the array in-place so that each unique number appears at most twice. After the modification, return the number of elements that should be kept.

The elements you keep should maintain their relative order, and they should occupy the first k positions of the array, where k is the number you return. The values in positions beyond k do not matter.

Requirements

1. Modify the array in-place without creating a new array
2. Each distinct element should appear at most twice in the final result
3. Return the count of valid elements (length k)
4. The first k elements of the modified array should contain the answer
5. Elements must maintain their original relative order
6. You must use O(1) extra memory (constant space)

Constraints

• 1 ≤ nums.length ≤ 30,000
• -10,000 ≤ nums[i] ≤ 10,000
• The array is sorted in non-decreasing order
• Time complexity should be O(n)
• Space complexity should be O(1)

Examples

Example 1:

Input: nums = [1,1,1,2,2,3] Output: 5 Modified array: [1,1,2,2,3,...] Explanation: The first five elements become [1,1,2,2,3]. The number 1 appears twice, 2 appears twice, and 3 appears once.

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3] Output: 7 Modified array: [0,0,1,1,2,3,3,...] Explanation: The first seven elements become [0,0,1,1,2,3,3]. Each distinct value appears at most twice.

Example 3:

Input: nums = [1,1,1,1] Output: 2 Modified array: [1,1,...] Explanation: Only two 1's are kept.