algoadvance

Leetcode 80. Remove Duplicates from Sorted Array II

Problem Statement

You are given a sorted array nums. Remove the duplicates in such a way that each element appears 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.

For example:

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 the new length of 7, and the first seven elements of nums should be [0,0,1,1,2,3,3]. It does not matter what you leave beyond the returned length.

Clarifying Questions

  1. Can the input array be empty?
    • Yes, if the array is empty, simply return 0.
  2. What types of elements are in the array?
    • The elements are integers.
  3. Is the input already sorted?
    • Yes, the input array is always sorted.
  4. Should the elements beyond the returned length be unmodified?
    • The elements beyond the returned length do not matter.

Strategy

To solve this problem, we’ll use two pointers:

  1. i to traverse the array.
  2. x to store the position where the next non-duplicate element should be placed.

We’ll keep track of the count of occurrences for each element:

Code

Here’s the C++ implementation of the above strategy:

#include <vector>
#include <iostream>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int x = 1;  // Place to insert the next element.
    int count = 1;  // Initialize count of the current number.
    
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] == nums[i - 1]) {
            // If we have encountered a duplicate
            if (count < 2) {
                nums[x++] = nums[i];
            }
            count++;
        } else {
            // Encountered a new number
            nums[x++] = nums[i];
            count = 1;
        }
    }
    
    return x;
}

// Example usage
int main() {
    vector<int> nums = {0,0,1,1,1,1,2,3,3};
    int newLength = removeDuplicates(nums);
    cout << "New length: " << newLength << endl;
    cout << "Modified array: ";
    for (int i = 0; i < newLength; ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the input array. This is because we traverse the array only once.

The space complexity is (O(1)) because we are modifying the input array in-place and not using any extra space except a few variables for pointers and counters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI