Path of Minimum Sum in a Binary Tree

[Question]
Given a binary tree, find the minimum sum from root to the leaf and also print that path?

[Analysis]
Apply post order traversal on binary tree. For a given node, the minimum sum from this node is, the smaller of the minimum sums between left and right sub-trees, plus the value in the node. It is tricky to deal with the node with only one child. Time Complexity is O(N). Space Complexity O(N).

[Solution]
//
// class BSTNode {
//    BSTNode left;
//    BSTNode right;
//    int    value;
// }
//
//--- JAVA ---
public static int findMinimumSumOfPath( BSTNode root, List<BSTNode> path)
{
   if (root.left ==null && root.right==null) {
    path.add(root);
    return root.value;
   }
   
   List<BSTNode> leftPath = new ArrayList<BSTNode>();
   List<BSTNode> rightPath = new ArrayList<BSTNode>();
   int leftSum= Integer.MAX_VALUE;
   int rightSum=Integer.MAX_VALUE;
   int sum=0;
   
   if (root.left!=null) 
    leftSum = findMinimumSumOfPath ( root.left, leftPath );
   if (root.right!=null) 
        rightSum = findMinimumSumOfPath ( root.right, rightPath);
   if (leftSum < rightSum) {
        path.add(root);
        path.addAll(leftPath);
        sum = root.value+leftSum;
   } 
   else {
        path.add(root);
        path.addAll(rightPath);
        sum = root.value+rightSum;
   }
   return sum;
}

//--- C++ ---
int minSumPath (Node* root, vector<int>& path) {
    if (!root) return 0;

    vector<int> path1, path2;
    int left = minSumPath(root->left, path1);
    int right=minSumPath(root->right, path2);

    path.push_back(root->val);
    if (left< right) 
        path.insert(path.end(), path1.begin(), path1.end());
    else
       path.insert(path.end(), path2.begin(), path2.end());
    
    return min(left,right) + root->val;
}

Jump Game (2)

[Question]
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

[Analysis]
Be greedy. Assume the minimum steps to reach position i is S[i], then from position i+1 to A[i]+i, the steps to reach are at most S[i]+1 (part of [ i+1, A[i]+i ] may already be reached before using A[i]).

[Solution]
//-----------
//-- C++ --
//-----------
class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        vector<int> cnt(n,0);

        for (int i=0, k=0; i<n && k<n; i++)
            for(int j=k; j<min(n, nums[i]+i+1); j++,k++)
                cnt[j] = (i==j)?0:cnt[i]+1;
               
        return cnt.back();
    }
};

Jump Game (1)

[Question]
Assume an array of integers, A[i]>=0, represents the maximum steps allowed to move forward from i. Starting scan from A[0], is there a path to reach the end of A (i.e. A[n-1])?

For example, given {3, 0, 2, 1, 2, 0, 0}, there is a path A[0], A[3], A[4], A[6]; given {3, 0, 2, 0, 2, 0, 0}, the path has to be A[0], A[2], A[4], A[6]; given {3, 1, 1, 0, 2, 0, 0},  no path to the end.

[Analysis]
Be greedy. Push the reach from the A[0] to forward index  j ="A[0]+0", A[1] to index j = max(j, A[1]+1), until i> j (unreachable anymore), or forward index j covers A's last index.

[Solution]
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int i=0, j=0;
        while (i<=j) {
            j = max(j, nums[i]+i);
            if (j>=nums.size()-1)
                return true;
            i++;
        }
        return false;
    }
};

In-order Iterator of a Binary Search Tree

[Question]
Implement an in-order iterator of Binary Search Tree (BST)

[Analysis]
Use a stack to traverse BST. The top of the stack is the element whose value has not been visited by in-order:  the next is either the left most node from this node or itself when all left sub-tree has been visited.

[Solution]
/*
 * public class BSTNode {
 *  BSTNode left, right;
 * int     value;
 * }
 */

import java.util.*;

public class BSTIterator {
BSTNode root;
Stack<BSTNode>   st;
BSTNode last;

public BSTIterator( BSTNode root ){
this.root = root;
st = new Stack<BSTNode>();
if (root!=null)
st.push(root);
last = null;
}

public boolean hasNext() {
return (!st.isEmpty());
}

public BSTNode next() {
while (last==null && st.peek().left!= null ||
last!=null && st.peek().left!= null && st.peek().left.value > last.value) {
st.push(st.peek().left);
}

last = st.pop();
if (last.right!=null) st.push(last.right);

return last;
}
}

