SDE - Intern

You have been given a 2D model of a country, with the help of a matrix containing 0 and 1. The 0’s in the model represent uninfected cells and 1’s represent the cells contaminated by a deadly spreading virus. Only a single wall can be built between any two cells of the model that are adjacent in all four directions, on their shared boundary.

With every passing night, the virus spreads to all the adjacent cells, unless the cells are blocked by a wall. You need to build walls in order to stop the virus from spreading in the whole country. Note that you can only install walls around only one region which is the affected area that threatens to infect the most uninfected cells of the matrix in one day.

Given the state of each cell, your task is to find the number of walls you used to stop as many cells as possible from being infected.

You are given a string 'STR'. Your task is to count the number of special palindromic substrings of size greater than 1 that the given string contains. A substring is said to be a special palindrome in the following two cases:

If all the characters in the substring are the same.

If the length of the substring is odd and only the middle element is different, while all the other characters are the same. 

Example:

“aba” is a special palindrome, while “abaa” is not

You have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.

Note :

Try to solve the problem in 'Single Scan'. ' Single Scan' refers to iterating over the array/list just once or to put it in other words, you will be visiting each element in the array/list just once.