CODEWITHSUNDEEP
scalafold
Karim Ibrahim
Karim Ibrahim

Reputation: 93

Checking Array content equality in linear time in Scala

I want to check if 2 arrays (target and arr) of integers have the same content (both arrays are unordered). Example: Array(1,1,3,4,1,5) contents are equal to Array(1,1,1,5,4,3) contents. I'm aware of the sorting solution and I'm trying to work out the linear time solution. I'm starting by getting the profile of the target array by target.groupBy(identity) and then folding the destination array using that profile:

def canBeEqual(target: Array[Int], arr: Array[Int]): Boolean = {
        import scala.collection.mutable.Map
        var profile = target.groupBy(identity).view.mapValues(_.length).toMap
        var mutableProfile = Map(profile.toSeq: _*)
        arr.fold(mutableProfile)((p, x) => {p(x) = p(x) - 1; p}).isEmpty 
    }

The problems I faced:

  1. The default Map is immutable, I rebuilt the profile map using the mutable map. How would that affect performance?
  2. I'm getting this compilation error:
Line 5: error: value update is not a member of Any (in solution.scala)
arr.fold(mutableProfile)((p, x) => {p(x) = p(x) - 1; p}).isEmpty
                                            ^

I added the types arr.fold(mutableProfile)((p:Map[Int,Int], x:Int) => {p(x) = p(x) - 1; p}).isEmpty and it failed with this error:

Line 5: error: type mismatch; (in solution.scala)
found   : (scala.collection.mutable.Map[Int,Int], Int) => scala.collection.mutable.Map[Int,Int]
required: (Any, Any) => Any

I'm currently stuck at this point. Can't figure out the issue with the mismatching types. Also any recommendations on how to approach this problem idiomatically (and efficiently) are appreciated.

Upvotes: 1

Views: 82

Answers (1)

Jatin
Jatin

Reputation: 31724

Not going by algorithm modifications, but to clear the compilation errors:

  def canBeEqual(target: Array[Int], arr: Array[Int]): Boolean = {
    if (target.length != arr.length) {
      false
    } else {
      var profile = target.groupBy(identity).mapValues(_.length)
      
      arr.forall(x =>
        profile.get(x) match {
          case Some(e) if e >= 1 =>
            profile += (x -> (e - 1))
            true
          case Some(_) => false
          case None => false
        })
    }
  }

Note that adding or removing from an immutable HashMap takes constant time. (ref: https://docs.scala-lang.org/overviews/collections/performance-characteristics.html)

forall preferred over fold as one can break in between when the condition does not match. (try putting a print statements in match to validate)

Or you can do:

target.groupBy(identity).mapValues(_.length) == arr.groupBy(identity).mapValues(_.length)

Upvotes: 3

Related Questions