Unit 3 Session 2 (Click for link to problem statements)
TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
Q: What is the input to the function?
items
containing elements that may have duplicates.Q: What is the expected output of the function?
Q: Should the original array be modified?
Q: Can additional arrays or data structures be used?
Q: What if the array is empty?
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: []
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
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