More Scala style code for one swap problem

Question
1

I came across a leetcode like problem - one swap[1]. The solution I found using sort plus for loop to solve that problem, for which I understand it is not the best solution for that problem. I feel it’s a bit interested, so I spent some time coding with Scala. The code is as below. But it seems to me there are rooms to improve (to be more Scala style because I feel my code is seemingly verbose) but I am not aware of. So I appreciate if any suggestions regarding this. By the way, I am not looking for the correct solution, nor cryptic effective (or imperative) way for this problem. I am merely looking for more Scala/ readable style approaching to such question. Many thanks.

def oneSwap(list: List[Int]): Boolean = {
  def isOneSwap(newList: List[Int]): Boolean = newList.sliding(2).find{ case pair =>
    val prev = pair(0)
    val current = pair(1)
    if (current < prev) true else false
  } match {
    case Some(_) => false
    case None => true
  }

  case class Acc(count: Int = 0, first: Int = 0, second: Int = 0)
  val acc = list.sliding(2).zipWithIndex.foldLeft(Acc()){ 
    case (acc, (List(prev, current), idx)) => 
    if(current < prev) {
      val newAcc = acc.copy(count = acc.count + 1)
      if(newAcc.first == 0) newAcc.copy(first = idx + 1) 
      else newAcc.copy(second = idx + 1)
    } else acc
  }
  acc.count match {
    case cnt if cnt > 2 => false
    case cnt if cnt == 0 => true
    case cnt if cnt == 2 =>
      val newList = list.
        updated(acc.first-1, list(acc.second)).
        updated(acc.second, list(acc.first-1))
      isOneSwap(newList)
    case cnt if cnt == 1 =>
      val newList = list.
        updated(acc.first-1, list(acc.first)).
        updated(acc.first, list(acc.first-1))
      isOneSwap(newList)
  }
}

[1]. Check if array can be sorted with one swap - GeeksforGeeks

2

You can follow the simple approach of sorting the input and comparing the mismatches.

def oneSwap(list: List[Int]): Boolean = {
  val mismatches =
    list.lazyZip(list.sorted).count {
      case (l, r) => l != r
    }

  mismatches <= 1
}

One may optimize the solution a little bit stoping once the count reaches 2 like this:

def oneSwap(list: List[Int]): Boolean =
  list
    .lazyZip(list.sorted)
    .view
    .collect {
      case (l, r) if (l != r) => 1
    }.scanLeft(0)(_ + _)
    .exists(_ == 2)
2 Likes
3

Keeping your linear time approach, here are some suggestions for improving the code

Instead of using find, if you are only interested if there is a matching element, you should use exists / forall. They also take a function returning a boolean, but return a boolean directly. Also, if (condition) true else false is the same as just writing condition.
If you want to define a non-partial function, like for find, you don’t need to use case, if you don’t do pattern matching. But in this case, it’s useful to do pattern matching, as you can destructure the Lists you get from sliding. Also, I think isSorted better describes what this function does. So a more concise way to write this would be:

def isSorted(newList: List[Int]): Boolean =
    newList.sliding(2).forall{
      case List(prev, current) => prev < current
      case _ => true // only happens if list is shorter than 2
    }

This returns true, if for all pairs in the list, the earlier element is smaller, so it returns false, if any pair is not sorted.

Next, finding the occurrences of wrongly ordered items:

I’d say this approach is fine. But we can skip the logic for deciding, if our current found unordered element is the first or not, if we just collect all the occurrences. This way, we also don’t need to keep count, but can just look at the results length:

val acc = list.sliding(2).zipWithIndex.collect {
            case (List(prev,curr), idx) if curr < prev => idx + 1 
          }.toList

collect takes a partial function, i.e. a function which may be undefined for some inputs. In Scala you can write it as a non-exhaustive pattern match. It works similarly to map, but filtering out elements for which no case matches. So in this case, it returns idx + 1 for any index, where the pair is not in order. The list’s length will be equivalent to count in your solution. We also need to modify the match for this variant:

acc match {
    case Nil => true
    case List(first) =>
      isSorted(list.
          updated(first-1, list(first)).
          updated(first, list(first-1)))
    case List(first, second) =>
      isSorted(list.
          updated(first-1, list(second)).
          updated(second, list(first-1)))
    case _ => false // more than two occurrences
  }

The whole thing in a scastie

2 Likes
4

That’s nice. I didn’t know lazyZip. :+1:

5

I did learn forall and collect previously, but can’t connect them together. Concrete examples really help me understand better. Appreciate that!

def isSorted(newList: List[Int]): Boolean =
   newList.sliding(2).forall{
     case List(prev, current) => prev < current
     case _ => true // only happens if list is shorter than 2
   }

val acc = list.sliding(2).zipWithIndex.collect {
           case (List(prev,curr), idx) if curr < prev => idx + 1 
         }.toList