Is My Function to Find Triplets in Scala running in O(N^2) 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 &lt;- sortedArray.indices) {
      var j = i + 1
      var k = sortedArray.length - 1
      val twoSum = target - sortedArray(i)

      Breaks.breakable {
        while (j &lt; sortedArray.length) {
          val sum = sortedArray(j) + sortedArray(k)
          if (k == j) Breaks.break()
          if (sum &gt; twoSum) {
            k -= 1
          } else if (sum &lt; twoSum) {
            j += 1
          } else if (sum == twoSum) {
            val triplet = Array(sortedArray(i), sortedArray(j), sortedArray(k) )
            resultsArrayOfTriplets = resultsArrayOfTriplets :+ triplet
            Breaks.break()
          }
        }
      }
    }
    resultsArrayOfTriplets
  }
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 &quot;magic numbers&quot; 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(_ &lt; 1).indices.flatMap{ i =&gt;
    (i+1).until(input.length-1).flatMap{ j =&gt;
      val (a, b) = (sortedInput(i), sortedInput(j))
      Iterator.from(j+1).take(input.length-j-1)
              .dropWhile(a + b + sortedInput(_) &lt; 0)
              .takeWhile(a + b + sortedInput(_) == 0)
              .map(k =&gt; Array(a, b, sortedInput(k)))
    }
  }
}.toArray