Kratos Kratos - 2 months ago 10
Scala Question

Split the list when duplicate is found scala

I have a list of elements in Scala and I am looking for a way to split the list when a duplicate is found.

For example:

List(x,y,z,e,r,y,g,a)
would be converted to
List(List(x,y,z,e,r),List(y,g,a))

or
List(x,y,z,x,y,z)
to
List(x,y,z), List(x,y,z)

and
List(x,y,z,y,g,x)
to
List(x,y,z), List(y,g,x)


Is there a more efficient way than iterating and and cheking for every element separately?

Answer

Quick and dirty O(n) using O(n) additional memory:

import scala.collection.mutable.HashSet
import scala.collection.mutable.ListBuffer

val list = List("x", "y", "z", "e", "r", "y", "g", "a", "x", "m", "z")

var result = new ListBuffer[ListBuffer[String]]()
var partition = new ListBuffer[String]()

list.foreach { i => 
    if (partition.contains(i)) {
        result += partition
        partition = new ListBuffer[String]()
    }
    partition += i
}

if (partition.nonEmpty) {
    result += partition
}
result

ListBuffer(ListBuffer(x, y, z, e, r), ListBuffer(y, g, a, x, m, z))

Comments