title: Algorithm to translate list operations to be index based
body: <p>Assume you have an unsorted list of distinct items. for example: </p>
  
  <pre><code>['a', 'z', 'g', 'i', 'w', 'p', 't']
  </code></pre>
  
  <p>You also get a list of Insert and remove operations. Insert operations are composed of the index to insert to, and the item to insert. For example: Insert(5, 's')</p>
  
  <p>Remove operations are expressed using the element to remove. For example: Remove('s')</p>
  
  <p>So a list of operations may look like this: </p>
  
  <ul>
  <li>Insert ('s', 5)</li>
  <li>Remove ('p')</li>
  <li>Insert ('j', 0)</li>
  <li>Remove ('a')</li>
  </ul>
  
  <p>I am looking for the most efficient algorithm that can translate the list of operations so that they are index based. That means that there is no need to modify the insert operations, but the remove operations should be replaced with a remove operation stating the <strong>current</strong> index of the item to be removed (not the original one).</p>
  
  <p>So the output of the example should look like this:</p>
  
  <ul>
  <li>Starting set: ['a', 'z', 'g', 'i', 'w', 'p', 't']</li>
  <li>Insert('s', 5) ( list is now: ['a', 'z', 'g', 'i', 'w', 's', 'p', 't']</li>
  <li>Remove (6) (list is now: ['a', 'z', 'g', 'i', 'w', 's', 't']</li>
  <li>Insert('j', 0) (list is now: ['j', 'a', 'z', 'g', 'i', 'w', 's', 't']</li>
  <li>Remove(1) (list is now: ['j', 'z', 'g', 'i', 'w', 's', 't']</li>
  </ul>
  
  <p>Obviously, we can scan for the next item to remove in the set after each operation, and that would mean the entire algorithm would take O(n*m) where n is the size of the list, and m is the number of operations.</p>
  
  <p>The question is - is there a more efficient algorithm?</p>