Month: April 2017

Given an array of integers, move all the zeroes to the beginning of the array, leaving the order of the other integers unaltered. This operation has to be done in place.

Time Complexity O(n)
Java

package algos;

public class moveZeroesToStart {

	public static int[] moveToStart(int[] input) {
		int n = input.length - 1, count = n-1;
		for (int i = n - 1; i >= 0; i--) {
			if (input[i] != 0) {
				input[count--] = input[i];
			}
		}

		while (count >= 0) {
			input[count--] = 0;
		}

		return input;
	}

	public static int[] moveToEnd(int[] input) {
		int n = input.length, count = 0;
		for (int i = 0; i < n; i++) {
			if (input[i] != 0) {
				input[count++] = input[i];
			}
		}

		while (count < n) {
			input[count++] = 0;
		}

		return input;
	}

	public static void main(String[] args) {

		int[] arr = { 3, 2, 0, 1, 5, 0, 0 };
		arr = moveToStart(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
                System.out.println();
		arr = moveToEnd(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
}

Output

0
0
0
3
2
1
5

3
2
1
5
0
0
0

JavaScript

var moveToStart = function(input) {
  var n = input.length - 1;
  var count = n-1;
  for (var i = n - 1; i >= 0; i--) {
    if (input[i] !== 0) {
      input[count--] = input[i];
    }
  }
  while (count >= 0) {
    input[count--] = 0;
  };
  return input;
};

var moveToEnd = function(input) {
  var n = input.length;
  var count = 0;
  for (var i = 0; i < n; i++) {
    if (input[i] !== 0) {
      input[count++] = input[i];
    }
  }
  while (count < n) {
    input[count++] = 0;
  };
  return input;
};

var arr = [3, 2, 0, 1, 5, 0, 0];
arr = moveToStart(arr);
for (var i = 0; i < arr.length; i++) {
  console.info(arr[i]);
}
console.log();
arr = moveToEnd(arr);
for (var i = 0; i < arr.length; i++) {
  console.info(arr[i]);
}

Demo

Follow Up
To do the opposite and move zeroes to the end of the array we need to start from the beginning with the counter at 0.

Calculate the maximum amount of water that can held within a bar graph without overflow.
The amount of water that can be held at any point is the difference of the minimum of the maximum of left bars and maximum of right bars and the height of that point.
If we don’t precompute the maximum values on left and right for every index, the time complexity becomes O(n^2). So we go with the precompute option.

Time Complexity O(n)
Space Complexity O(n)

Code

package algos;

import java.lang.Math;

public class maxWater {
	public static void main(String[] args) {
		int[] input = { 5, 1, 3, 4 };
		int len = input.length;
		int[] left = new int[len];
		int[] right = new int[len];
		int rightMax = input[len - 1], leftMax = input[0];
		for (int i = 1; i < len - 1; i++) {
			leftMax = Math.max(leftMax, input[i]);
			left[i] = leftMax;
			rightMax = Math.max(rightMax, input[len - 1 - i]);
			right[len - 1 - i] = rightMax;
		}
		int count = 0;
		for (int i = 1; i < len - 1; i++) {
			count += Math.min(left[i], right[i]) - input[i];
		}
		System.out.println(count);
	}
}

Output

4

The following code handles negatives as well.

Time Complexity O(n)
Space Complexity O(1)

Code

package algos;

public class maxThreeProd {
	public static int maxThree(int[] input) {
		if (input.length <= 3) {
			int ret = 1;
			for (int i = 0; i < input.length; i++) {
				ret *= input[i];
			}
			return ret;
		}

		int m1 = Integer.MIN_VALUE;
		int m2 = Integer.MIN_VALUE;
		int m3 = Integer.MIN_VALUE;
		int l1 = Integer.MAX_VALUE;
		int l2 = Integer.MAX_VALUE;
		for (int i = 0; i < input.length; i++) { if (input[i] > m1) {
				m3 = m2;
				m2 = m1;
				m1 = input[i];
			} else if (input[i] > m2) {
				m3 = m2;
				m2 = input[i];
			} else if (input[i] > m3) {
				m3 = input[i];
			}

			if (input[i] < l1) {
				l2 = l1;
				l1 = input[i];
			} else if (input[i] < l2) {
				l2 = input[i];
			}
		}

		return Math.max(l1 * l2 * m3, m1 * m2 * m3);

	}

	public static void main(String[] args) {
		int[] input = { 1, 5, 3, 2 };
		if (input.length == 0)
			System.out.println("null");
		else
			System.out.println(maxThree(input));
	}
}

Output

30

We use dynamic programming to solve this.
Space complexity = O(2*n)
Time complexity = O(n^3).

public class maxSquareX {
    public static void main(String[] args) {

        char[][] input = { 
                    { 'X', '0', 'X', 'X', 'X' },
                    { 'X', 'X', 'X', 'X', 'X' },
                    { 'X', 'X', '0', 'X', '0' },
                    { 'X', 'X', 'X', 'X', 'X' },
                    { 'X', 'X', 'X', '0', '0' },
                  };

        int[][] rows = new int[input.length][input[0].length];
        int[][] cols = new int[input.length][input[0].length];

        for (int i = 0; i < input.length; i++) {
            for (int j = 0; j < input[0].length; j++) {
                if (input[i][j] == '0') {
                    rows[i][j] = cols[i][j] = 0;
                } else {
                    rows[i][j] = (i == 0) ? 1 : rows[i - 1][j] + 1;
                    cols[i][j] = (j == 0) ? 1 : cols[i][j - 1] + 1;
                }
            }
        }
        int max = 1; // since this is the minimum answer we can get int small; 
        // Start from bottom right 
        for (int i = input.length - 1; i >= 0; i--) {
            for (int j = input[0].length - 1; j >= 0; j--) {
                small = Math.min(rows[i][j], cols[i][j]);
                while (small > max) {
                    // we use index [j - small + 1] because small might be
                    // input.length + 1 and when that is subtracted from 'j' we
                    // might get an 'ArrayIndexOutOfBoundsException'.
                    if (small <= rows[i][j - small + 1] && small <= cols[i - small + 1][j]) {
                        max = small;
                    } else
                        small--;
                }
            }
        }
    }
}

Output

3

Bounded Knapsack (1/0) Solution in Java using Dynamic Programming
There are few items with weights and values, we need to find the items that contribute the maximum value that can be stored in knapsack of a particular capacity.
There are only 2 choices for each item, i.e. it can either be included or excluded from the bag.
Space complexity O(i*(capacity+1))
Time complexity O(i*(capacity+1))

package algos;
import java.math.MathContext;
import java.util.ArrayList;

class item {
    public int weight;
    public int value;
    public item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

public class knapsackB {

    public static void main(String[] args) {
        item[] items = {
            new item(1, 1),
            new item(3, 4),
            new item(4, 5),
            new item(5, 7)
        };

        int bag = 7;
        int[][] result = new int[items.length][bag + 1];


        for (int it = 0; it < items.length; it++) {
            for (int i = 0; i <= bag; i++) {

                if (items[it].weight <= i) {
                    if (it != 0)
                        result[it][i] = Math.max(result[it - 1][i], items[it].value + result[it - 1][i - items[it].weight]);
                    else result[it][i] = items[it].value;
                } else {
                    // use previous
                    if (it != 0)
                        result[it][i] = result[it - 1][i];
                    else result[it][i] = 0;
                }

            }
        }

      // Printing Result matrix 
       for (int it = 0; it < items.length; it++) {
            for (int i = 0; i <= bag; i++) {
                System.out.print(result[it][i] + " ");
            }
            System.out.println("");
        }

        int itemIndex = items.length - 1;
        int weightIndex = bag;
        
         // Printing the answer
        System.out.println(result[itemIndex][weightIndex]);

        ArrayList < item > finalBag = new ArrayList < item > ();
        while (weightIndex != 0) {
            if (result[itemIndex][weightIndex] != result[itemIndex - 1][weightIndex]) {
                // include this
                finalBag.add(items[itemIndex]);
                weightIndex = weightIndex - items[itemIndex].weight;
                itemIndex--;
            } else {
                itemIndex--;
            }
        }
  
       // Printing the bag
        for (item i: finalBag) {
            System.out.println(i.value);
        }


    }
}

Output

0 1 1 1 1 1 1 1 
0 1 1 4 5 5 5 5 
0 1 1 4 5 6 6 9 
0 1 1 4 5 7 8 9
9
5
4

Using Recursion

This is very inefficient.

/* A Naive recursive implementation of 0-1 Knapsack problem */
class Knapsack
{
 
    // A utility function that returns maximum of two integers
     static int max(int a, int b) { return (a > b)? a : b; }
      
     // Returns the maximum value that can be put in a knapsack of capacity W
     static int knapSack(int W, int wt[], int val[], int n)
     {
        // Base Case
    if (n == 0 || W == 0)
        return 0;
      
    // If weight of the nth item is more than Knapsack capacity W, then
    // this item cannot be included in the optimal solution
    if (wt[n-1] > W)
       return knapSack(W, wt, val, n-1);
      
    // Return the maximum of two cases: 
    // (1) nth item included 
    // (2) not included
    else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                     knapSack(W, wt, val, n-1)
                      );
      }
 
   public static void main(String args[])
   {
        int val[] = new int[]{60, 100, 120};
        int wt[] = new int[]{10, 20, 30};
    int  W = 50;
    int n = val.length;
    System.out.println(knapSack(W, wt, val, n));
    }
}

Output

220

Time Complexity = O(2^n).

The recursion tree is for following sample inputs.
wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}

                       K(3, 2)         ---------> K(n, W)
                   /            \ 
                 /                \               
            K(2,2)                  K(2,1)
          /       \                  /    \ 
        /           \              /        \
       K(1,2)      K(1,1)        K(1,1)     K(1,0)
       /  \         /   \          /   \
     /      \     /       \      /       \
K(0,2)  K(0,1)  K(0,1)  K(0,0)  K(0,1)   K(0,0)

Bounded Knapsack with Fractions allowed
In the above problem if we are allowed to include fractions, then we sort the items based on their value to weight ratios in descending order and include them in the knapsack, until it is full.

package algos;
import java.util.ArrayList;
import java.util.PriorityQueue;

class item {
    public int weight;
    public int value;
    public item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }

public class knapsackF {
    public static void main(String[] args) {
        PriorityQueue < item > queue =
            new PriorityQueue < item > (4, (a, b) - > -Double.compare(a.value / (double) a.weight, b.value / (double) b.weight));
        queue.add(new item(1, 1));
        queue.add(new item(3, 4));
        queue.add(new item(4, 5));
        queue.add(new item(5, 7));

        ArrayList < item > bag = new ArrayList < item > ();
        int capacity = 7;
        double val = 0;
        item current;
        while (!queue.isEmpty() && capacity != 0) {
            current = queue.poll();
            bag.add(current);
            if (current.weight <= capacity) {
                val += current.value;
                capacity -= current.weight;
            } else {
                val += ((capacity / (double) current.weight) * current.value);
                capacity = 0;
            }
        }
        System.out.println(val);
        for (item i: bag) {
            System.out.println(i.value);
        }
    }
}

Output

9.666666666666666
7
4

Unbounded Knapsack solution
In this approach we use Dynamic programming to store the capacities incrementally to get the required maximum value at capacity.
Time complexity = O(i*(c+1))
Space complexity = O(c+1)

package algos;

class item {
    public int weight;
    public int value;
    public item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }

public class knapsackU {
    public static void main(String[] args) {
        item[] items = {
            new item(1, 1),
            new item(3, 4),
            new item(4, 5),
            new item(5, 7)
        };
        int capacity = 7;
        int[] capacityList = new int[capacity + 1];

        for (int cap = 0; cap <= capacity; cap++) {
            for (item i: items) {
                if (i.weight <= cap) {
                    capacityList[cap] = Math.max(capacityList[cap], i.value + capacityList[cap - i.weight]);
                }
            }
        }
        System.out.println(capacityList[capacity]);
    }
}

Output

9

Unbounded Knapsack with Fractions allowed
This is a straightforward implementation, as we need to find the maximum ratio among the given items (value/weight) and then multiply it with the capacity of the bag.
Time complexity = O(i)
Space complexity = O(1)

package algos;
import java.math.MathContext;

class item {
    public int weight;
    public int value;
    public item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }

public class knapsackUF {
	public static void main(String[] args) {
		item[] items = {new item(1,1), new item(3,4), new item(4,5), new item(5,7)};
	    int capacity = 7;
	    double maxRatio = 0;
	    
	 for(item i: items) {
		 maxRatio = Math.max(maxRatio, i.value/(double) i.weight);
	 }
	 System.out.println(maxRatio*capacity);
	}
}

Output

9.799999999999999