the best way to remove an element from list in multimap

now it's simply iterate over the lists and if list contains the value, removes it from

In Scala:

trait MultiMap[K, V] {

  final val map: mutable.Map[K, ArrayBuffer[V] = ...


  def values(): Seq[V] = ...

  def remove(value: V) = 
    for {
      (_, buff) <- map if buff.contains(value)
    } 
      buff -= value
}

In Java:

class MultiMap<K, V> {
    
    private final Map<K, ArrayList<V>> map = ...;

    public void remove(V value) {
        for (ArrayList<V> list: map.values()) {
            if (list.contains(value)) {
                list.remove(value);
                list.trimToSize();
            } 
        }
    }

}

both of the methods have O(n^2) complexity. how to improve the complexity of the algorithm?

Instead of removing item from ArrayBuffer after checking if it exists, you can try use filter operation instead:

trait MultiMap[K, V] {
    private final val map: mutable.Map[K, ArrayBuffer[V]] = mutable.Map.empty[K, ArrayBuffer[V]]
    def values(): Seq[V] = map.values.flatten.toSeq
    def remove(value: V): Unit = map.values.foreach(_.filter(_ != value))
}

it won't be O(N^2) if N total number of values, but because filter creates new buffer instance each time, this might be possibly another performance downside.

UPDATE

Another option, in order to achieve almost O(1) or more precisely O(M), where M amount of value duplicates, is to create another index or map, but for values and information where they are located (key in main map and index in buffer) :

import scala.collection.mutable._

trait MultiMap[K, V] {
    private final val map: Map[K, ArrayBuffer[V]] = Map.empty
    private final val valuesIndex: Map[V, ArrayBuffer[(K, Int)]] = Map.empty

    def add(key: K, value: V): Unit = {
      map += key -> map.get(key).fold(ArrayBuffer(value))(_ += value)
      valuesIndex += value -> valuesIndex.get(value).fold(ArrayBuffer(key -> 0))(_ += (key -> (map(key).length - 1)))
    }

    def remove(value: V): Unit = {
      valuesIndex.getOrElse(value, ArrayBuffer.empty).foreach {
        case (key, index) => map(key).remove(index)
      }
      valuesIndex.remove(value)
    }
}

Hope this helps!

You could bring your time complexity down to O(log n) (where n is number of values in tree) by using Red-black tree. Same thing is doing c++ in it's std::multimap implementation.

On a side note O(n^2) might not be exactly precise. If you have n keys, each with at most m elements in value array, your time complexity is O(n * m).

public void remove(V value) {
  for (List<V> list: map.values()) { // O(n)
    list.removeIf(element -> element.equals(value)); // O(m)
  }
}

You could switch to Map<K, HashSet<V>> that would bring you down to O(n)... but that does not satisfy the multiset requirement to allow duplicate values under one key:

public void remove(V value) {
  for (HashSet<V> set: map.values()) { // O(n)
    set.remove(value); // O(1)
  }
}