Maximum Sum Increasing Subsequence Dynamic Programming

Problem: Given an array of numbers, Find an increasing subsequence with the maximum sum. Ex: {4,6,1,3,8,4,6} will give {4,6,8} with maximum sum of 18 Basic idea is to traverse the array left to right and check if previous values are smaller than the current value. If they are smaller they can be added to current value to get the sum for current element. If the sum is greater than the existing current sum, update the value.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

public static int[] maxSumIncSubSeq(int[] n){ int[] t1 = new int[n.length]; int[] t2 = new int[n.length]; for(int i = 0; i < n.length; i++){ t1[i] = n[i]; t2[i] = i; } for(int i = 0; i < n.length; i++){ for (int j = 0; j <= i; j++){ if(n[j] < n[i] && t1[i] < n[i] + t1[j]){ t1[i] = n[i] + t1[j]; t2[i] = j; } } } int max = Integer.MIN_VALUE; int maxInd = -1; List<Integer> result = new ArrayList<Integer>(); for(int i = 0; i < n.length; i++){ if(max < t1[i]){ max = t1[i]; maxInd = i; } } System.out.println("Max is : " + max); while(maxInd >= 0){ result.add(n[maxInd]); if(maxInd == 0){ break; } maxInd = t2[maxInd]; } int [] r = new int[result.size()]; for(int i = 0; i < result.size(); i++){ r[i] = result.get(i); } return r; }

Different ways to add parenthesis

Problem : Given a string of numbers and operators return all possible results from computing all the different possible ways to group numbers and operators, all the valid operators are '+',  '-',  '*'.
Basic Idea is to start from left and move towards right recursively while calculating the result of every pair bases on the operator in between them. for ex :
(2-(1-1))
(2-1) -1)
Example 1
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2*3-4*5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

public class Solution { public List<Integer> diffWaysToCompute(String input) { List<Integer> result = new ArrayList<Integer>(); for(int i = 0;i < input.length(); i++){ if(input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*'){ List<Integer> left = diffWaysToCompute(input.substring(0,i)); List<Integer> right = diffWaysToCompute(input.substring(i+1)); for(int j = 0; j < left.size(); j++){ for(int k = 0; k < right.size(); k++){ switch (input.charAt(i)){ case '+' : result.add(left.get(j) + right.get(k)); break; case '-' : result.add(left.get(j) - right.get(k)); break; case '*' : result.add(left.get(j) * right.get(k)); break; default : break; } } } } } if(result.size() == 0 ){ result.add(atoi(input)); } return result; } public static int atoi(String str) { if (str == null || str.length() < 1) return 0; // trim white spaces str = str.trim(); char flag = '+'; // check negative or positive int i = 0; if (str.charAt(0) == '-') { flag = '-'; i++; } else if (str.charAt(0) == '+') { i++; } // use double to store result double result = 0; // calculate value while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') { result = result * 10 + (str.charAt(i) - '0'); i++; } if (flag == '-') result = -result; // handle max and min if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE; if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE; return (int) result; } }

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Basic idea is to scan the string from left to right and push left parenthesis in a stack and pop them whenever a right parenthesis is encountered and check for valid pair, If its not a valid pair then return false. At the end of the scan, stack should be empty as all left parenthesis should have been popped out to match for valid pairs with right pantheists. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

public class Solution { public boolean isValid(String s) { if(s == null || s.length() <2 ){ return false; } Stack stack = new Stack(); for(int i=0; i < s.length(); i++){ if(isLeftParanthesis(s.charAt(i)) ){ stack.push(s.charAt(i)); }else if(isRightParanthesis(s.charAt(i))){ if(!stack.isEmpty()){ char top = (char)stack.pop(); if(!isValidPair(top,s.charAt(i))){ return false; } }else{ return false; } } } if(!stack.isEmpty()){ return false; } return true; } public boolean isLeftParanthesis(char c){ return (c == '(' || c == '{' || c == '['); } public boolean isRightParanthesis(char c){ return (c == ')' || c == '}' || c == ']'); } public boolean isValidPair(char c1, char c2){ if(c1 == '(' && c2 == ')'){ return true; } if(c1 == '{' && c2 == '}'){ return true; } if(c1 == '[' && c2 == ']'){ return true; } return false; } }

Find Max Sum in a pyramid traversal

Problem : Given an array of n integers. find the max sum while traversing from parent to children when elements are arranged as a pyramid.
For ex: input = [5, 4, 12, 3, 11, 7, 2, 8, 1, 9 ]
     index = [0, 1, 2,  3, 4,  5, 6, 7, 8, 9 ]
        5
      4  12
    3  11   7
  2   8   1   9

 Output : 36
  5 + 12 + 11 + 8

