Move Element To End

Tags

Move Element To End

Category

Arrays

Difficulty

Medium

Problem Statement

Given an array of integers and a target integer, move all instances of the target integer to the end of the array. The order of the non-target elements does not need to be preserved. The operation must be performed in place.

Intuition

We can use a two-pointer technique where one pointer starts at the beginning and the other at the end. The left pointer searches for elements equal to the target, while the right pointer searches for elements not equal to the target. When both find their respective elements, we swap them. This efficiently partitions the array without needing extra space.

Approach

  1. Initialize two pointers: left at index 0 and right at the last index.
  2. While left < right:
    • If the element at right equals the target, decrement right (it is already in the correct region).
    • Else if the element at left equals the target, swap elements at left and right, then move both pointers inward.
    • Else increment left (element is not the target and is already in the correct region).
  3. Return the modified array.

Pseudocode

function moveElementToEnd(array, toMove):
    left = 0
    right = length(array) - 1

    while left < right:
        if array[right] == toMove:
            right -= 1
        else if array[left] == toMove:
            swap(array[left], array[right])
            left += 1
            right -= 1
        else:
            left += 1

    return array

Time & Space Complexity

  • Time: O(n) — each element is visited at most once by either pointer.
  • Space: O(1) — the rearrangement is done in place with only two pointer variables.

Key Insights

  • The two-pointer approach guarantees a single pass through the array.
  • We must check right first to avoid swapping a target element from the right into the left region.
  • The relative order of non-target elements is not preserved, which is acceptable per the problem constraints.

Edge Cases

  • Array is empty: return an empty array.
  • Target does not exist in the array: no swaps occur, array is returned unchanged.
  • All elements equal the target: every element stays, array is unchanged.
  • Array has a single element: return as-is regardless of whether it matches the target.

Linked mentions