Top Interview 150

Managing duplicates in sorted arrays is a classic problem that often appears in coding interviews. Today, we’ll tackle LeetCode 80: Remove Duplicates from Sorted Array II, where each unique element can appear at most twice. Here's a breakdown of the problem and an efficient JavaScript solution.

🚀 Problem Description

Given a sorted integer array nums, modify it in-place so that each unique element appears at most twice. Return the count of elements (k) in the modified array. The first k elements should store the valid elements in sorted order, while the rest can be ignored.

💡 Examples

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,_,_]

🧠 Key Insights

• Sorted input: Since the array is sorted, duplicates are grouped together.
• Two-pointer approach: Use one pointer to traverse the array and another to track the position of the next valid element.

🏆 JavaScript Solution
Here’s the implementation:

var removeDuplicates = function(nums) {
    let k = 0; // Pointer to track the position of valid elements

    for (let num of nums) {
        // Include the current number if it's the first two occurrences
        if (k < 2 || num !== nums[k - 2]) {
            nums[k] = num;
            k++;
        }
    }

    return k; // Return the count of valid elements
};

🔍 How It Works

1. Track valid elements:
   • If the pointer k is less than 2, include the element because all elements appear at least once.
   • If the current number is not the same as the element two places before (nums[k - 2]), include it.
2. Modify in-place:
   • Copy valid elements to the front of the array at position k.
3. Return k:
   • The first k elements of nums now store the valid result.

🔑 Complexity Analysis

Time Complexity: O(n), where n is the length of the array. Each element is processed once.
Space Complexity: O(1), as no additional space is used.

📋 Dry Run

Input: nums = [1,1,1,2,2,3]

✨ Pro Tips for Interviews

1. Understand constraints:
   • Ensure that modifications are in-place with O(1) space.
2. Clarify edge cases:
   • Empty array.
   • Arrays with all identical elements.

📚 Learn More

Check out the full explanation and code walkthrough on Dev.to:
👉 Remove Duplicates from Sorted Array - JavaScript Solution

Let me know your thoughts! How would you approach this problem? 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving