CollegeStash

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

This is straight forward implementation of the DFS (Depth First Search) traversal algorithm using recursion.

 var obj = {
  baz: {
    foo: {
      bar: "5"
    },
    hell: {
      sin: "0"
    }
  },
  a: {
    b: "1"
  }
};

var hash = {};
var str = '';

var dfs = function(obj, str) {
  for (var key in obj) {
    if (obj.hasOwnProperty(key)) {
      if (typeof obj[key] === 'string')
        hash[str + key] = obj[key];
      else {
        dfs(obj[key], str + key + '.');
      }
    }
  }
};
dfs(obj, str);
console.log(hash);

var obj = {
  baz: {
    foo: {
      bar: "5"
    },
    hell: {
      sin: "0"
    }
  },
  a: {
    b: "1"
  }
};
var tracker = [];
var hashMap = {};
var hashKey = '';

function dfs(obj, tracker) {
  for (var key in obj) {
    if (obj.hasOwnProperty(key)) {

      if (typeof obj[key] == "string") {
        tracker.push(key);
        hashKey = appendArray(tracker);
        hashMap[hashKey] = obj[key];
        tracker.pop();
      } else {
        tracker.push(key);
        dfs(obj[key], tracker);
        tracker.pop();
      }
    }
  }
}
dfs(obj, tracker);
console.log(hashMap);

function appendArray(arr) {
  var ret = '';
  for (var i = 0; i < arr.length; i++) {
    ret = ret + '.' + arr[i];
  }
  return ret.substring(1, ret.length);
}

const test = {
  baz: {
    foo: {
      bar: "5"
    },
    hell: {
      sin: "0"
    }
  },
  a: {
    b: "1"
  }
};

const flatten = (obj, str = '', temp = {}) => {
  for (const [key, val] of Object.entries(obj)) {
    if (typeof val === 'object') {
      flatten(val, `${str}${key}.`, temp);
    } else {
      temp[`${str}${key}`] = val;
    }
  }
};

const output = {};
flatten(test, '', output);
console.log(output);

Output

Object {baz.foo.bar: "5", baz.another.bar: "0", a.b: "1"}

Demo

This problem can be solved using Kadane’s Algorithm.
We start by taking an empty array of zeros of size of the number of rows of input matrix.
We move from left to right columns and calculate max for every column and update up, down, left, right accordingly.
Input matrix mxn
Time = O(m*n*n)
Space = O(m)

package algos;

import java.util.HashMap;

class solution {

	public solution() {
	}

	public HashMap getMaxSum(int[] arr) {
		int max = arr[0], start = 0, end = 0, mstart = 0, mend = 0, currmax = arr[0];
		for (int i = 1; i < arr.length; i++) {

			if (arr[i] > arr[i] + currmax) {
				currmax = arr[i];
				start = i;
				end = i;
			} else {
				currmax = currmax + arr[i];
				end = i;
			}

			if (currmax > max) {
				max = currmax;
				mstart = start;
				mend = end;
			}
		}
		HashMap result = new HashMap();
		result.put("up", mstart);
		result.put("down", mend);
		result.put("max", max);
		return result;
	}

	public HashMap getMaxSubArray(int[][] matrix) {
		int max = matrix[0][0], left = 0, right = 0, up = 0, down = 0;
		int[] rowArray = new int[matrix.length];
		for (int cl = 0; cl < matrix[0].length; cl++) {
			for (int i = 0; i < matrix.length; i++) {
				rowArray[i] = 0;
			}
			for (int cr = cl; cr < matrix[0].length; cr++) {
				for (int row = 0; row < matrix.length; row++) {
					rowArray[row] += matrix[row][cr];
				}
				HashMap currentSet = getMaxSum(rowArray);
				if (currentSet.get("max") > max) {
					max = currentSet.get("max");
					up = currentSet.get("up");
					down = currentSet.get("down");
					left = cl;
					right = cr;
				}
			}
		}

		HashMap result = new HashMap();
		result.put("up", up);
		result.put("down", down);
		result.put("left", left);
		result.put("right", right);
		result.put("max", max);
		return result;
	}

}

public class kadanes {
	public static void main(String[] args) {
		solution sol = new solution();
		int[][] matrix = { { -2, -2, -2 }, { 2, 2, 2 }, { -2, -2, -2 } };
		HashMap result = sol.getMaxSubArray(matrix);
		System.out.println("max:" + result.get("max") + " up:" + result.get("up") + " down:" + result.get("down")
				+ " left:" + result.get("left") + " right:" + result.get("right"));
	}
}

Output

max:6 up:1 down:1 left:0 right:2