Remove Element

▶

Steps

setup

Initialize pointers

Set 'start' to 0 (beginning) and 'end' to 3 (last index). The array is [3,2,2,3].

💡 Initializing pointers sets the stage for scanning and partitioning the array.

Line:

start, end = 0, len(nums) - 1

💡 We have two pointers ready to scan and modify the array from opposite ends.

compare

Check if nums[start] == val

Check if element at 'start' (index 0) equals val (3). It does, so we prepare to swap.

💡 This comparison decides if we need to swap to remove the val element.

Line:

if nums[start] == val:

💡 When the current element equals val, we swap it with the element at 'end' to move val to the back.

swap

Swap nums[start] and nums[end]

Swap elements at 'start' (index 0) and 'end' (index 3). Both are 3, so array remains the same.

💡 Swapping moves val elements to the end, shrinking the valid array.

Line:

nums[start], nums[end] = nums[end], nums[start]

💡 Even if values are the same, the swap ensures val is at the end and 'end' pointer can move left.

shrink

Decrement end pointer

After swapping, decrement 'end' from 3 to 2 to exclude the last element from valid range.

💡 Moving 'end' left shrinks the array size to exclude val elements at the end.

Line:

end -= 1

💡 The valid array now ends at index 2, ignoring the last element which is val.

compare

Check if nums[start] == val again

Check if element at 'start' (index 0) equals val (3). It still does, so prepare to swap again.

💡 We re-check because 'start' did not move yet; we must remove all val elements at 'start'.

Line:

if nums[start] == val:

💡 Multiple val elements at the start require multiple swaps to move them out.

swap

Swap nums[start] and nums[end]

Swap elements at 'start' (index 0) and 'end' (index 2). Array changes from [3,2,2,3] to [2,2,3,3].

💡 Swapping moves val element at start to the end, and brings a non-val element forward.

Line:

nums[start], nums[end] = nums[end], nums[start]

💡 This swap effectively moves a val element out and a valid element in, shrinking the problem.

shrink

Decrement end pointer

After swapping, decrement 'end' from 2 to 1 to exclude the last val element.

💡 Shrinking the valid array from the right excludes val elements moved there.

Line:

end -= 1

💡 The valid array now ends at index 1, excluding val elements at indices 2 and 3.

compare

Check if nums[start] == val

Check if element at 'start' (index 0) equals val (3). It does not (nums[0] = 2), so increment 'start'.

💡 When current element is not val, we move 'start' forward to check next element.

Line:

else:
    start += 1

💡 Incrementing 'start' moves the scanning forward over valid elements.

traverse

Increment start pointer

Increment 'start' from 0 to 1 to check the next element.

💡 Moving 'start' forward continues scanning for val elements to remove.

Line:

start += 1

💡 The algorithm progresses by scanning each element from the left.

compare

Check if nums[start] == val

Check if element at 'start' (index 1) equals val (3). It does not (nums[1] = 2), so increment 'start'.

💡 Continue scanning valid elements to find any remaining val elements.

Line:

else:
    start += 1

💡 No swap needed; just move forward.

traverse

Increment start pointer

Increment 'start' from 1 to 2. Now 'start' is 2 and 'end' is 1, so loop ends.

💡 When 'start' passes 'end', scanning is complete and valid elements are at the front.

Line:

start += 1

💡 The new length of the array without val elements is 'start' = 2.

reconstruct

Return new length

Since 'start' (2) is now greater than 'end' (1), return 'start' as the new length of the array without val elements.

💡 Returning 'start' gives the count of valid elements at the front of the array.

Line:

return start

💡 The algorithm partitions the array so that the first 'start' elements are valid.

def remove_element(nums, val):
    start, end = 0, len(nums) - 1  # STEP 1
    while start <= end:  # STEP 2 loop condition
        if nums[start] == val:  # STEP 2 compare
            nums[start], nums[end] = nums[end], nums[start]  # STEP 3 swap
            end -= 1  # STEP 4 decrement end
        else:
            start += 1  # STEP 8,9,11 increment start
    return start  # STEP 12

if __name__ == '__main__':
    arr = [3,2,2,3]
    val = 3
    new_len = remove_element(arr, val)
    print(new_len, arr[:new_len])

📊

Remove Element - Watch the Algorithm Execute, Step by Step

Watching each pointer move and swap helps you understand how the algorithm efficiently removes elements in-place without extra space.

setup

start

3

0

2

1

2

2

end

3

3

compare

start

3

0

2

1

2

2

end

3

3

swap

start

3

0

2

1

2

2

end

3

3

move_right

start

3

0

2

1

end

2

2

3

3

compare

start

3

0

2

1

end

2

2

3

3

swap

start

2

0

2

1

end

3

2

3

3

move_right

start

2

0

end

2

1

3

2

3

3

compare

start

2

0

end

2

1

3

2

3

3

move_left

2

0

end

2

1

3

2

3

3

compare

2

0

end

2

1

3

2

3

3

move_left

2

0

end

2

1

start

3

2

3

3

return

2

0

end

2

1

start

3

2

3

3

Result: 2

Key Takeaways

✓ Two pointers scan from opposite ends to partition the array in-place efficiently.

This insight is hard to see from code alone because the pointer interactions are subtle and happen simultaneously.

✓ Swapping val elements to the end shrinks the valid array size without extra space.

Visualizing the swap and pointer decrement clarifies how the array is partitioned dynamically.

✓ The 'start' pointer only moves forward when the current element is not val, ensuring all val elements are removed.

