# 1301. Algorithm - TemplatesAlgorithm

Templates for algorithms solutions.

## 1. Templates

### 1.1 Recursion Template

Four steps:

1. recursion terminator
2. process logic in current level
3. drill down
4. reverse the status in the current level if necessary

Pseudo code example:

// pseudo code
public void recursion(int level, int param) {
// recursion terminator
if (level > MAX_LEVEL) {
// process result and quit
return;
}

// process logic in current level
process(level, data);

// drill down, call the same function for next level
recursion(level + 1, param, data);

// reverse the status in the current level if necessary
}


### 1.1 Defining Customized Comparator

private class IntervalComparator implements Comparator<Interval> {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
}
// three return values
// -1, i1 < i2
// 0, i1 = i2
// 1, i1 > i2


Usage.

Collections.sort(intervals, new IntervalComparator());

// lamda expression
Collections.sort(intervals, (a, b) -> a.start - b.start);


More conditions

private class IntervalComparator implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
if (a.start == b.start) {
return a.end - b.end;
} else {
return a.start - b.start;
}
}
}
Collections.sort(intervals, new IntervalComparator());
// equivalent to one line lamda expression
Arrays.sort(intervals, (a,b)->(a.start == b.start ? a.end - b.end : a.start - b.start));


The comparison only works for integer, not for double type.

### 1.2 Sorting Array by Another Array’s Value.

Integer[] index = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
index[i] = i;
}

Arrays.sort(index, new Comparator<Integer>() {
public int compare(Integer i1, Integer i2) {
return nums[i2] - nums[i1];
}
});

int start = 0;
int end = nums.length - 1;

while (start < end) {
int mid = (start + end) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}


Optimized Version.

int start = 0;
int end = nums.length - 1;

while (start + 1 < end) { // avoid infinite loop, need to check nums[start] and nums[end] after the while loop
int mid = start + (end - start) / 2; // avoid overflow, assuming start is not negative and end is not very large positive.
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}


### 1.4 Direction Array used in Grid Traversal, DFS & BFS.

int[] dr = new int[]{-1, 0, 1, 0};
int[] dc = new int[]{0, -1, 0, 1};

// A is a given matrix
int m = A.length;
int n = A[0].length;
for (int i = 0; i < 4; i++) {
int r = pos[0] + dr[i];
int c = pos[1] + dc[i];
if (r < 0 || r >= m || c < 0 || c >= n) {
continue;
}

if (A[r][c] == 1) {
// code here
}
}


### 1.5 Subset

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (nums == null) {
return res;
}

Arrays.sort(nums);// not necessary, just for unit test

List<Integer> list = new ArrayList<Integer>();
helper(nums, 0, list, res);
return res;
}

private void helper(int[] nums, int pos, List<Integer> list, List<List<Integer>> res) {
res.add(new ArrayList<Integer>(list)); // when adding it to the result depends on requirement

for (int i = pos; i < nums.length; i++) {