Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Count The Planes (Main Thread)

Here is the interview question prompt, presented for reference.

Assume that we are building software to determine how many planes are in the sky.

The data that we have on planes currently in the air comes in the form of a grid, modeled by a matrix array. See below:

[
  ['.', '.', '.', 'P'],
  ['.', '.', '.', 'P'],
  ['P', 'P', '.', 'P'],
  ['.', '.', '.', 'P']
]

Within that matrix, the dots (.s) represent available airspace. The Ps that are neighboring each other model one plane each. So in the above example, there are exactly 2 planes.

Given a multi-dimensional array of .s and Ps exclusively, can you find the number of planes that there are in the sky? Planes may only be placed horizontally or vertically. A diagonal plane like this would not count as one plane. Instead, there will be 3 separate planes.

[
  ['.', '.', 'P'],
  ['.', 'P', '.'],
  ['P', '.', '.']
]

Could you accomplish this in one pass?

const sky = [
  ['.', '.', '.', 'P'],
  ['.', '.', '.', 'P'],
  ['P', 'P', '.', 'P'],
  ['.', '.', '.', 'P']
]

numOfPlanes(sky);
// 2

Constraints

  • Total number of elements in the matrix <= 100000
  • The elements will consist only of . and P characters
  • The matrix can be empty
  • Expected time complexity : O(n * m) where n and m are number of rows and columns respectively
  • Expected space complexity : O(1)

You can see the full challenge with visuals at this link.

Challenges • Asked almost 2 years ago by DanieLao

Jake from AlgoDaily Commented on Aug 02, 2019:

This is the main discussion thread generated for Count The Planes.

DanieLao Commented on Aug 02, 2019:

Brilliant solution!

Zestymonk Commented on Mar 10, 2020:

i didnt get should we add diagonal ones as seperate or as one?

Rahat Zaman Commented on Feb 16, 2021:

Hi Zestymonk,
There was an issue with the problem specification that you are refering to. We have now fixed it and also updated the solution.