# More Scala style code for one swap problem

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)
}
}
``````

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

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 `List`s 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

That’s nice. I didn’t know lazyZip.

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
``````