Data Structure

Binary Tree Traversal, Part 1

2019-10-23

outline:

pre-order, post-order, in-order traversal of binary tree
level-order traversal of binary tree

pre-order, post-order, in-order traversal of binary tree

pre-order:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }
    
    public void preorder(TreeNode node, List res) {
        if (node != null) {
            res.add(node.val);
            preorder(node.left, res);
            preorder(node.right, res);
        }
    }
}

post-order:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    
    public void postorder(TreeNode node, List res) {
        if (node != null) {
            postorder(node.left, res);
            postorder(node.right, res);
            res.add(node.val);
        }
    }
}

in-order:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
    
    public void inorder(TreeNode node, List res) {
        if (node != null) {
            inorder(node.left, res);
            res.add(node.val);
            inorder(node.right, res);
        }
    }
}

level-order

recursive method:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int level = 0;
        if (root == null)
            return res;
        level_recur(root, res, level);
        return res;
    }
    
    public void level_recur(TreeNode node, List<List<Integer>> res, int level) {
        // add new level if necessary
        if (res.size() == level)
            res.add(new ArrayList<Integer>());      
        // add current value to corresponding level
        res.get(level).add(node.val);
        // recursion
        if (node.left != null)
            level_recur(node.left, res, level+1);
        if (node.right != null)
            level_recur(node.right, res, level+1);
    }
}

iterative method:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null)
            return res;
        int level = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            res.add(new ArrayList<Integer>());
            int level_len = queue.size();
            for (int i = 0; i < level_len; i++) {
                TreeNode cur = queue.remove();
                res.get(level).add(cur.val);
                if (cur.left != null)
                    queue.add(cur.left);
                if (cur.right != null)
                    queue.add(cur.right);
            }
            level += 1;
        }
        return res;
    }
}

Backtracking Leetcode Summary, Part 2

2019-10-22

Subsets
Palindrome
Combination Sum, repeated number used
Combination Sum, unique number used

Subsets:

Problem Description: Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets.
Few Key Points:

This algorithm is very close to that of permutation. The only difference is that this counts for subsets instead of permutations.
One of the key point is to keep the order, don’t permute like the permutation algorithm

Code:
backtracking part, takes parameters:

result: LinkedList>
current: ArrayList
nums: nums to extract from

cur_idx: current index
Note: when adding to result, convert the current list into a new list

public void backtrack(List<List<Integer>> l, 
                      List<Integer> tmpList, 
                      int [] nums, 
                      int start) {
    l.add(new ArrayList<>(tmpList));
    for (int i = start; i < nums.length; i++) {
        tmpList.add(nums[i]);
        backtrack(l, tmpList, nums, i+1);
        tmpList.remove(tmpList.size() - 1);
    }
}

The solution part:

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> tmp = new ArrayList<Integer>();
    int start = 0;
    backtrack(res, tmp, nums, start);
    return res;
}

Palindrome:

Problem Description: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
e.g.:
Input: “aab”
Output:
[[“aa”,”b”],
[“a”,”a”,”b”]]
Few Key Points:
An utility function can be used to determine if str is palindrome or not.
Code:
backtrack:

