SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

Given a sorted array, the task is to remove some duplicates in-place such that each unique element appears at most twice. Since the array is already sorted, duplicates will be adjacent. We need to ensure that we keep at most two occurrences of each element while maintaining the order of elements.

Approach

1. If the array length is less than or equal to 2, return the length as the array already satisfies the condition.
2. Initialize a variable k to 2, as the first two elements can always remain in the array.
3. Iterate through the array starting from the third element (index 2).
4. For each element, compare it with the element at position k - 2. If they are different, it means we can include this element in the result.
5. Assign the current element to the position k and increment k.
6. Continue this process until the end of the array.
7. Return k, which represents the number of elements in the modified array.

Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array. This is because we iterate through the array once.

Space Complexity

The space complexity is O(1) since we are modifying the array in place and not using any extra space that scales with the input size.

Code

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int count = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (nums[i] == nums[j] && j != i) {
                    ++count; }}
            if (count > 1) {
                nums.erase(nums.begin() + i + 1, nums.begin() + i + count);
                n -= count - 1; // Adjust the size of the array
            }count = 0;
        }
        return nums.size();
    }};

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count = 0
        n = len(nums)
        i = 0
        while i < n:
            for j in range(n):
                if nums[i] == nums[j] and j != i:
                    count += 1
            if count > 1:
                del nums[i + 1 : i + count]
                n -= count - 1  # Adjust the size of the array
            count = 0
            i += 1
        return len(nums)

Java

class Solution {
    public int removeDuplicates(int[] nums) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (nums[i] == nums[j] && j != i) {
                    count++;
                }}
            if (count > 1) {
               
                for (int k = i + 1; k + count - 1 < n; k++)
                {nums[k] = nums[k + count - 1];}
                n -= count - 1;
            }count = 0;
        }
        return n;
    }}

JavaScript

var removeDuplicates = function(nums) {
    let count = 0
    console.log(nums)
    for(let i = 0; i< nums.length; i++) {
        for(let j = 0; j<nums.length; j++){
            if(nums[i]==nums[j] && j !=i){
                count++
            }
        }
        if(count>1){
            nums.splice(i+1,count-1)
        }
        count = 0
    }
    return nums.length
};