SPOJ: SUBSUMS - Subset Sums

Today I solved the Subset Sums (SUBSUMS) problem on SPOJ. Here's the link: http://www.spoj.com/problems/SUBSUMS

By the name of it, it seems like a classic Dynamic Programming problem, but as soon as you pay attention to the constraints, it soon becomes evident that a DP solution which will most optimally have O(N*W) complexity, where N = number of elements and W= the target sum range's upper bound, will bottleneck at W.

I solved this problem using Meet in the middle technique whereby, I divide the set of input numbers into 2 halves and consider sums of all subsets in each half (cardinality 2^17 in each set, which can be pretty easily generated using brute-force recursion), to find the subset-duos (containing one subset from each half) who sum up to fall in the given range. The count of such possible subset-duos gives us our solution. My solution also involves putting binary search and recursion into use.

Here's my accepted(https://www.spoj.com/status/SUBSUMS,chandniverma/) solution code:

  

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.function.BiPredicate;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		int arr[] = new int[N];
		for (int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();
		
		System.out.println(getCountOfSubsets(arr, A, B));
	}

	private static long getCountOfSubsets(int[] arr, int a, int b) {
		Integer[] firstSubsetSums = getSubsetSums(arr, 0, arr.length/2);
		Integer[] secondSubsetSums = getSubsetSums(arr, arr.length/2+1, arr.length-1);
		Arrays.sort(secondSubsetSums);
		
		long count = 0;
		for(int i=0; i<firstSubsetSums.length; i++) {
			int p = findLastIdxWithFalsePredicate(secondSubsetSums, a-firstSubsetSums[i], (sum, mark)->sum>=mark);
			int q = findLastIdxWithFalsePredicate(secondSubsetSums, b-firstSubsetSums[i], (sum, mark)->sum>mark);
			count += (q-p);
		}
		
		return count;
	}

	private static int findLastIdxWithFalsePredicate(Integer[] sums, int val, BiPredicate<Integer, Integer> pred) {
		int min = 0;
		int max = sums.length-1;
		while (min<max) {
			int mid = min + (max-min+1)/2;
			if (pred.test(sums[mid], val)) {
				max = mid-1;
			} else {
				min = mid;
			}
		}
		if (pred.test(sums[min], val))
			return -1;
		return min;
	}

	private static Integer[] getSubsetSums(int[] arr, int st, int end) {
		List<Integer> sums = new ArrayList<>();
		generateSubsetSumsRecur(arr, st, end, st, 0, sums);
		return sums.toArray(new Integer[0]);
	}

	private static void generateSubsetSumsRecur(int[] arr, int st, int end, int index, int runningSum, List<Integer> sums) {
		if (index == end+1) {
			sums.add(runningSum);
			return;
		}
		
		generateSubsetSumsRecur(arr, st, end, index+1, runningSum+arr[index], sums);
		generateSubsetSumsRecur(arr, st, end, index+1, runningSum, sums);
	}
}

 
  

The complexity of the above code is:

O(2^(N/2) + 2^(N/2)*(lg (2^(N/2)))) 

= O(2^(N/2) + 2^(N/2)*N/2) 

= O(N*2^(N/2)) 

Feel free to checkout and let me know your thoughts in the comments below! Do share if you have a better solution in mind!

SPOJ Dynamic Programming: KNAPSACK

Today I started with solving Dynamic Programming problems and the first one on the refresher list was the classical 0/1-Knapsack.

I found an online judge, SPOJ, testing solutions to this problem here: https://www.spoj.com/problems/KNAPSACK/

