Find number of islands from a give 2D matrix of 0s and 1s

For a given 2D matrix of 0s and 1s, find number of islands where an island is defined as number of 1s together. For example for a 2D matrix below:

0,1,1,0

0,1,1,0

0,0,0,0

1,1,0,0

Number of islands is 2.

Solution is going to O(m*n) where m and n are number or rows and columns of the matrix respectively.

    int numIslands(int [][]a) {

        if (a == null || a.length == 0 || a[0].length == 0) {

            return 0;

        }

        int rows = a.length;

        int cols = a[0].length;

        boolean[][]b = new boolean[rows][cols];

        int counter = 0;

        for (int i = 0; i < rows; i++)

            for (int j = 0; j < cols; j++)

                if (a[i][j] == 1 && !b[i][j]) {

                    counter ++;

                    visitIsland(a, b, i, j);

                }

        return counter;

    }

    void visitIsland(int[][]a, boolean[][]b, int i, int j) {

        if (a == null || b == null

                || a.length == 0 || b.length == 0

                || a[0].length == 0 || b[0].length == 0

                || i < 0 || j < 0 || i == a.length || j == a[0].length)

            return;

        b[i][j] = true;

        if (i + 1 < a.length && a[i+1][j] == 1 && !b[i + 1][j])

            visitIsland(a, b, i + 1, j);

        if (j + 1 < a[0].length && a[i][j+1] == 1 && !b[i][j+1])

            visitIsland(a, b, i, j + 1);

        if (i - 1 >= 0 && a[i-1][j] == 1 && !b[i - 1][j])

            visitIsland(a, b, i - 1, j);

        if (j - 1 >= 0 && a[i][j-1] == 1 && !b[i][j-1])

            visitIsland(a, b, i, j-1);

    }

Finds unique value from a sorted array that has duplicates such as [1,1,2,2,3,3]

    /**
     * Finds unique value from a sorted array that has duplicates such as [1,1,2,2,3,3]<br/>
     * The approach is to have a O(log n) algorithm - perform operation as a binary search
     * @param a
     * @return
     */
    public static int findUnique(int []a) {
        if (a == null || a.length == 0) {
            throw new RuntimeException("Invalid parameter");
        }

        int length = a.length;
        if (length %2 == 0) return Integer.MIN_VALUE;

        // If only single element array, return the element
        if (length == 1) return a[0];

        // This is to handle the case when the unique element is either first or last.
        if (a[0] != a[1]) return a[0];
        if (a[length - 1] != a[length - 2]) return a[length - 1];
     
        int s = 0, e = length - 1;

        // Else perform binary search
        for (; s < e;) {
            int m = (s + e) / 2;
            int mid = a[m];

            if (m == s || m == e) return mid;

            if (mid == a[m ^ 1]) {
                s = m + 1;
            } else {
                e = m;
            }
        }

        return a[s];
    }

Find permutations of a string

import java.util.*;
public class Permutation {
    public static void main(String[] args) {
        Permutation s = new Permutation();
        List<String> list = s.permutation("abc");
        System.out.println(list);

    }

    /**
     * Function that returns a list of all permutations of a word<br/>
     * The logic is that:<br/>
     * First remove the first character.<br/>
     * Find the permuatations of remaining word.<br/>
     * For each of those words, put the the first character at every location<br/>
     * Return the final list
     * @param word
     * @return List
     */
    public List<String> permutation(String word) {
        if (word == null || word.length() == 0) {
            return new ArrayList<String>();
        }

        // If word is of single character, create a list and return
        if (word.length() == 1) {
            return Arrays.asList(word);
        }

        // Recurse until we get list of single character word list
        List<String> w = permutation(word.substring(1));

        // Fetch first character of original word
        Character ch = word.charAt(0);

        List<String> result = new ArrayList<String>();

        // Iterate over the list returned as part of recursion and append to each character of the words in the list.
        for(String s : w) {
            result.addAll(append(s, ch));
        }

        // Return the resultant string
        return result;
    }


    private List<String> append(String s, Character ch) {
        if (s == null) {
            return new ArrayList<String>();
        }

        if (ch == null) {
            return Arrays.asList(s);
        }

        // Iterate over the string and append character at each point in the string
        // Note that since we will have to append to the end, hence we will have to special case the last character too.
        List<String> result = new ArrayList<String>();
        for (int i = 0; i <= s.length(); i++) {
            String temp = s.substring(0,i) + String.valueOf(ch);
            if (i < s.length()) {
                temp += s.substring(i);
            }

            result.add(temp);
        }

        return result;
    }

}

Regular expression implementation for '*' and '?' wildcard characters

Assuming we have two string - a normal string which will be matched against a regular expression string. The idea is simple: iterate through both string simultaneously. If:

• current char in regex is '?', skip current characters from both strings
• current char in regex is '*', find the next matching character in original string
• else match the current character.

The implementation of the above idea is captured in code at the link

Sliding window implementation:

Problem: Given an array and subarray size, find the max. sum from subarrays.
Solution: 
Naive solution is to iterate through all the subarrays and find the sums. Each time, compare the sum with the previous max and update accordingly. The solution is quadratic in nature.
A better solution implementing sliding window where in each iteration, remove the first integer in the last array and add the value of the newly added array in the subarray.
An implementation of it is here in the link.

SOLID design principles

To understand what these principles are, I have kept them inline comments in the code. I will keep updating the code portions that will act as examples to quickly understand each of them.
The format of the code is as follows:
SOLID principles one line definitions
Pick each letter from SOLID, i.e., each principle and create separate namespace followed by partition line as a series of "=".

namespace SOLIDDesignPrinciples
{
    // S: Single responsibility principle (SRP)
    // A class/method should concentrate on one task - doing one thing only

    // O: Open/Close principle (OCP)
    // A component should be open for extension but close for change
    // Change a class behavior using inheritance/polymorphism

    // L: Liskov Substitution principle (LSP)
    // S is derived from B then object of B can be replaced with objects of S

    // I: Interface Segregation principle (ISP)
    // No client should be forced to use/depend on methods it doesn't use. Keep interfaces small and cohesive

    // D: Dependency Inversion principle (DIP)
    // A. High level modules should not depend upon low level modules. Both should depend upon abstractions.
    // B. Abstractions should not depend upon details. Details should depend upon abstractions.
    // Use lots of interfaces and abstractions
    class MainClass
    {
        public static void Main (string[] args)
        {
            Console.WriteLine ("Hello World!");
        }
    }
}

====================================================================
namespace SOLIDDesignPrinciples
{
    namespace SingleResponsibilityPrinciple
    {
        /// <summary>
        /// Single responsibility - this class will act as a single responsibility class.
        /// As an example, let it be an employee class. There can be many implementations to it,
        /// where in the class, in addition to keeping employee's basic info, we will calculate bonus, taxes etc.
        /// Note that this class becomes complex if we calculate information related to the basic information.
        /// Rather, we can have separate classes for each job.
        /// We will have two classes in order to follow SRP.
        /// </summary>
        public class EmployeeInformation
        {
            public int Salary { get; set; }

            public int Age { get; set; }

            public string Name { get; set; }

            public EmployeeInformation ()
            {
            }
        }
   
        public class Calculations
        {
            private EmployeeInformation empInfo;

            public EmployeeInformation EmployeeInformation
            { get; private set; }

            public Calculations (EmployeeInformation empInfo)
            {
                this.empInfo = empInfo;
            }

            public int Tax { get; private set; }

            public void CalculateTax ()
            {
                // Implementation here
            }

            public int Bonus { get; private set; }

            public void CalculateBonus (int percentage)
            {
                // Implementation here
            }
        }
    }
}
====================================================================

3SUM algorithm

Problem is:
Given an array of integers, find subset of 3 elements of the array such that sum of those three elements is zero.
Brute force:
1. Find all 3-element subsets in the set S.
2. For each subset, find some of each subset
3. Print the one whose sum is zero
Alternative and improved:
1. Sort the list.
2. Following is the algorithm

-25 -10 -7 -3 2 4 8 10  (a+b+c==-25)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-3)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==2)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==0)

where bold one is 'a' and red ones are 'b' and 'c' - shown in the parenthesis on the right.

Following is the working code:

class tuple

{

private:

int i;

int j;

int k;

public:

tuple() { i = 0; j = 0; k = 0; }

tuple(int a, int b, int c) { i = a; j = b; k = c; }

int GetI() { return i; }

int GetJ() { return j; }

int GetK() { return k; }

void SetI(int a) { i = a; }

void SetJ(int b) { j = b; }

void SetK(int c) { k = c; }

};

int compare (const void* a, const void *b)

{

return (*(int*)a - *(int*)b);

}

tuple* SUM (int *a, int n)

{

if (a == NULL) return NULL;

if (n <= 2) return NULL;

qsort (a, n, sizeof(int), compare);

cout << "Sorting complete \n";

cout << "Sorted array is:\n";

for (int i = 0; i < n; i++)

cout << a[i] << '\t';

cout << endl;

for (int i = 0; i < n - 3; i++)

{

int j = i + 1;

int k = n - 1;

while (j < k)

{

if (a[i] + a[j] + a[k] == 0)

return new tuple(i, j, k);

if (a[i] + a[j] + a[k] < 0)

j++;

if (a[i] + a[j] + a[k] > 0)

k--;

}

}

return NULL;

}