public void backtrack(List<List<String>> result, 
                      List<String> tmp, 
                      String str, 
                      int index) {
    if (index == str.length()) 
        result.add(new ArrayList<String>(tmp));
    else {
        for (int i = index; i < str.length(); i++) {
            if (isPalindrome(str, index, i)) {
                tmp.add(str.substring(index, i+1));
                backtrack(result, tmp, str, i+1);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

Check if str is palindrome:

public boolean isPalindrome(String str, int s, int e) {
    while (s < e) {
        if (str.charAt(s++) != str.charAt(e--))
            return false;
    }
    return true;
}

The solution part:

public List<List<String>> partition(String s) {
    List<List<String>> res = new LinkedList<List<String>>();
    List<String> list = new ArrayList<String>();
    int idx = 0;
    backtrack(res, list, s, idx);
    return res;
}

Combination Sum, repeat allowed

Problem Description: Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times.
e.g.:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[[7],
[2,2,3]]
Codes:
backtrack:

public void backtrack(List<List<Integer>> res, 
                 List<Integer> tmp, 
                 int[] cand, 
                 int rem, 
                 int cur) {
    if (rem == 0) {
        res.add(new ArrayList<Integer>(tmp));
    } else if (rem < 0) {
        return;
    } else {
        for (int i = cur; i < cand.length; i++) {
            if (rem >= cand[i]) {
                tmp.add(cand[i]);
                backtrack(res, tmp, cand, rem - cand[i], i);
                tmp.remove(tmp.size()-1);
            } else {
                break;
            }
        }
    }
}

The solution part:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> tmp = new ArrayList<Integer>();
    int cur = 0;
    int rem = target;
    Arrays.sort(candidates);
    backtrack(res, tmp, candidates, rem, cur);
    return res;
}

Combination Sum, no repeats

Problem Description: Same as combination sum, with only difference that each number can only be used once.

Codes:
backtrack: (added while loop to eliminate repeating results)

public void backtrack(List<List<Integer>> res, 
                 List<Integer> tmp, 
                 int[] cand, 
                 int rem, 
                 int cur) {
    if (rem == 0) {
        res.add(new ArrayList<Integer>(tmp));
    } else if (rem < 0) {
        return;
    } else {
        for (int i = cur; i < cand.length; i++) {
            if (rem >= cand[i]) {
                tmp.add(cand[i]);                    
                backtrack(res, tmp, cand, rem - cand[i], i+1);
                tmp.remove(tmp.size()-1);
                while (i < cand.length-1 && cand[i] == cand[i+1])
                    i += 1;
            } else {
                break;
            }
        }
    }
}

The solution part is the same as the last section.

Backtracking Leetcode Summary, Part 1

2019-10-18

N-Queens
Permutation

N-Queens:

Problem Description: The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
Thought Process in Short: Backtracking with DFS. We know each row has one queen, so we move from top line to the bottom line line by line, checking each column, and two diagonals.
Few Key Points:

For all “hill” diagonals row + column = const, and for all “dale” diagonals row - column = const.
There could be the only one queen in a row and the only one queen in a column.

Algorithms:

Start from the first row = 0.
Iterate over the columns and try to put a queen in each column.
1. If square (row, column) is not under attack
  1. Place the queen in (row, column) square.
  2. Exclude one row, one column and two diagonals from further consideration.
  3. If all rows are filled up row == N
    - That means that we find out one more solution.
      Else
    - Proceed to place further queens backtrack(row + 1).
  4. Now backtrack : remove the queen from (row, column) square.

Codes:
Initialize log variables:

int rows[];
int hills[];
int dales[];
int n;
List<List<String>> output = new ArrayList();
int queens[];

Checking if a cell is under attack:

public boolean isNotUnderAttack(int row, int col) {
    int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
    if (res == 0) {
        return true;
    } else {
        return false;
    }
}

Method placing and removing queens:

public void placeQueen(int row, int col) {
    queens[row] = col;
    rows[col] = 1;
    hills[row - col + 2 * n] = 1;
    dales[row + col] = 1;
}

public void removeQueen(int row, int col) {
    queens[row] = 0;
    rows[col] = 0;
    hills[row - col + 2 * n] = 0;
    dales[row + col] = 0;
}

Adding a solution to existing solutions:

public void addSolution() {
    List<String> solution = new ArrayList<String>();
    for (int i = 0; i < n; ++i) {
        int col = queens[i];
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < col; ++j) {
            sb.append(".");
        }
        sb.append("Q");
        for (int j = 0; j < n - col - 1; ++j) {
            sb.append(".");
        }
        solution.add(sb.toString());
    }
    output.add(solution);
}

The actual backtracking process:

public void backtrack (int row) {
    for (int col = 0; col < n; col++) {
        if (isNotUnderAttack(row, col)) {
            placeQueen(row, col);
            if (row + 1 == n) {
                addSolution();
            } else {
                backtrack(row + 1);
            }
            removeQueen(row, col);
        }
    }
}

Main function of solution:

public List<List<String>> solveNQueens(int n) {
    this.n = n;
    rows = new int[n];
    hills = new int[4 * n - 1];
    dales = new int[2 * n - 1];
    queens = new int[n];
    
    backtrack(0);
    return output;
}

Permutation:

One of the more basic backtracking problem.
Algorithms:

If the first integer to consider has index n that means that the current permutation is done.
Iterate over the integers from index first to index n - 1.
1. Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]).
2. Proceed to create all permutations which starts from i-th integer : backtrack(first + 1).
3. Now backtrack, i.e. swap(nums[first], nums[i]) back.

Code：
BFS to find solutions, then backtracking to reverse to previous states. The following is the backtracking part.

public void backtrack(int n, 
                      ArrayList<Integer> nums, 
                      List<List<Integer>> res, 
                      int first_idx) {
    if (first_idx == n) {
        res.add(new ArrayList<Integer>(nums));
    }
    for (int i = first_idx; i < n; i++) {
        # swap first and ith
        Collections.swap(nums, first_idx, i);
        backtrack(n, nums, res, first_idx+1);
        # swap back to original
        Collections.swap(nums, first_idx, i);
    }
}