 valid move: 4 to 3 or 11
 invalid move: 4 to 5 / 12 / 7 / 2
Basic idea is that at each level the number of elements are level +1.
Level 0= 1 element
Level 1= 2 elements
Level n-1 = n elements
Level n = n+1 elements.

For an elements its children would be at (index of element + level +1) and (index of an element +2) .
Traverse all levels recursively, find the max among both of its children, add it to the max and pass the new index and level to next recursion. Do this till index+level+2 < array.size.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public long findMaxSum(List<Integer> input) { if(input == null || input.size() < 1){ return 0; } return findMaxSum(input, 0, 0,input.get(0)); } public long findMaxSum(List<Integer> input, int level, int parentIndex, int sum){ if(parentIndex+level+2 < input.size()){ parentIndex = (input.get(parentIndex+level+1) > input.get(parentIndex+level+2)) ? parentIndex+level+1 : parentIndex+level+2; sum = sum + input.get(parentIndex); return findMaxSum(input, ++level, parentIndex, sum); }else{ return sum; } }

Find Single Number

Problem : Given an array of integers, every element appears twice except one. Find that single one in linear time. Can you do it in without using extra memory ?
Basic idea is to scan the array you take a xor of each element. Duplicate elements will cancel each other.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public class Solution { public int singleNumber(int[] nums) { if(nums == null){ return 0; } if(nums.length == 1){ return nums[0]; } int result =0; for(int i=0; i < nums.length; i++){ result = result^nums[i]; } return result; } }

2 Majority elements in an array

Problem : Given an array of n integers. Find all the elements which occur more than n/3 times in the array.

Basic idea is to use negation technique. There can be only 2 elements which can exist more than n/3 times in a given array. Take two temp variables and two counters and scan the array. Every time a new elements is encountered, store it in the temp variable and increase the counter by one. If next element is same as one of the two temp variables then increase the respective counter. If next element is different then decrease the counter, If one of the counter reaches 0 then replace that element with the new found element and set the counter to 1(This works on the same technique of negation of elements in case 1 element was present more than n/2 times). If we consider each element occurring for more than n/3 times and count them and decrease the count when we encounter a different which is less than n/3 times. In the end we will be left with at least 1 count of elements which exist more than n/3 times. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

public List<Integer> majorityElement(int[] nums) { int countCheck = (nums.length/3) +1; int [] elements = new int[2]; int count1 = 0; int count2 =0; List<Integer> arrayList = new ArrayList<Integer>(); if(nums.length <1){ return arrayList; } if(nums.length == 1){ arrayList.add(nums[0]); return arrayList; } if(nums.length == 2 && nums[0] == nums[1]){ arrayList.add(nums[0]); return arrayList; } if(nums.length == 2 && nums[0] != nums[1]){ arrayList.add(nums[0]); arrayList.add(nums[1]); return arrayList; } for(int i = 0; i< nums.length; i++){ if(nums[i]== elements[0] || nums[i]==elements[1]){ if(nums[i] == elements[0]) count1++; else if(nums[i]== elements[1])count2++; }else if(count1==0){ elements[0] = nums[i]; count1++; }else if(count2 ==0){ elements[1]=nums[i]; count2++; }else { if(count1 >0){ count1--; } if(count2>0){ count2--; } } } count1=0; count2=0; System.out.println(elements[0]); System.out.println(elements[1]); for(int i=0; i< nums.length; i++){ if(elements[0]==nums[i]) count1++; if(elements[1] == nums[i]) count2++; } if(elements[0] != elements[1]){ if(count1 > (nums.length)/3 && nums.length>2){ arrayList.add(elements[0]); } if(count2 > (nums.length)/3 && nums.length >2){ arrayList.add(elements[1]); } }else{ arrayList.add(elements[0]); } return arrayList; }

Minimum cost path

Problem : Given a matrix and start point and end point what is the minimum cost to reach from start point to end point. Given that you can only go right or down.

Basic idea is that for each node you can only either come from up or down. Start from 0,0 and for each node check the minimum path from both directions. For row = 0, there is only right direction to go so keep adding the cost . for column = 0 there is only down direction to go. For rest of the T[i][j] check T[i][j] = T[i][j] +Min( T[i-1][j]], T[i][j-1] ). This will give the total sum for each node in the matrix. To back track and find the path. check where the sum came from and add that value in the array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

public int[] minimumCostPath(int[][] input){ // total number of nodes traversed would be m+n-1 if(input.length < 1 || input[0].length < 1){ return new int [] {0}; } int[] result = new int[input.length + input[0].length - 1]; int total = input[0][0]; for(int i = 0; i < input.length; i++){ for(int j = 0; j< input[i].length; j++){ if(i == 0 && j != 0){ input[i][j] = input[i][j] + input[i][j-1]; total = input[i][j]; }else if(j != 0 && i != 0){ input[i][j] = Math.min(input[i][j] + input[i-1][j], input[i][j] + input[i][j-1]); total = input[i][j]; }else if(j == 0 && i != 0){ input[i][j] = input[i][j] + input[i-1][j]; total = input[i][j]; } } } //get path; int path = result.length -1; int i = input.length-1; int j = input[0].length -1; while(total != 0){ if(i > 0 && j > 0){ if(input[i-1][j] < input[i][j-1]){ result[path] = total-input[i-1][j]; total = input[i-1][j]; i = i-1; path--; }else{ result[path] = total - input[i][j-1]; total = input[i][j-1]; j = j-1; path--; } }else if(j == 0 && i != 0){ result[path] = total - input[i-1][j]; total = input[i-1][j]; i = i-1; path--; }else if(i == 0 && j != 0){ result[path] =total - input[i][j-1]; total = input[i][j-1]; j = j-1; path--; } else if(i == 0 && j == 0){ result[path] = input[i][j]; total = total - input[i][j]; path--; } } return result; }