title: Remove all occurrences of a value from a list in linear time
body: <p>I would like to implement a program in python where all occurrences of a value are removed from a list in place and in linear time (O(n)). There have been posts of problems similar to this, but none had the constraint of doing it in linear time. </p>
  
  <p>I managed to come up with a solution, but I am looking for a more simpler and cleaner version (or preferably a totally different implementation).</p>
  
  <p>Below I use two "pointers", back and front, to traverse through the list. Both start at 0 and go through the list until they hit the value that want we want remove. At that point the front pointer checks if the integers after are also the values we want to remove. Front pointer continues to traverse until we hit the first integer, which is not the value we want. Then I swap value and continue the process. </p>
  
  <pre><code>def remove_all(lst, val):
      back = 0
      front = 0
      while (front &lt; len(lst)-1):
          while(front &lt; len(lst) and lst[front] != val):
              front += 1
              back += 1
          if (front &lt; len(lst)-1 and lst[front] == val):
              while(front &lt; len(lst)-1 and lst[front] == val):
                  front += 1
              lst[back], lst[front] = lst[front], lst[back]
              back += 1
      if (lst[-1] != val):
          raise ValueError('Value not present in the list')
      while(len(lst) != 0 and lst[-1] == val):
          lst.pop()
  </code></pre>