CODEWITHSUNDEEP
scala
RichyHBM
RichyHBM

Reputation: 798

Functional "Find pairs that add up to X" with linear time complexity

I am trying to implement the "find pairs that add up to X" functionally with linear time complexity, for which I have the following:

def pairs(nums: List[Int], sum: Int): List[(Int, Int)] = {

  def pairsR(nums: List[Int], sum: Int, start: Int, end: Int, acc: List[(Int, Int)]): List[(Int, Int)] = {

    val newAcc = nums(start) + nums(end) match {
      case n if n == sum => ( (nums(start), nums(end)) :: acc, start + 1, end - 1)
      case n if n < sum => (acc, start + 1, end)
      case n if n > sum => (acc, start, end - 1)
    }

    if(start < end) pairsR(nums, sum, newAcc._2, newAcc._3, newAcc._1)
    else newAcc._1
  }

  pairsR(nums, sum, 0, nums.length - 1, List())
}

Which would work if I were trying to look for the first pair that adds to X (assuming I return after finding the first occurrence). But because I am trying to find all pairs I am getting some duplicates, as seen here: (note in the list there is only a single 5, yet because the pointers arrive at 5 at the same time I am guessing they count it twice)

pairs(List(1,2,3,4,5,6,7,8,9), 10) should equalTo (List( (1, 9), (2, 8), (3, 7), (4, 6) ))

Yet I get the following failure:

List((5,5), (4,6), (3,7), (2,8), (1,9)) is not equal to List((1,9), (2,8), (3,7), (4,6))

Is this algorithm just not possible to accomplish in linear time when you are looking for ALL pairs (and not just the first)? I know its possible to do with a HashSet, but I wanted to know if you could take the "pointers" approach?

Upvotes: 2

Views: 79

Answers (1)

Aivean
Aivean

Reputation: 10892

Here is an updated version of your code:

def pairs(nums: List[Int], sum: Int): List[(Int, Int)] = {
  val numsArr = nums.toArray

  def pairsR(start: Int, end: Int, acc: List[(Int, Int)]): List[(Int, Int)] =
    numsArr(start) + numsArr(end) match {
      case _ if start >= end => acc.reverse
      case `sum` => pairsR(start + 1, end - 1, (numsArr(start), numsArr(end)) :: acc)
      case n if n < sum => pairsR(start + 1, end, acc)
      case n if n > sum => pairsR(start, end - 1, acc)
    }

  pairsR(0, numsArr.length - 1, Nil)
}

Test:

pairs(1 to 9 toList, 10)

Result:

res0: List[(Int, Int)] = List((1,9), (2,8), (3,7), (4,6))

Some notes:

  1. When start and end pointers intersect somewhere at the middle of the array, it's time to end recursion and return acc. This condition must go first so you don't apply generic logic
  2. As you prepend results to the acc, acc is in reversed order in the end, so it's reasonable to reverse it before returning.
  3. No need to add static parameters, such as nums and sum as arguments of the inner recursive function
  4. As people suggested in the comments, if you need read-only collection with constant time indexed access, your choice is Array. Vector will also work, but it's slower

As a side note, current implementation may produce incorrect results if you have duplicate elements in your input list:

pairs(List(1,1,1,2,2), 3)

Result:

res1: List[(Int, Int)] = List((1,2), (1,2))

The easiest way to fix that is to preprocess input list removing duplicate elements. This will make result contain only distinct pairs. However if you want to include all pairs with elements of the same value but different index, then it's not possible to do that in linear time (consider an example when you have N elements of X value and you want to find all sums of 2X. Result's length will be N2).

Also, this algorithm requires input data to be sorted. There is an easy change to the algorithm to make it work on unsorted data (using counting sort).

Upvotes: 1

Related Questions