Remove Duplicates

Unit 3 Session 2 (Click for link to problem statements)

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Two-pointer technique

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• The function remove_dupes() should take a sorted array and remove duplicates in place, modifying the original array. Return the length of the modified array, where each element appears only once.

HAPPY CASE
Input: ["honey", "haycorns", "thistle", "extract of malt", "thistle"]
Expected Output: 4
Modified Array: ["honey", "haycorns", "thistle", "extract of malt", ...]

EDGE CASE
Input: ["honey", "haycorns", "extract of malt", "thistle"]
Expected Output: 4
Modified Array: ["honey", "haycorns", "extract of malt", "thistle"]

Input: []
Expected Output: 0
Modified Array: []

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers to track the position of unique elements in the sorted array. One pointer will iterate through the array to find unique elements, while the other will maintain the position for placing unique elements.

1. If the input array `items` is empty, return 0.
2. Initialize a pointer `i` to 0 to track the last unique element's position.
3. Loop through the array starting from index 1:
   a. If the current element is different from the last unique element (items[i]), increment `i` and update items[i] with the current element.
4. Return `i + 1` to get the length of the modified array

⚠️ Common Mistakes

• Not handling the empty array case.
• Incorrectly updating the index for unique elements.

I-mplement

Implement the code to solve the algorithm.

def remove_dupes(items):
    if not items:
        return 0
    
    i = 0  # Pointer for the position of the last unique element
    
    for j in range(1, len(items)):
        if items[j] != items[i]:
            i += 1
            items[i] = items[j]
    
    return i + 1