Seeing the pointer stall and swap when val is found helps understand the control flow better than reading code.

Practice

1. You are given a sorted array of integers and a value K. You need to count the number of pairs (i, j) with i < j such that the absolute difference between the elements at these indices is at most K. Which algorithmic approach guarantees the most efficient solution for this problem?

easy

A. Use binary search to find the upper bound for each element and count pairs accordingly.

B. Use a brute force nested loop to check all pairs and count those with difference ≤ K.

C. Use dynamic programming to store counts of valid pairs up to each index.

D. Use a two-pointer sliding window approach to find pairs with difference ≤ K in O(n) time.

Solution

1. Step 1: Understand problem constraints and sorted input

   The array is sorted, so for each element, pairs with difference ≤ K lie within a contiguous range to the right.

2. Step 2: Identify optimal approach

   A two-pointer sliding window approach can find pairs with difference ≤ K in O(n) time by expanding and contracting the window efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two pointers leverage sorted order for linear time counting [OK]

Hint: Two-pointer sliding window exploits sorted array for O(n) counting [OK]

Common Mistakes:

• Assuming binary search is always better than two pointers
• Using DP which is unnecessary and inefficient
• Choosing brute force due to simplicity

2. Consider the following Python code that reverses a list of characters recursively using two pointers. What will be the final output printed by the program?

def reverseString(s):
    def helper(left, right):
        if left >= right:
            return
        s[left], s[right] = s[right], s[left]
        helper(left + 1, right - 1)

if __name__ == "__main__":
    s = ['a', 'b', 'c', 'd']
    reverseString(s)
    print(s)

easy

A. ['d', 'b', 'c', 'a']

B. ['d', 'c', 'b', 'a']

C. ['a', 'b', 'c', 'd']

D. ['c', 'b', 'a', 'd']

Solution

1. Step 1: Trace helper calls and swaps

   Initial call helper(0,3): swap s[0] and s[3] -> ['d','b','c','a'] Next call helper(1,2): swap s[1] and s[2] -> ['d','c','b','a'] Next call helper(2,1): left >= right, stop recursion.

2. Step 2: Final array state

   The array after all swaps is ['d','c','b','a'], which is the reversed input.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All pairs swapped correctly, final reversed array matches ['d', 'c', 'b', 'a'] [OK]

Hint: Recursive swaps from ends reverse array correctly [OK]

Common Mistakes:

• Off-by-one errors in recursion base case
• Swapping wrong indices
• Not swapping at all

3. Given the following code for trapping rain water, what is the value of the variable water returned by trap([2,0,2])?

easy

A. 4

B. 0

C. 2

D. 1

Solution

1. Step 1: Initialize variables

   left=0, right=2, left_max=0, right_max=0, water=0

2. Step 2: Trace iterations

   Iteration 1: height[left]=2, height[right]=2, height[left] not less than height[right], so process right pointer. right_max updated to 2, right moves to 1.
   Iteration 2: left=0, right=1, height[left]=2, height[right]=0, height[left] > height[right], process right pointer.
   height[right]=0 < right_max=2, water += 2 - 0 = 2, right moves to 0.
   Loop ends as left == right.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Water trapped between two height 2 bars with 0 in middle is 2 units [OK]

Hint: Trace pointers and water increments carefully [OK]

Common Mistakes:

• Off-by-one errors in pointer movement
• Confusing which pointer to move
• Incorrectly updating max heights

4. Suppose the problem changes: you can reuse elements multiple times to form the triplet sum closest to the target. Which modification to the two-pointer approach correctly handles this scenario?

hard

A. Keep the two-pointer approach but reset pointers after each sum check to allow reuse.

B. Use three nested loops to allow repeated elements since two pointers assume unique indices.

C. Modify the two-pointer approach to allow left and right pointers to stay or move without skipping duplicates, enabling reuse.

D. Sort the array and use a hash set to store sums, then binary search for closest sum.

Solution

1. Step 1: Understand reuse requirement

   Reusing elements means pointers can stay or move without skipping duplicates, unlike standard two-pointer which assumes unique indices.

2. Step 2: Adjust two-pointer logic

   Allow pointers to move or stay to consider repeated elements, carefully updating closest sum without skipping valid reuse combinations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Modifying pointer movement to allow reuse fits problem constraints [OK]

Hint: Allow pointers to stay or move to reuse elements [OK]

Common Mistakes:

• Using naive two-pointer without reuse
• Switching to triple loops unnecessarily
• Using hash sets without efficiency

5. If the problem is changed so that duplicates are allowed at most k times (where k is a positive integer), which modification to the optimal two-pointer approach is correct?

hard

A. Change the condition to compare current element with the element at write_index - k and allow writing if different

B. Use a hash map to count occurrences and rebuild the array with at most k duplicates

C. Keep the original condition comparing with write_index - 2 regardless of k

D. Use nested loops to remove duplicates exceeding k by shifting elements

Solution

1. Step 1: Understand the generalization

   Allowing at most k duplicates means we must check if the current element differs from the element k positions before the write pointer.

2. Step 2: Modify the condition accordingly

   Replace the fixed 2 with k in the condition: write_index < k or nums[read_index] != nums[write_index - k]. This generalizes the approach.

3. Step 3: Avoid inefficient or incorrect methods

   Hash maps or nested loops increase time or space complexity unnecessarily.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Condition generalized to k duplicates ensures correctness and efficiency [OK]

Hint: Replace 2 with k in index offset check [OK]

Common Mistakes:

• Not generalizing condition to k
• Using hash maps increases space
• Nested loops cause O(n²) time