Remove Duplicates

Edit PagePage History

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: Lists, Two-pointer technique

U-nderstand

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

• Q: What is the input to the function?

  • A: The input is a sorted list nums containing elements that may have duplicates.

• Q: What is the expected output of the function?

  • A: The function should return the length of the list after removing duplicates, with the duplicates removed in-place.

• Q: Should the original list be modified?

  • A: Yes, the function should modify the original list in-place to remove duplicates.

• Q: Can additional lists or data structures be used?

  • A: No, the problem requires that no additional list or data structures be used.

• Q: What if the list is empty?

  • A: If the list is empty, the function should return 0.

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

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

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

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

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 list. One pointer will iterate through the list to find unique elements, while the other will maintain the position for placing unique elements.

1. If the input list `items` is empty, return 0.
2. Initialize a pointer `i` to 0 to track the last unique element's position.
3. Loop through the list 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. Delete the leftover tail (`del items[i+1:]`) so the list only contains unique elements.
5. Return `i + 1` to get the length of the modified list.

⚠️ Common Mistakes

• Not handling the empty list 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

    write = 1
    for read in range(1, len(items)):
        if items[read] != items[write - 1]:
            items[write] = items[read]
            write += 1

    # Remove leftover tail so the list contains only unique elements
    del items[write:]
    return write