Remove Duplicates from the List recursively

Related searches

I want to remove duplicates from the list recursively using pattern matching with Scala

here is my input

val xs = List(1,2,3,4,6,3,2,7,9,4)

Tried code:

  def removeDuplicates(xs : List[Int]) : List[Int] = xs match {
  case Nil =>Nil
  case x::ys => { 
      if(ys.contains(x)){
      removeDuplicates(ys)
    } else {
        }
/// ???
  }
}

I was stuck at the question mark, how to appened my result to the mutable list and return it.

Thank you.

You're close:

 def removeDuplicates(xs : List[Int]) : List[Int] = xs match {
  case Nil => Nil
  case x::ys => if (ys.contains (x)) removeDuplicates (ys) else
      x :: removeDuplicates (ys)
 }

scala> removeDuplicates (List (1,2,3,4,6,3,2,7,9,4))
res143: List[Int] = List(1, 6, 3, 2, 7, 9, 4)

While this is a brief solution, it isn't tail recursive and therefore vulnerable for stackoverflows - whereas Jean Logearts solution solves the problem.

Here is an alternative solution with an inner function, tailrecursive too:

def removeDuplicates (xsOuter : List[Int]) : List[Int] = {

  @annotation.tailrec
  def removeDuplicates (xs: List[Int], collected: List[Int]) : List[Int] = xs match {
    case Nil => collected
    case x :: ys => if (collected.contains (x)) removeDuplicates (ys, collected) else
      removeDuplicates (ys, x :: collected)
  }

  removeDuplicates (xsOuter, Nil)
}

scala> removeDuplicates (List (1,2,3,4,6,3,2,7,9,4))
res151: List[Int] = List(9, 7, 6, 4, 3, 2, 1)

with a bias to the first elements, but with the result reversed, which can be easily corrected by returning collected.reverse in the Nil case, if it is important.

The outer function serves the job to provide a simple, one-argument interface to the user, so he doesn't need to provide an empty List.

Note, that the solution is crying for a type annotation, since it doesn't depend at all on the List elements being of type Int:

scala> def removeDuplicates [A] (xsOuter : List[A]) : List[A] = {
     | 
     |   @annotation.tailrec
     |   def removeDuplicates (xs: List[A], collected: List[A]) : List[A] = xs match {
     |     case Nil => collected
     |     case x :: ys => if (collected.contains (x)) removeDuplicates (ys, collected) else
     |       removeDuplicates (ys, x :: collected)
     |   }
     | 
     |   removeDuplicates (xsOuter, Nil)
     | }
removeDuplicates: [A](xsOuter: List[A])List[A]

scala> removeDuplicates (List (1,2,3,4,6,3,2,7,9,4))
res152: List[Int] = List(9, 7, 6, 4, 3, 2, 1)

remove duplicates in a list, using recursion instead of loops. � GitHub, if (old_list[0] not in new_list):. Notice that new_list will always be empty at this point, so this condition will always be true and all elements will be� The following approach can be followed to remove duplicates in O (N) time: Start from the leftmost character and remove duplicates at left corner if there are any. The first character must be different from its adjacent now. Recur for string of length n-1 (string without first Let the string

You need to keep track of the current state: already seen elements using a set (for fast lookup), and the new list being constructed:

@tailrec
def removeDuplicatesRec(
  remaining: List[Int], 
  seen: Set[Int], 
  acc: List[Int]
): List[Int] = remaining match {
  case Nil => acc
  case head :: tail => 
    if (!seen.contains(head)) removeDuplicatesRec(tail, seen + head, acc :+ head)
    else removeDuplicatesRec(tail, seen, acc)
}

def removeDuplicates(xs: List[Int]): List[Int] =
  removeDuplicatesRec(xs, Set.empty, List.empty)

Python: Remove duplicates in a list pass into new list (Recursion , Recursive Solution: In this solution, we will use recursion to achieve having only unique elements in our Linked List. Approach 1: Iterative� Remove any duplicates from a List: mylist = ["a", "b", "a", "c", "c"] mylist = list (dict.fromkeys (mylist)) print(mylist) Try it Yourself ».

Here's a classic approach using an inner function and tail recursion. The tail recursion may not be necessary for small lists but it is easier for me to reason about.

  def removeDuplicates(xs : List[Int]) : List[Int] =  {
    @scala.annotation.tailrec
    def accumulator(xs: List[Int], acc: List[Int]):List[Int] = xs match {
      case Nil => acc
      case h::t if(!acc.contains(h)) => accumulator(t, h :: acc)
      case h::t if(acc.contains(h)) =>  accumulator(t, acc)
    }
    accumulator(xs, List[Int]())
  }

scala> removeDuplicates(List(1,2,3,4,6,3,2,7,9,4))
res16: List[Int] = List(9, 7, 6, 4, 3, 2, 1)

Of course, distinct is the preferred way to do this but this is a good exercise. distinct can be used to verify your solution though.

scala> List(1,2,3,4,6,3,2,7,9,4).distinct == removeDuplicates(List(1,2,3,4,6,3,2,7,9,4)).sorted
res21: Boolean = true

Remove Duplicates From a Sorted Linked List-Interview Problem, I want to remove duplicates from the list recursively using pattern matching with Scala here is my input val xs = List(1,2,3,4,6,3,2,7,9,4) Tried code: def� 1. Start from the leftmost character and if there are any duplicates in left corner remove them 2. Now, the first character is different from its adjacent character, recur for the remaining string of length n-1 3. After the recursive call, all the duplicates are removed from the remaining string,

Remove Duplicates from the List recursively - scala - html, Learn how to remove duplicates from a list in Elixir leveraging the Enum module and by writing a recursive function from scratch. Fork 0 remove duplicates in a list, using recursion instead of loops.

Remove Duplicates From List in Elixir, Remove duplicates from a sorted linked list Given a linked list sorted in increasing order, write a function which removes any duplicate nodes from the list by traversing the list only once. For example, if the list is {1, 2, 2, 2, 3, 4, 4, 5}, it should be converted to {1, 2, 3, 4, 5}.

Naive approach is to recursively remove all adjacent duplicates in the string till no duplicates is left in the string. The problem with this approach is that it might require (n+1)/2 passes in the worst case resulting in O(n 2 ) complexity.

Comments
  • is it the same way,to remove consecutive duplicates if (ys.head!==Nil && x==ys.head) removeConsecutiveDups(ys) else x::removeConsecutiveDups(ys)
  • List(1,1,1,1,1,1,2,2,2,2,4,4,4,4,5,6,7,7,7) for the above comment @user-unknown
  • @Krish: It's easy, to put the code into an editor, copy it, modify it a bit and then paste it into the REPL. If you enter ": pas"(te) into the editor, you can paste a block of code as a whole into the REPL (which is only sometimes important, but often visually more appealing) and - if it is accepted (hit Ctrl-D for signalling end-of-file for the pasting) test, if it works as expeceted.
  • To the content: ys.head!==Nil is probably a typo, meaning ys.head != Nil, but that's a type error, since the head of a List in never Nil, but if you correct that to if (ys != Nil && ..), it works as wanted.
  • I am getting stack overflow error for consecutive duplicates. case x::ys => if(ys!=Nil||x==ys.head) removeConsecutiveDups(ys) else x::removeConsecutiveDups(ys)
  • I was trying this in data bricks community notebook, there are some errors. This is too complicated is there anyway to optimize more
  • @Krish: You just need to import annotation._ and replace the two calls to removeDuplicates in removeDuplicatesRec with removeDuplicatesRec, then it works as intended, too.