Remove Duplicates - codepath/compsci_guides GitHub Wiki

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.

  • Q: What is the input to the function?

    • A: The input is a sorted array items containing elements that may have duplicates.

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

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

  • Q: Should the original array be modified?

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

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

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

  • Q: What if the array is empty?

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

  • 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", "thistle", "extract of malt"]
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