(Scala) Leetcode 200. Memory limit exceeded

Question

I am using Scala to solve the problem documented here: https://leetcode.com/problems/number-of-islands/

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"] ] Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"], ["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"] ] Output: 3

I thought it was a simple application of Breadth (or depth) First Search. However, my program produces a Memory Limit Exceeded error at Leetcode. I also ran the program on my laptop. My Mac reports it uses more than 3 GB memory, even if I'd commented out 3 lines of the test case. What consumes so much memory in my code?

// Memory OVERFLOW !!? Why ??
class Leet0200 {
  def numIslands(grid: Array[Array[Char]]): Int = {
    var (y, x) = getPosition(grid)
    var c = 0
    val dirs = Array(
      Array(1, 0),
      Array(-1, 0),
      Array(0, 1),
      Array(0, -1)
    )
    while ((y, x) != (-1, -1)) {
      c += 1
      val queue = scala.collection.mutable.Queue[(Int, Int)]()
      queue.enqueue((y,x))
      while (queue.nonEmpty) {
        val me = queue.dequeue()
        val (me_y, me_x) = me
        grid(me_y)(me_x) = 'c'
        for (d <- dirs) {
          val (ny, nx) = (me_y + d(0), me_x+d(1))
          if (ny >= 0 && ny < grid.length
              && nx >= 0 && nx < grid(0).length
              && grid(ny)(nx) == '1') {
            queue.enqueue((ny, nx))
          }
        }
      }
      val newPos = getPosition(grid)
      y = newPos._1
      x = newPos._2
    }
    c
  }

  def getPosition(grid: Array[Array[Char]]): (Int, Int) = {
    for (y <- grid.indices) {
      for (x <- grid(0).indices) {
        if (grid(y)(x) == '1') return (y, x)
      }
    }
    (-1, -1)
  }

}

object Leet0200 {
  def main(args: Array[String]): Unit = {
    val leet = new Leet0200()
    println(
      leet.numIslands(Array(
    Array('1','1','1','1','1','0','1','1','1','1','1','1','1','1','1','0','1','0','1','1'),
        Array('0','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','0'),
        Array('1','0','1','1','1','0','0','1','1','0','1','1','1','1','1','1','1','1','1','1'),
        Array('1','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'),
        Array('1','0','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'),
        Array('1','0','1','1','1','1','1','1','0','1','1','1','0','1','1','1','0','1','1','1'),
        Array('0','1','1','1','1','1','1','1','1','1','1','1','0','1','1','0','1','1','1','1'),
        Array('1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','0','1','1'),
        Array('1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1'),
        Array('1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'),
        Array('0','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1'),
        Array('1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'),
        Array('1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'),
        Array('1','1','1','1','1','0','1','1','1','1','1','1','1','0','1','1','1','1','1','1'),
        Array('1','0','1','1','1','1','1','0','1','1','1','0','1','1','1','1','0','1','1','1'),
        Array('1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','0'),
        //Array('1','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','0','0'),
        //Array('1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'),
        //Array('1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'),
        Array('1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1')
    )))
  }
}

Honest feedback, LeetCode is not a good resource for learning Scala. All their problems are intended to be solved using very imperative algorithms, which will only teach you about basic syntax of the language. You will not learn about all the things that make Scala what it is, like Option the rich collections framework, Either and Try, prefer immutability, strong type system, etc. — Luis Miguel Mejía Suárez
– Luis Miguel Mejía Suárez, Commented Aug 22, 2020 at 22:06
While I tend to agree with Luis Miguel about LeetCode leaning toward imperative code, that isn't always the case. I solved this one in 15 lines of purely FP Scala. — jwvh
– jwvh, Commented Aug 23, 2020 at 4:30
@jwvh it would be actually quite interesting to see that solution, at least as a Scatie :) — Luis Miguel Mejía Suárez
– Luis Miguel Mejía Suárez, Commented Aug 23, 2020 at 5:44

John · Accepted Answer · 2020-08-22 22:29:26Z

You will have duplicates in your queue and they will snowball. When you put stuff into the queue, check if it's already in there by changing your queue to a Set.

For example, let's inspect a map:

Initially, getPosition() will return (0, 0).

0, 0: You will put into the queue: (0, 1) and (1, 0).
0, 1: You will put into the queue: (0, 2) and (1, 1). The queue now has: (1, 0), (0, 2), (1, 1)
1, 0: You will put into the queue: (2, 0) and (1, 1). The queue now has: (0, 2), (1, 1), (2, 0), (1, 1)

Note that there are now 2 x (1, 1) in the queue. Thus (1, 1) will be processed twice, hence adding 2 x the results to the queue (i.e. 2 x (2, 1) and 2 x (1, 2)). These results will duplicate into 4 x (2, 2). Hence a snowball effect.

This will be the snowball effect consuming memory in your queue. If you use a Set, then you won't have the snowball effect as the same position will not get added again.

An alternate solution is to use your marker when adding to the queue instead of when processing like the code below:

val queue = scala.collection.mutable.Queue[(Int, Int)]()
queue.enqueue((y,x))
grid(y)(x) = 'c'; // <--- moved to
while (queue.nonEmpty) {
    val me = queue.dequeue()
    val (me_y, me_x) = me
//  grid(me_y)(me_x) = 'c' // <--- moved from
    for (d <- dirs) {
        val (ny, nx) = (me_y + d(0), me_x+d(1))
        if (ny >= 0 && ny < grid.length
        && nx >= 0 && nx < grid(0).length
        && grid(ny)(nx) == '1') {
            queue.enqueue((ny, nx))
            grid(ny)(nx) = 'c'; // <--- moved to
        }
    }
}

Because you do the grid(ny)(nx) == '1' check, the same position will not be added to the queue multiple times.

Collectives™ on Stack Overflow

(Scala) Leetcode 200. Memory limit exceeded

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related