Here is my accepted(https://www.spoj.com/status/KNAPSACK,chandniverma/) solution to the same:

import java.util.*;
import java.lang.*;

class Main
{
 public static void main (String[] args) throws java.lang.Exception
 {
  Scanner sc = new Scanner (System.in);
  int s = sc.nextInt();
  int n = sc.nextInt();
  
  int[] size = new int[n+1];
  long[] val = new long[n+1];
  for (int i=1; i<=n; i++) {
   size[i] = sc.nextInt();
   val[i] = sc.nextInt();
  }
  sc.close();
  
  long[][] memo = new long[n+1][s+1];
  for (int i=0; i<=n; i++) {
   for (int j=0; j<=s; j++) {
    memo[i][j] = -1;
   }
  }
  System.out.println(getMaxVal(size, val, s, n, memo));
 }

 private static long getMaxVal(int[] size, long[] val, int s, int n, long[][] memo) {
  if (n<=0 || s<=0)
   return 0;

  if (memo[n][s] != -1)
   return memo[n][s];

  if ((s-size[n]) >= 0) {
   return memo[n][s] = Math.max (
    val[n] + getMaxVal(size, val, s-size[n], n-1, memo),
    getMaxVal(size, val, s, n-1, memo)
    );
  } else {
   return memo[n][s] = getMaxVal(size, val, s, n-1, memo);
  }
 }
}

This solution works with a complexity of O(n*s) where n is the number of items under consideration and s is the size or capacity of the bag.

You can always find my SPOJ profile with solved problem list at https://www.spoj.com/users/chandniverma/.

You can also checkout my recent-most submissions at SPOJ on https://www.spoj.com/status/chandniverma/.

Feel free to share optimisations and improvisations in comments below!

See ya next time!

<3✌

LeetCode Medium: Count Complete Tree Nodes

Here is one LeetCode Medium level problem (Problem # 222: Count Complete Tree Nodes) which is an actual 2 liner to solve when solved recursively:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

This solution is O(n) in number of nodes in the binary tree and is a generic solution that can be used to solve any binary tree for that matter.

The fact that this is a complete binary tree, brings to my mind another solution approach with O((lg n)^2) solution which I'll share here very soon!

Until next time,

Stay Tuned and Happy Coding!

See ya later!!

LeetCode Problem #441. Arranging Coins

Here is my solution on LeetCode Problem #441. Arranging Coins 

Approach 1: Based on binary search and inequalities

class Solution {
    public int arrangeCoins(int N) {
        long minLevel = 0;
        long maxLevel = N;
        while (minLevel<maxLevel) {
            long midLevel = minLevel + (maxLevel-minLevel+1)/2;
            boolean predicate = ((midLevel*midLevel + midLevel) > (2*(long)N));
            
            if (predicate) {
                maxLevel = midLevel-1;
            }
            else {
                minLevel = midLevel;
            }
        }
        
        if ((minLevel*minLevel + minLevel) > (2*(long)N))
            return -1;
        return (int)minLevel;
    }
}

The time complexity is super-fast: O(lg n) where n is the the input N(the number of coins) and I don't think it can get any faster iteratively.

The only other faster solution I can think of is using SriDharacharya formula to find the roots to inequality:

l^2 + l <= 2*N

where l = last complete level

Do share your thoughts below!

<3
~Take Care

LeetCode Medium: Lowest Common Ancestor of a Binary Tree

My Solution for LeetCode medium problem #236: Lowest Common Ancestor of a Binary Tree, based on tree-recursion:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        boolean leftHasP = hasDescendant(root.left, p.val);
        boolean leftHasQ = hasDescendant(root.left, q.val);
        boolean rightHasP = hasDescendant(root.right, p.val);
        boolean rightHasQ = hasDescendant(root.right, q.val);
        
        if (root.val == p.val || root.val == q.val)
            return root;
        if ((leftHasP && rightHasQ) || (leftHasQ && rightHasP))
            return root;
        if (!leftHasP && !leftHasQ)
            return lowestCommonAncestor(root.right, p, q);
        else
            return lowestCommonAncestor(root.left, p, q);
        
    }
    
    private boolean hasDescendant(TreeNode root, int val) {
        if (root == null)
            return false;
        
        if (root.val == val) {
            return true;
        }
        if (hasDescendant(root.left, val) || hasDescendant(root.right, val)) {
            return true;
        }
        
        return false;
    }
}

Feel free to share your thoughts in comments, below!

LeetCode Medium: Construct Binary Tree from Inorder and Postorder Traversal

When we are given Inorder traversal of nodes in a tree, along with 1 other traversal, either preorder or postorder,  we can derive the original tree structure from the provided information.

I have solved the following LeetCode problem with the same idea in mind. Grab a look:

