Remove Element

Problem

• Given an integer array nums and an integer val, remove all occurrences of val in-place. Return the number of remaining elements, and make sure the first k elements of nums (where k is the return value) are the elements not equal to val. Order doesn't matter and leftover values after k don't matter either.

Approach

• 1. Track how many values removed with a counter
• 2. Loop through the array. When you hit a value equal to val, swap it with the element from the back.
• 3. Keep shrinking the end of the array like insertion sort where you know which values are already sorted.
• 4. Don't increment the main index if you just swapped, you need to re-check the new value at that spot.

Edge Cases

• All elements are val → return 0.
• No elements are val → return len(nums).
• Multiple vals at the end or beginning, swap logic still works.

Reflections

It’s basically compacting the valid elements to the front. This problem really made me think about when NOT to increment an index. Very tricky problem and the top solution made me realize I was dramatically overthinking it and coming from the wrong angle. The best solutions utilzed val != nums[i] where as I used a proper two pointer solution as long as val == nums[i].

Go Solution

func removeElement(nums []int, val int) int {
  c := 0
  for i := 0; i <= len(nums)-1-c; i++ {
    for nums[i] == val && i <= lch(nums,c) {
      if i != lch(nums, c) {
        nums[i], nums[lch(nums, c)] = nums[lch(nums, c)], nums[i]
      }
      c++
    }
  }
  return lch(nums, c) + 1
}

func lch(n []int, c int) int {
  return len(n) - 1 - c
}

Performance

• Runtime beats: 100%
• Memory beats: 20%

Complexity

• Time: O(n) Potentially visit every element once, even if some are swapped.
• Space: O(1) Do everything in-place with a few counters — no extra memory needed.