CODEWITHSUNDEEP
scala
shiv455
shiv455

Reputation: 7764

Move zeros to the end of an Array

Im trying to solve below problem in scala

Input:[1,0,44,55,0,43,78,99]
output:[1,44,55,43,78,99,0,0]

here is what i have tried

def moveZeros(nums:Array[Int]): Array[Int] ={
    for(i<-0 until nums.length ; j<-0 until nums.length){
      if(nums(j)!=0)
      {
        var temp:Int = nums(i)
        nums(i)=nums(j)
        nums(j)=temp
      }

    }
    nums
  }

output :[0,0,1,44,55,78,99,43]

not expected output

Im looking for o(n) time complexity and O(1) space complexity solution

This is a leetcode problem https://leetcode.com/problems/move-zeroes/

Upvotes: 2

Views: 169

Answers (5)

lprakashv
lprakashv

Reputation: 1159

You can find all the immutable, functional, "true Scala" way of doing it in the above answers. But, considering the O(N) time-complexity and O(1) space complexity nothing beats a mutable, efficient, in-place algorithm!

Here is the implementation with Scala's array using foldLeft:

val arr = Array(1, 0, 44, 55, 0, 43, 78, 99)
val lastNonZero = arr.foldLeft(0) { 
  (zeros, elem) => if (elem != 0) { arr(zeros) = elem; zeros+1 } else zeros
}

(lastNonZero until arr.length).foreach{ i => arr(i) = 0 }

No extra space due to collection creation (not even .toList/.toArray) and no sorting.

enter image description here

Upvotes: 0

Ofek Hod
Ofek Hod

Reputation: 4024

Functional and immutable solution, also very simple to understand:

def moveZerosToEnd(input: Seq[Int]): Seq[Int] = {
    val ZERO = 0
    val zeroCount = input.count(_==ZERO)
    val removeZeros = input.filter(_!=ZERO)
    val zeroSuffix = Seq.fill(zeroCount)(ZERO)
    removeZeros ++ zeroSuffix
}

enter image description here

Time complexity: O(n): Fixed number of iterations over the sequence.
Space complexity: O(n): removeZeros, zeroSuffix and the output line may consume up to n space, so complexity is O(n).

Upvotes: 0

V-Lamp
V-Lamp

Reputation: 1678

This is a pure FP solution with O(n) time complexity and O(1) space complexity.

Unlike any of the other solutions so far, it can work for very large input that doesn't fit in memory:

object MoveZeros extends App {
  def moveZerosToEnd(input: Iterator[Int]): Iterator[Int] = {
    val endOfInputSignal = None
    val iteratorWithEndSignal: Iterator[Option[Int]] =
      input.map(Some(_)) ++ Iterator.single(endOfInputSignal)
    iteratorWithEndSignal.scanLeft((0, Iterator.empty[Int])) {
      case ((zerosCounter, _), value) => value match {
        case Some(value) =>
          if (value == 0)
            // Count zero and drop it
            (zerosCounter + 1, Iterator.empty)
          else
            (zerosCounter, Iterator.single(value))
        case None =>
          // Add counted zeros to the end
          (zerosCounter, Iterator.fill(zerosCounter)(0))
      }
    }.flatMap(_._2)
  }
  val input = List(1,0,44,55,0,43,78,99)
  val expected = List(1,44,55,43,78,99,0,0)
  val res = moveZerosToEnd(input.iterator)
    .toList // To list only for easy testing
  assert(res == expected)
  println(res)
}

Upvotes: 1

shiv455
shiv455

Reputation: 7764

i have rewritten my code with while loop it seems to work, lemme know if there is more elegant solution which satisfies linear time complexity and constant space complexity

  def moveZeros(nums: Array[Int]): Array[Int] = {
    var i = 0
    var j = 0
    while ( {
      i < nums.length && j < nums.length
    }) {
      if (nums(j) != 0) {
        val tmp = nums(i)
        nums(i)=nums(j)
        nums(j) = tmp
        i+=1
      }

      j += 1
    }
    nums

  }

Upvotes: 2

Guru Stron
Guru Stron

Reputation: 142448

You can try something like that:

nums.zipWithIndex
   .sortBy(t => if (t._1 == 0) Int.MaxValue else t._2)
   .map(_._1)

zipWithIndex will map your collection into sequence of tuples of element value and it's index (i.e. [(1, 0), (0, 21), (44, 2)] for start of your example array)

sortBy will perform the ordering by either index of element or Int.MaxValue

map will return map to the original element.

Upvotes: 2

Related Questions