2
\$\begingroup\$

Given the classical problem to find triplets that sum to zero in an array. Is my Scala implementation correct and executed in O(N^2)? If yes, why? Can someone make a running time analysis.

What other ways could we solve this issue? With duplicated elements and not using the two pointer technique?

def tripletsFromArrayThatSumZero(input: Array[Int]): Array[Array[Int]] = {
    val target = 0 // the target is the number after the sum
    val sortedArray = input.sorted
    var resultsArrayOfTriplets = Array[Array[Int]]()

    for (i <- sortedArray.indices) {
      var j = i + 1
      var k = sortedArray.length - 1
      val twoSum = target - sortedArray(i)

      Breaks.breakable {
        while (j < sortedArray.length) {
          val sum = sortedArray(j) + sortedArray(k)
          if (k == j) Breaks.break()
          if (sum > twoSum) {
            k -= 1
          } else if (sum < twoSum) {
            j += 1
          } else if (sum == twoSum) {
            val triplet = Array(sortedArray(i), sortedArray(j), sortedArray(k) )
            resultsArrayOfTriplets = resultsArrayOfTriplets :+ triplet
            Breaks.break()
          }
        }
      }
    }
    resultsArrayOfTriplets
  }
\$\endgroup\$
1
  • \$\begingroup\$ I think the idea behind the algorithm is sound, and very clever - good job. However, I don't think it accounts for multiple instances of the same value. {-3, 1, 1, 2} for example and I think it also misses cases where there are adjacent - call them matched - pairs {-5, 1, 2, 3, 4}. Put those cases into your tests and see what happens. \$\endgroup\$ – Donald.McLean Apr 30 at 17:23
2
\$\begingroup\$

I have a few issues with the posted code. We'll start with the trivial.

Code posted on Code Review should be complete. You forgot to include the necessary import to make this compile.

val target = 0 - I find this somewhat redundant. If target isn't zero then you also need to change the name of the method. On the other hand, we're not supposed to bury "magic numbers" in our code, so it's debatable.

But the real problem here is that you're writing imperative code in a functional language. You've written C code in Scala.

Imperative : Create an empty mutable collection. Run code with a side-effect of filling the collection. Return the collection.

Functional : Start with one or more populated collections. Filter, collect, and transform them, without mutation, into the resulting collection.

Here's an implementation that's similar in that the i index starts at zero, the j index starts at i+1, and the k index searches the remaining space for the result.

def zeroSumTriples(input: Array[Int]): Array[Array[Int]] = {
  val sortedInput = input.sorted

  sortedInput.takeWhile(_ < 1).indices.flatMap{ i =>
    (i+1).until(input.length-1).flatMap{ j =>
      val (a, b) = (sortedInput(i), sortedInput(j))
      Iterator.from(j+1).take(input.length-j-1)
              .dropWhile(a + b + sortedInput(_) < 0)
              .takeWhile(a + b + sortedInput(_) == 0)
              .map(k => Array(a, b, sortedInput(k)))
    }
  }
}.toArray
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Scala can be a functional language, and it's arguably its most elegant, powerful, and correct when written that way, but it can also be an object-oriented language, an abstract type system, or even an imperative language. It's consciously multi-paradigm. \$\endgroup\$ – Snowbody May 3 at 0:03
0
\$\begingroup\$

Since jwvh already has a great solution to your problem, I'll point out a few things in your original code.

One thing that immediately caught my eye was the use of Breaks.break(). This does not work the same as in Java. It throws a BreakControl exception that can stop your program if not caught by the breakable block encasing your while loop. Throwing and catching exceptions often can hurt performance, so I would strongly encourage you to stay away from scala.util.control.Breaks. I believe you can eliminate the first break by making the condition of the inner while loop j < k, but the second break would still remain.

Another thing is that you're using Arrays to represent triplets and the resulting list of triplets. Perhaps using an array for holding three numbers may be okay in Java, but even there, using an array for a collection that must grow in size is a bad idea.

In Java, you may use a class that implements List, such as an ArrayList, but in Scala, I'd suggest using a List, an immutable linked list for resultsArrayOfTriplets. Appending to an array isn't a great idea, since it requires creating a new array and copying elements of the old array to that (an O(n) operation). Instead, you can prepend new triplets to the existing list of triplets (a constant time operation).

For the triplets themselves, I would suggest using a tuple (Int, Int, Int) even though it's homogeneous and you can use an Array. This is both because Arrays are mutable, and you don't want to be able to modify the triplets later, and because an Array could be of any size, whereas here, the size of a triplet is fixed.

A couple smaller things - resultsArrayOfTriplets could be just results, and target could either be a parameter to allow the caller to generalize to triplets summing to any number or a "magic number."

However, making these changes would just be putting a bandaid on a much bigger problem. As jwvh pointed out, you're essentially writing C code in Scala. vars (and mutability), Arrays, while loops, and the like are not idiomatic in Scala.


To answer the question in the title, no, it appears your code would be O(n^2) in the worst case, since for every ith element of the array, the maximum number of times you would go through the array again is n-i.

\$\endgroup\$
-1
\$\begingroup\$

Your solution also works with O(n ^ 2), except you need to cover few cases as mentioned in the comments above.

A small solution that could make things look neat:

Efficient O(n ^ 2) ThreeSum Solution In Scala

object Solution {
  import scala.util.Sorting
  import scala.collection.mutable
  def threeSum(a: Array[Int]): List[List[Int]] = {
    if(a.isEmpty) List.empty
    else {
      Sorting.quickSort(a)
      val resArr = mutable.Set.empty[List[Int]]
      val range = a.indices.init
      for {
        i <- range
      } yield {
        var l = i + 1
        var r = a.length - 1
        while(l < r) {
          val tSum = a(i) + a(l) + a(r)
          if(tSum == 0) {
            resArr.addOne(List(a(i), a(l), a(r)))
            l += 1
            r -= 1
          } else if(tSum < 0) { l += 1 }
          else { r -= 1  }
        }
      }
      resArr.toList
    }
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.