Problem #106: Construct Binary Tree from Inorder and Postorder Traversal 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length==0)
            return null;
        TreeNode root = treeFromInorderPostorder(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
        return root;
    }
    
    private TreeNode treeFromInorderPostorder(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        
        int inRootIdx = inStart;
        for (int i=inStart; i<=inEnd; i++) {
            if (inorder[i]==rootVal) {
                inRootIdx = i;
                break;
            }
        }
        // assert(inRootIdx != -1);
        int nodesInLeftSubtree = inRootIdx - inStart;
        if (nodesInLeftSubtree == 0) {
            root.left = null;
        } else {
        root.left = treeFromInorderPostorder(inorder, inStart, inRootIdx-1, postorder, postStart, postStart+nodesInLeftSubtree-1);
        }
        
        int nodesInRightSubtree = inEnd - inRootIdx;
        if (nodesInRightSubtree == 0) {
            root.right = null;
        } else {
        root.right = treeFromInorderPostorder(inorder, inRootIdx+1, inEnd, postorder, postStart+nodesInLeftSubtree, postEnd-1);
        }
        
        return root;
    }
}

In the similar vein, consider a previously solved problem:

Problem #105: Construct Binary Tree from Preorder and Inorder Traversal

The bounds for parameters with which to make recursive calls in these problems can be slightly tricky to understand so one needs to be careful with those.

Besides that, as always, let me know in comments if you find these solutions helpful or have ideas for improvement.

Toodles!

LeetCode medium: Construct Binary Tree from Preorder and Inorder Traversal

When we are given Inorder traversal of nodes in a tree, along with 1 other traversal, either preorder or postorder,  we can derive the original tree structure from the provided information.

I have solved the following LeetCode problem with the same idea in mind:

Problem #105: LeetCode medium: Construct Binary Tree from Preorder and Inorder Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length == 0 || preorder.length==0)
            return null;
        TreeNode root = treeFromInorderPreorder(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1);
        return root;
    }
    
    private TreeNode treeFromInorderPreorder(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd) {
        
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        
        int inRootIdx = inStart;
        for (int i=inStart; i<=inEnd; i++) {
            if (inorder[i]==rootVal) {
                inRootIdx = i;
                break;
            }
        }
        // assert(inRootIdx != -1);
        int nodesInLeftSubtree = inRootIdx - inStart;
        if (nodesInLeftSubtree == 0) {
            root.left = null;
        } else {
        root.left = treeFromInorderPreorder(inorder, inStart, inRootIdx-1, preorder, preStart+1, preStart+1+nodesInLeftSubtree);
        }
        
        int nodesInRightSubtree = inEnd - inRootIdx;
        if (nodesInRightSubtree == 0) {
            root.right = null;
        } else {
        root.right = treeFromInorderPreorder(inorder, inRootIdx+1, inEnd, preorder, preStart+nodesInLeftSubtree+1, preEnd);
        }
        
        return root;
    }
}

In the similar vein, consider:

Problem #106: Construct Binary Tree from Inorder and Postorder Traversal

The bounds for parameters with which to make recursive calls can be slightly tricky to understand so one needs to be careful with those.

Besides that, as always, let me know in comments if you find these solutions helpful or have ideas for improvement.

Toodles!...

LeetCode Medium: Binary Tree Level Order Traversal

Here is my solution to LeetCode Problem #102: Binary Tree Level Order Traversal based on BFS traversal with modification -

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            int levelSize = q.size();
            List<Integer> level = new ArrayList<> ();
            for (int i=0; i<levelSize; i++) {
                TreeNode current = q.remove();
                level.add(current.val);
                if (current.left != null) q.add(current.left);
                if (current.right != null) q.add(current.right);
            }
            res.add(level);
        }
        
        return res;
    }
}

Try these related problems too:

https://chandniverma.blogspot.com/2020/06/leetcode-medium-binary-tree-right-side.html

LeetCode: More problems on Trees

Here are my Java solutions to more problems on trees. Following are 2 related ones:

Problem #104: Maximum Depth of Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        
        int lDepth = maxDepth(root.left);
        int rDepth = maxDepth(root.right);
        
        return Math.max(lDepth, rDepth)+1;
    }
}

Problem #543: Diameter of a Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    private int height(TreeNode root) {
        if (root == null)
            return -1;
        
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null)
            return 0;
        
        int lHeight = height(root.left);
        int rHeight = height(root.right);
        int lDiameter = diameterOfBinaryTree(root.left);
        int rDiameter = diameterOfBinaryTree(root.right);
        
        return Math.max(lHeight+rHeight+2 , Math.max(lDiameter, rDiameter));
    }
}

~~~

I plan to extend this category of posts with more related ones to come soon!

Until then,

Happy Problem Solving!!