No Duplicates Allowed

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

U-nderstand

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

• Which copy of a repeated number should be kept?
  • The last occurrence. Earlier copies are removed, and the kept numbers stay in the same relative order as their last occurrences in nums.
• What if the list is empty?
  • Return an empty list.

HAPPY CASE
Input: nums = [1, 2, 1, 3, 2]
Output: [1, 3, 2]
Explanation: The earlier copies of 1 (index 0) and 2 (index 1) are removed. The last occurrences at indices 2, 3, and 4 remain in order.

EDGE CASE
Input: nums = []
Output: []
Explanation: There are no numbers, so the result is empty.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Loop backwards through the list, and each time we find a new element, add it to the front of a new list.

1) Create an empty list to store unique numbers
2) Starting at the END of the nums list:
  a) If the number is not already in unique,
     insert it at the beginning of unique
3) Return the unique nums

⚠️ Common Mistakes

• Scanning from the front and keeping the first copy of each number. That keeps the wrong copy: on [1, 2, 1, 3, 2] it returns [1, 2, 3] instead of [1, 3, 2].
• Assuming the list-based solution is linear. On a Python list, x not in unique_nums is O(n) and unique_nums.insert(0, x) is O(n), so the first solution below takes O(n^2) time in the worst case (when every number is distinct). The frequency-map solution uses average O(1) dict lookups and builds its result with append, so it runs in O(n) time.

I-mplement

def remove_duplicates_from_front(nums):
    unique_nums = []
    for i in range(len(nums)-1, -1, -1):
        if nums[i] not in unique_nums:
            unique_nums.insert(0, nums[i])
    return unique_nums

Alternate solution using a modified frequency map:

def remove_duplicates_from_front(nums):
    frequency_map = {}
    for num in nums:
        frequency_map[num] = True
    last_occurrences = []
    for num in nums[::-1]:  # Reverse iterate
        if frequency_map[num]:
            last_occurrences.append(num)
            frequency_map[num] = False
    return last_occurrences[::-1]  # Reverse again to original order