Problem Statement

Recently when I came across this problem, it was presented to me in a very simple langaugae. And that really helped me in solving it without getting influenced or overwhelemed with the usecases where it can be applied.

I came across this on internet, and this was the problem statment -

Given a Matrix made of 1 & 0 find the number of connected 1s in it.

example -

Input :
        1, 1, 0, 0, 0
        0, 1, 0, 0, 1
        1, 0, 0, 1, 1
        0, 0, 0, 0, 0
        1, 0, 1, 0, 1

Output : 5

Above may look challanging, but it only make you think about a matrix and certain o/p from it. You are not forced to think any thing else. And with little effort you can solve it.

But same problem can be presented in following way -

Counting the number of connected components in an undirected graph

I can not say for you, but for me this brings in many other elements in the problem - graph and undirected and connected components . Now it may make you think how to store a grpah and what is connected component and what is undirected. For uninitiated or out of touch folks it may take some time to reach from here to matrix (where we staretd).

It can also accompany an image like this undirected graph

another variation

Counting the number of connected components in undirected graph stored in adjacency matrix

which brings in another new element in the mix called adjacency matrix .

More possible complex version of same problem!!

undirected graph application

undirected graphs are used in so many applications that it is very easy to give this problem a flavor of the application, where a complicated langauge will boil down to a same matrix . But all of redundant information will make it difficult for you to think just about the problem.

Solution

If you come across this problem which doesnt tells you matrix and 1s & 0s, then arriving to them is a challange. Either you need to be up to date with related data structures or reayd to spend time or energy to go through and design them.

But once you have boiled down to Matrix and connected 1s (some people also call them islands), Following is how I solved it.

  • Approach each element in matrix and find out if it is 1, if yes you found 1 island.
  • Evaluate all its valid neighbors and check if they are connected to it, if you find one connected 1, repeat this process with it.
  • Record each evaluated 1 in a sperate data structure and use it in first bullet to decide if element can be skipped.

Valid Neighbors

if each element is defined like this case class Element(r: Int, c: Int) and ROWS and COLS are size of matrix then neighbors are

def neighboringElements(e: Element): Seq[Element] = {
  val neighbors = Seq(Element(e.r-1, e.c-1), Element(e.r-1, e.c), Element(e.r-1, e.c+1),
                      Element(e.r, e.c-1), Element(e.r, e.c+1),
                      Element(e.r+1, e.c-1), Element(e.r+1, e.c), Element(e.r+1, e.c+1))

     neighbors filter ( n => n.r >= 0 && n.r < ROWS && n.c >= 0 && n.c < COLS)
}

Evaluate Neighbor

Define a set which will keep the record of element which we already evaluated.

val elementVisited = Set[Element]()

Now we can evaluate each element here -

 def visitNeighbors(e: Element) {
   neighboringElements(e) foreach { n =>
     if (!(elementVisited contains Element(n.r,n.c)) && (matrix(n.r)(n.c) == 1)) {
       elementVisited.add(n)
       visitNeighbors(n)
     }
   }
 }

Thats is it .. now we have all our pieces ready. Complete program will look like this…

import scala.collection.mutable.Set

object matrixIsland {
  val ROWS = 5
  val COLS = 5
  case class Element(r: Int, c: Int)
  //val matrix = Array(Array(1,0,0,1,0),Array(1,1,0,1,1),Array(1,0,1,1,0),Array(1,0,1,0,1),Array(1,1,1,1,0))
  //val matrix = Array(Array(1,0,1,0,0),Array(0,0,0,0,1),Array(0,1,0,0,0),Array(0,0,0,1,0),Array(0,1,0,0,0))
  val matrix = Array(Array(1,1,0,0,0),Array(0,1,0,0,1),Array(1,0,0,1,1),Array(0,0,0,0,0),Array(1,0,1,0,1))

  def neighboringElements(e: Element): Seq[Element] = {
    val neighbors = Seq(Element(e.r-1, e.c-1), Element(e.r-1, e.c), Element(e.r-1, e.c+1),
                        Element(e.r, e.c-1), Element(e.r, e.c+1),
                        Element(e.r+1, e.c-1), Element(e.r+1, e.c), Element(e.r+1, e.c+1))

    neighbors filter ( n => n.r >= 0 && n.r < ROWS && n.c >= 0 && n.c < COLS)
  }

  val elementVisited = Set[Element]()

  def visitNeighbors(e: Element) {
    neighboringElements(e) foreach { n =>
      if (!(elementVisited contains Element(n.r,n.c)) && (matrix(n.r)(n.c) == 1)) {
        elementVisited.add(n)
        visitNeighbors(n)
      }
    }
  }

  var count = 0

  def numberOfIslands(matrix: Array[Array[Int]]): Int = {
    var row = 0
    while (row < ROWS) {
      var col = 0
      while (col < COLS) {
        if (( matrix(row)(col) == 1 ) && !(elementVisited contains Element(row,col))) {
          println(s"Found a new island $row $col")
          count = count + 1
          elementVisited.add(Element(row,col))
          visitNeighbors(Element(row,col))
        } else {
          elementVisited.add(Element(row,col))
        }
        col = col + 1
      }
      row = row + 1
    }
    count
  }

  def main(args: Array[String]): Unit = {
    println(numberOfIslands(matrix))
  }
}

This code is also available in my git.

Thanks for reading. Keep things simple!!! Cheers!!!

Please note -

This is no way the most optimized solution, I will keep it optimizing in my repo. If something worth updating on blog I will do the same. I will try to make this scala code more functional I will provide a c++ version of this very soon