LeetCode: Number of Islands

Problem:

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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Analysis:

One simple solution for this problem is to use BFS or DFS. Simply scan the grid line by line, when you find a '1', DFS/BFS from it to search neighboring '1', until all the '1' cells connecting to it have been visited. Then you find one region. We call this procedure as "region growing", a popular algorithm in computer graphics. You should mark all visited '1' cells as visited. Then scan the grid again and find another unvisited '1' and do the above procedure again. When you scan the whole grid, you will get all islands.
Here I propose another solution. We give a ID for each island, beginning from count = 2 (use 'count' to represent the ID. 0 and 1 are used for water and land). First, we scan the grid line by line and when you find a cell with '1', you check its four neighbors. If its all neighbors are either '0' or '1', which means all its neighbors are not visited or water. Then you find a new island! Mark this island using count and increase the count by 1. Else, if you find some neighbors are not '0' or '1', this indicates the current cell is connected with some other islands. Pick the island which has the smallest ID and then mark the current cell using this ID and also remark all connected islands using this ID. In this way, you will merge all disjointed islands which are connected by the current cell. Keep doing this until you finish scanning the whole grid. 

C++:

class Solution {
public:
struct point{
int X;
int Y;
char key;
};
struct island{
vector<point> points;
char key;
};

map<char, island> islands;

void updateIsland(island isd, char key, vector<vector<char>> &grid){
for(int i = 0; i<isd.points.size(); i++){
isd.points[i].key = key;
grid[isd.points[i].Y][isd.points[i].X] = key;
islands[key].points.push_back(isd.points[i]);
}
islands.erase(isd.key);
}

int numIslands(vector<vector<char>> &grid) {
int h = grid.size();
if(h==0)
return 0;
int w = grid[0].size();

for(int i=0; i<h; ++i){
for(int j=0; j<w; ++j){
if(grid[i][j]=='1'){
grid[i][j] = 0;
}
else{
grid[i][j] = 1;
}
}
}

char count=2;
for(int i=0; i<h; ++i){
for(int j=0; j<w; ++j){
if(grid[i][j]==0){
vector<char> neib;
int left = j-1; int right = j+1; int top = i-1; int bottom = i+1;
if(left>=0 && grid[i][left]!=0 && grid[i][left]!=1){
neib.push_back(grid[i][left]);
}
if(right<=w-1 && grid[i][right]!=0 && grid[i][right]!=1){
neib.push_back(grid[i][right]);
}
if(top>=0 && grid[top][j]!=0 && grid[top][j]!=1){
neib.push_back(grid[top][j]);
}
if(bottom<=h-1 && grid[bottom][j]!=0 && grid[bottom][j]!=1){
neib.push_back(grid[bottom][j]);
}

if(neib.size()!=0){
char min=127;
for(int a=0; a<neib.size(); a++){
if(neib[a]<min)
min = neib[a];
}
for(int a=0; a<neib.size(); a++){
if(neib[a]!=min){
updateIsland(islands[neib[a]], min, grid);
}
}
grid[i][j] = min;
point p = {j, i, min};
islands[min].points.push_back(p);
}
else{
grid[i][j] = count;
point p = {j, i, count};
vector<point> pv;
island isld = {pv, count};
isld.points.push_back(p);
islands[count] = isld;
count++;
}

}
}
}

return islands.size();
}

};

LeetCode: RotateArray

Problem:

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Analysis:

First think about the problem which rotates the array to the right by 1 step. In this case, if we start from the end of the array, we only need to store the first element since only that number will be overwritten when rotation (nums[n01] will overwrite nums[0]). Now let us come back to the problem. We need to rotate k steps. We still start from the end of the array and we need to store the first k elements in a temporary array since these elements will be overwritten before they are rotated. This is just the same as the 1 step case we need to store the first element. 

C++:

void rotate(int nums[], int n, int k) {

        k = k%n; //we only need to rotate the array within k%n steps if k is greater than n

        int *temp = new int[k];

        for(int i=n-1; i>=0; i--){

            int offset = (i+k)%n;

            if(offset<k){

                temp[offset] = nums[offset]; //for the first k elements, we need to store them

            }

            if(i>=k){

                nums[offset] = nums[i]; //for the elements whose indices are greater or equal to k, we can just use the initial value in the array to rotate

            }

            else{

                nums[offset] = temp[i]; //for the elements whose indices are less than k, since they were already overwritten, we will use the temp array to rotate them

            }

            

        }

        

        

        delete []temp;

}

Cost:

O(n) for time and O(1) for space.

LeedCode: Reverse bits

Question:

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Analysis:

The idea is to extract each bit of the number by shifting the number right one bit per time and AND with 0x1. Each AND, we record the result bit as the least significant bit of the final result Res. In order to store all AND results, we need to left shift the Res one bit per AND operation and OR it with the AND result. 