Main function of solution:

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new LinkedList();
    ArrayList<Integer> nums_list = new ArrayList<Integer>();
    for (int num : nums) {
        nums_list.add(num);
    }
    int n = nums.length;
    backtrack(n, nums_list, res, 0);
    return res;
}

A Brief Summary of Sorting Algorithm, Part 1

2019-10-13

Basics:
- in-place sorting vs. out-place sorting
- internal sorting vs. external sorting
- stable vs. unstable sorting
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort

Internal vs. external sorting

Internal sorting and external sorting describes where the sorting occurs:

internal sorting located entirely in memory
external sorting utilizes hard disk and external storage

Stable vs. unstable sorting

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

stable sorting algorithms includes:
1. Bubble Sort
2. Insertion Sort
3. Merge Sort
4. Count Sort

Bubble Sort

Bubble Sort is a type of stable sorting algorithm. The algorithm compares two elements that are next to each other and swap two element is the left one is larger than the right one. Time complexity of bubble sort is O(n*n).

def bubbleSort(arr): 
    n = len(arr) 
    for i in range(n): 
        for j in range(0, n-i-1): 
            if arr[j] > arr[j+1] : 
                arr[j], arr[j+1] = arr[j+1], arr[j] 
    return arr

Selection Sort

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted sub-array. Selection sort can be done stably. Time complexity of selection sort is O(n*n).

def selectionSort(arr):
    for i in range(len(arr)): 
        min_idx = i 
        for j in range(i+1, len(arr)): 
            if arr[min_idx] > arr[j]: 
                min_idx = j 
        tmp = arr[i]
        arr[i] = arr[min_idx]
        arr[min_idx] = tmp
    return arr

Insertion Sort

Insertion sort is stable. In every iteration of insertion sort, the first element is selected and inserted into the correct location in the sorted half of the array. Time complexity of Insertion sort is O(n*n).

def insertionSort(arr): 
    for i in range(1, len(arr)): 
        key = arr[i] 
        j = i-1
        while j >= 0 and key < arr[j] : 
                arr[j + 1] = arr[j] 
                j -= 1
        arr[j + 1] = key 
    return arr

Merge Sort

Merge sort is stable. Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. Time complexity is O(n*log(n)).

def mergeSort(arr): 
    if len(arr) >1: 
        mid = len(arr)//2
        L = mergeSort(arr[:mid])
        R = mergeSort(arr[mid:])
        i = j = k = 0
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i+=1
            else: 
                arr[k] = R[j] 
                j+=1
            k+=1
        while i < len(L): 
            arr[k] = L[i] 
            i+=1
            k+=1
        while j < len(R): 
            arr[k] = R[j] 
            j+=1
            k+=1
    return arr

Quick Sort

For quick sort, we pick a random element as pivot. Compare each element with the pivot to create first half of the list smaller than the pivot and the second half larger than the pivot. After that, quick sort divide conquer two halves. Time complexity for quick sort is O(nlog(n)), worst case is O(nn). Quick sort can be made stable.

def partition(arr,low,high): 
    i = (low-1)
    pivot = arr[high]
    for j in range(low , high): 
        if   arr[j] < pivot: 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 

def quickSort(arr,low,high): 
    if low < high: 
        pi = partition(arr,low,high) 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high)

Heap Sort

Build a max heap from the input data.
At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.

Repeat above steps while size of heap is greater than 1.
Heapify: this procedure calls itself recursively to move the max value to the top of the heap. Time complexity for heapify is O(log(n)) and time complexity for building a heap is O(n). Thus, heap sort gives the overall time complexity as O(n*log(n)).

def heapify(arr, n, i): 
    largest = i # Initialize largest as root 
    l = 2 * i + 1     # left = 2*i + 1 
    r = 2 * i + 2     # right = 2*i + 2 
    # left child  
    if l < n and arr[i] < arr[l]: 
        largest = l 
    # right child
    if r < n and arr[largest] < arr[r]: 
        largest = r 
    # change the root 
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i] # swap 
        # Heapify upward 
        heapify(arr, n, largest) 
  
def heapSort(arr): 
    n = len(arr) 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i] # swap 
        heapify(arr, i, 0) 
    return a

ZEXI JIN

Data Structure

Binary Tree Traversal, Part 1

pre-order, post-order, in-order traversal of binary tree

level-order

Backtracking Leetcode Summary, Part 2

Subsets:

Palindrome:

Combination Sum, repeat allowed

Combination Sum, no repeats

Backtracking Leetcode Summary, Part 1

N-Queens:

Permutation:

A Brief Summary of Sorting Algorithm, Part 1

Internal vs. external sorting

Stable vs. unstable sorting

Bubble Sort

Selection Sort

Insertion Sort

Merge Sort

Quick Sort

Heap Sort