Trie Implementation

[Question]
Implement a Trie.

[Analysis]
Trie: http://en.wikipedia.org/wiki/Trie


[Solution]

import java.util.*;

public class Trie {
Trie[]  nodes; //nodes of characters: a, b, ... z.
int[]   count;
boolean eow;    //end of word
boolean isLeaf;

public Trie() {
nodes = new Trie[26];
count = new int[26];
eow = false;
isLeaf = true;
}

public void addWord(String word) {
if (word==null || word.length()==0) return;

String temp= word.toLowerCase();
char[] chars = temp.toCharArray();
Trie p = this;
for(char c: chars) {
p.count[c-'a'] ++;
p.isLeaf = false;
if (p.nodes[c-'a'] == null) {
Trie node = new Trie();
p.nodes[c-'a'] = node;
}
p = p.nodes[c-'a'];
}
p.eow = true;
}

public boolean isWord(String word) {
String temp= word.toLowerCase();
char[] chars = temp.toCharArray();

Trie p = this;
for (char c: chars) {
if (p.nodes[c-'a'] == null) return false;
p = p.nodes[c-'a'];
}
return p.eow;
}

public void removeWord (String word) {
String temp = word.toLowerCase();

if (isWord (temp)) {
char[] chars = temp.toCharArray();

Trie p = this;
boolean flag = false;
for (char c: chars) {
p.count[c-'a']--;
if (p.count[c-'a'] == 0) {
p.nodes[c-'a'] = null;
flag = true;
break;
}
p = p.nodes[c-'a'];
}
if (!flag && p.eow) {
p.eow = false;
}
if (p.numOfWords() == 0) p.isLeaf = true;
}
}

public List<String> getAllWords() {
List<Character> path = new ArrayList<Character> ();
List<String>    words= new ArrayList<String>();
getAllWords(path, words);
return words;
}

public int numOfWords() {
int total =0;
for (int i: count) {
total+=i;
}
return total;
}

private void getAllWords(List<Character> path, List<String> words) {
if (eow) {
String s = "";
for (Character c: path) s+=c;
words.add(s);
}

if (isLeaf) return;

for (int i=0; i<nodes.length; i++) {
if (nodes[i]!=null) {
char c = Character.toChars('a'+i)[0];
path.add(c);
nodes[i].getAllWords(path, words);
path.remove(path.size()-1);
}
}
}
}

Stable Partition of an Array

[Question]
Given an array of positive and negative integers, re-arrange it so that positives on one end and negatives on the other, but retain the original order of appearance, e.g. 2,7,-5, 9,-1, 10,-3 => -5, -1, -3, 2, 7, 9, 10.  Do it in-place, in O(nlogn).

[Analysis]
Using the partition method in quick sort, the order of those elements may change. Using the bubble sort to exchange one by one, the order is kept but the time complexity will be O(n^2). Merge sort can be a help here to get the O(nLogn) and in place method: i.e. assume each half of the array has been in right order (negatives on the left, positives on the right), then merge two half into one.

[Solution]

public class ArrayPartition implements TestCaseRunner{
void swap (int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

void mirror (int[] a, int left, int right) {
if (left<0 || right >= a.length) return;
while (left<right) {
swap (a, left++, right--);
}
}

void merge(int[] a, int i, int length ) {
if (length < 2) return;

int med = i+(length>>1);
int j = med;
merge(a, i, length>>1);
merge(a, j, length - (length>>1));

while (i<j && a[i]<0) {
i++;
}

if (i<med) {
while (j< i+length && a[j]<0) {
j++;
}

if (j>med) {
mirror (a, i, j-1);
mirror (a, i, j-med + i-1);
mirror (a, j-med+i, j-1);
}
}
}

public int[] partition(int[] a) {
if (a==null || a.length < 2) return a;
merge(a, 0, a.length);
return a;
}

public void runTestCases() {
int[] a = {1, -1, 2, 3, -5, -2, 9, 3, -4};
partition(a);
for(int i: a) System.out.println(i);
}
}