C++:

uint32_t reverseBits(uint32_t n) {

         uint32_t res=0;

        for(int i=0; i<sizeof(n)*8; i++){

            res<<=1;

            res |= (n&0x1);

            n>>=1;

        }

        return res;

}


Cost:
O(1)

LeedCode: Number of 1 bits

Question:

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

Analysis:

This is a simple problem. Two ways: Either shifting the number to the right one bit per time and then AND with 0x1 and count the number of 1 for each AND operation. Or shifting the 0x1 left one bit per time and AND with the number. Then count the number of non-zero of the AND operation.

C++:

int hammingWeight(uint32_t n) {

        int res=0;

        int x=0x1;

        for(int i=0; i<sizeof(uint32_t)*8; i++){

            if((n&x)!=0)

                res++;

            x<<=1;

        }

        return res;

}

    

int hammingWeight2(uint32_t n) {

        int res=0;

        for(int i=0; i<sizeof(uint32_t)*8; i++){

            if((n&0x1)==1)

                res++;

            n>>=1;

        }

        return res;

}


Cost:
O(1)

LeetCode: Single Number II

Problem:

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Analysis:

We can extend this question: Every element appears N times and only one appears M times (M < N). Using a state machine, this problem is simple and straightforward. In our case, N = 3 and M = 1. Focusing on each bit of the number, we have N=3 states. Initially, that bit is 0, we have the initial state (0, 0). Then we scan the array and check that bit for each scanned number. If that bit first becomes 1, we have the state ( 0, 1). Next time it is 1, we change the state (0, 1) -> (1,0). If that bit becomes 1 for the N=3 times, the state will be back to (0, 0). Here is an example:

Array = {1, 2, 1, 1}.

Since N=3, we have three states. We can put all states into a array S[N]. (S[0] is NOT used here.)

Scan the array:

1) scan 1 (00000001):
                     S[2]: 00000000

                 S[1]: 00000001

                  S[0]: 11111111 (NOT used here)

                                           ^

                 state (0, 1) for this bit. Observe the state vertically. 

2) scan 2 (00000010):        
                      S[2]: 00000000

                   S[1]: 00000011

                   S[0]: 11111111 (NOT used here)

                                       ^

                                 state (0, 1) for this bit 

                                       ^

                                 state (0, 1) for this bit  

3) scan 1 (00000001):       
                      S[2]: 00000001

                   S[1]: 00000010

                   S[0]: 11111111 (NOT used here)

                                     ^

                            state (1, 0) for this bit 

                                      ^

                          state (0, 1) for this bit  

3) scan 1 (00000001):        
                      S[2]: 00000000

                   S[1]: 00000010

                   S[0]: 11111111 (NOT used here)

                                       ^

                        state back to (0, 0) for this bit 

                                       ^

                           state (0, 1) for this bit 

Therefore, we can get the single number which is S[1] = 2. 

As you can see, after we scan all the elements in the array, only S[M] will be has some bits which are not 0 and S[M] is the result. This is because except for the result number, other numbers will make all the bits back to the initial state and the final left bits which are not 0 will from the result number. 

Ok, now we can summary the algorithm. Each time we scan a number A[i] from the array A, we will 

update each state S[j] in array S. The bit of S[j] will be 1 if that bit of S[j] is previously 1 and the 

corresponding bit of A[i] is 0, or the bit of S[j-1] is 1 but the corresponding bit of A[i] is 1. This can 

be expressed as: S[j] = (S[j]&~A[i])|(S[j-1]&A[i]). If j==0, we set j-1=N-1.

C++:

We use N=3 and M = 1 for this problem.

#define N=3

#define M=1

class Solution {

public:

    int singleNumber(int A[], int n) {

        int S[M]; int t;

        S[0] = ~0;   //S[0] is used for the computation only. You can think S[0] will record the number which only appear 0 time

        for(int i=1; i<M; i++)

            S[i] = 0;

        

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

            t = S[N-1];

            for(int j=N-1; j>0; j--){

                S[j] = (S[j-1]&A[i])|(S[j]&~A[i]);

            }

            S[0] = (t&A[i])|(S[0]&~S[i]);

        }

        

        return S[M];

    }

};

Cost:

O(n)

LeedCode: Single World

Question:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Analysis:

Since each number appears twice, if we use XOR for these numbers, the result will be 0. Then 0 XORs with the number only appears only once, the result will be that number. Since XOR is commutative, we can XOR all numbers and the result will be single number. 

This method can be used for an array where every element appears even times and one number appears odd times and we can find out that number with odd appearance. 

C++:

class Solution {
public:
    int singleNumber(int A[], int n) {
        int res = 0;
        for(int i=0; i<n; i++)
        res ^= A[i];
     
        return res;
    }
};

Cost:
O(n)