Remove Duplicates from Sorted Array

▶

Steps

setup

Check if array is empty

The algorithm first checks if the input array is empty. If it is, it returns 0 immediately because there are no elements to process.

💡 This early return avoids unnecessary processing and handles edge cases gracefully.

Line:

if len(nums) == 0:
    return 0

💡 The algorithm only proceeds if there is at least one element to process.

setup

Initialize uniqueIndex pointer

Initialize 'uniqueIndex' to 0, pointing to the first element, which is considered unique by default.

💡 This pointer tracks the position where the next unique element should be placed.

Line:

uniqueIndex = 0

💡 Starting with the first element as unique simplifies the logic for subsequent comparisons.

traverse

Start iterating with currentIndex = 1

Set 'currentIndex' to 1 to start scanning the array from the second element onward.

💡 This pointer scans ahead to find new unique elements to compare against the last unique element.

Line:

for currentIndex in range(1, len(nums)):

💡 The iteration begins from the second element because the first is already considered unique.

compare

Compare nums[currentIndex] with nums[uniqueIndex]

Compare the element at currentIndex (1) with the element at uniqueIndex (0). Both are 1, so they are duplicates.

💡 This comparison determines if the current element is a new unique value or a duplicate.

Line:

if nums[currentIndex] != nums[uniqueIndex]:

💡 Duplicates are skipped by not moving uniqueIndex or overwriting the array.

traverse

Move currentIndex to 2

Increment currentIndex to 2 to check the next element in the array.

💡 Moving currentIndex forward continues scanning for unique elements.

Line:

for currentIndex in range(1, len(nums)):

💡 The scanning pointer moves forward regardless of duplicates.

compare

Compare nums[currentIndex] with nums[uniqueIndex]

Compare element at currentIndex (2) with element at uniqueIndex (0). They differ (2 != 1), indicating a new unique element.

💡 Finding a different element means we found a new unique value to record.

Line:

if nums[currentIndex] != nums[uniqueIndex]:

💡 This step shows how the algorithm compacts unique elements towards the front.

insert

Increment uniqueIndex to 1

Increment uniqueIndex from 0 to 1 to prepare to overwrite the next position with the new unique element.

💡 Moving uniqueIndex forward reserves space for the new unique element.

Line:

uniqueIndex += 1

💡 uniqueIndex always points to the last unique element's position.

insert

Overwrite nums[uniqueIndex] with nums[currentIndex]

Copy the new unique element (2) at currentIndex to the position at uniqueIndex (1), overwriting the duplicate.

💡 This step compacts the array by placing unique elements consecutively at the front.

Line:

nums[uniqueIndex] = nums[currentIndex]

💡 Overwriting duplicates ensures the array's first part contains only unique elements.

traverse

End of iteration

The loop ends as currentIndex has reached the end of the array. All unique elements are now at the front.

💡 Completing the iteration means the array is compacted with unique elements in order.

Line:

for currentIndex in range(1, len(nums)):
    ...

💡 The array's first uniqueIndex + 1 elements are unique and sorted.

reconstruct

Return the count of unique elements

Return uniqueIndex + 1, which is 2, representing the number of unique elements in the array.

💡 The returned length tells how many elements at the start of the array are unique.

Line:

return uniqueIndex + 1

💡 The algorithm outputs the length of the unique portion of the array.

def remove_duplicates(nums):
    # STEP 1: Check if array is empty
    if len(nums) == 0:
        return 0
    # STEP 2: Initialize uniqueIndex
    uniqueIndex = 0
    # STEP 3: Iterate from second element
    for currentIndex in range(1, len(nums)):
        # STEP 4: Compare current element with last unique
        if nums[currentIndex] != nums[uniqueIndex]:
            # STEP 7: Increment uniqueIndex
            uniqueIndex += 1
            # STEP 8: Overwrite with new unique element
            nums[uniqueIndex] = nums[currentIndex]
    # STEP 10: Return count of unique elements
    return uniqueIndex + 1

if __name__ == '__main__':
    arr = [1,1,2]
    length = remove_duplicates(arr)
    print(length)  # Expected: 2
    print(arr[:length])  # Expected: [1,2]

📊

Remove Duplicates from Sorted Array - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how duplicates are skipped and unique elements are retained without extra space.

compare

1

0

1

1

2

2

move_left

uniqueIndex

1

0

1

1

2

2

compare

uniqueIndex

1

0

currentIndex

1

1

2

2

compare

uniqueIndex

1

0

currentIndex

1

1

2

2

move_right

uniqueIndex

1

0

1

1

currentIndex

2

2

compare

uniqueIndex

1

0

1

1

currentIndex

2

2

move_left

1

0

uniqueIndex

1

1

currentIndex

2

2

swap

1

0

uniqueIndex

2

1

currentIndex

2

2

compare

1

0

uniqueIndex

2

1

currentIndex

2

2

record

1

0

uniqueIndex

2

1

2

2

Result: 2

Key Takeaways

✓ Two pointers moving in the same direction efficiently identify and overwrite duplicates in-place.

This insight is hard to see from code alone because the pointer roles and their interaction are implicit without visualization.

✓ The uniqueIndex pointer only moves forward when a new unique element is found, ensuring compact storage of unique values.

Seeing this visually clarifies why uniqueIndex does not move on duplicates, which is subtle in code.

✓ Overwriting duplicates with new unique elements maintains the sorted order and avoids extra space usage.

The visualization shows how the array changes step-by-step, which is not obvious from just reading the code.

Practice

1. You are given an array representing heights of bars where water can be trapped between bars after raining. Which approach guarantees an optimal O(n) time and O(1) space solution to calculate the total trapped water?

easy

A. Use two pointers starting from opposite ends, updating left_max and right_max while moving inward.

B. Use a greedy approach that always fills the lowest bar first without considering future bars.

C. Use dynamic programming with a 2D table storing water trapped between every pair of bars.

D. Use a brute force nested loop to find max heights on left and right for each bar.

Solution

1. Step 1: Understand problem constraints

   The problem requires calculating trapped water efficiently in linear time and constant space.

2. Step 2: Identify approach matching constraints

   The two pointers approach moves inward from both ends, updating left_max and right_max, allowing O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers approach is known optimal for trapping rain water [OK]

Hint: Two pointers from ends -> O(n) time, O(1) space [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing DP with 2D tables for this problem
• Thinking greedy fill lowest bar always works

2. Consider the following buggy code for merging two sorted arrays in-place. Which line contains the subtle bug that causes missing elements in the final merged array?

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    # Missing copying remaining nums2 elements

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)

medium

A. Line 12: Missing while loop to copy remaining nums2 elements

B. Line 9: nums1[k] = nums2[j]

C. Line 4: i = m - 1

D. Line 7: if nums1[i] > nums2[j]:

Solution

1. Step 1: Analyze the main merging loop

   The main loop merges elements from the back correctly but stops when either i or j is negative.

2. Step 2: Identify missing step

   There is no loop copying remaining elements from nums2 if any remain, causing missing elements in nums1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without copying leftover nums2 elements, final array is incomplete [OK]

Hint: Always copy leftover nums2 elements after main loop [OK]

Common Mistakes:

• Forgetting leftover nums2 copy
• Overwriting nums1 elements too early

3. What is the time and space complexity of the optimal two-pointer overwrite approach for moving zeroes to the end of an array of length n?

medium

A. Time: O(n), Space: O(1) because it scans array twice but no extra space

B. Time: O(n^2), Space: O(1) due to nested loops

C. Time: O(n), Space: O(n) because it uses an auxiliary array implicitly

D. Time: O(n log n), Space: O(1) due to sorting involved

Solution

1. Step 1: Identify loops and operations

   The algorithm scans the array twice sequentially: once to overwrite non-zero elements, once to fill zeroes.

2. Step 2: Analyze time and space

   Each loop is O(n), total O(n). No extra arrays or recursion used, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear passes, constant extra space [OK]

Hint: Two linear scans, no nested loops or extra arrays [OK]

Common Mistakes:

• Mistaking two loops as nested (O(n^2))
• Assuming extra space due to overwriting
• Confusing with sorting complexity

4. What is the time complexity of the binary search based solution for Two Sum II -- Input Array Is Sorted, where for each element you perform a binary search for its complement?

medium

A. O(n²)

B. O(n)

C. O(log n)

D. O(n log n)

Solution

1. Step 1: Identify outer loop complexity

   Outer loop runs n times, iterating over each element.

2. Step 2: Identify inner binary search complexity

   Binary search runs in O(log n) time for each iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   n iterations x log n binary search -> O(n log n) [OK]

Hint: Outer loop x binary search = n x log n [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming binary search is O(1)
• Ignoring loop inside binary search

5. Suppose the 3Sum problem is modified so that elements can be reused multiple times in a triplet (e.g., triplet [0,0,0] is valid if zeros exist). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Remove the duplicate skipping for fixed element i and inner pointer j, allowing repeated elements.

B. Use three nested loops to allow repeated indices and check sums directly.

C. Keep the same code but remove the sorting step to allow duplicates naturally.

D. Modify the hash set approach to not skip duplicates and allow complement to be equal to nums[j].

Solution

1. Step 1: Understand reuse means duplicates allowed in triplets

   Allowing reuse means complement can be equal to nums[j], so skipping duplicates must be adjusted.

2. Step 2: Modify hash set approach accordingly

   Do not skip duplicates; allow complement == nums[j]; sorting still needed to avoid unordered duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Allowing complement == nums[j] and no skipping duplicates handles reuse correctly [OK]

Hint: Allow complement == nums[j] and no skipping duplicates for reuse [OK]

Common Mistakes:

• Removing sorting breaks uniqueness
• Using triple loops is inefficient
• Removing duplicate skipping blindly causes duplicates