Code templates

[YuezhenQin]

1. Two pointers: one input, opposite ends

public int fn(int[] arr) {
    int left = 0;
    int right = arr.length - 1;
    int ans = 0;
    while (left < right) {
        if (CONDITION) {
            left ++;
        } else {
            right --;
        }
    }
    return ans;
}

2. Two pointers: two inputs, exhaust both

public int fn(int[] arr1, int[] arr2) {
    int i = 0;
    int j = 0;
    int ans = 0;
    while (i < arr1.length && j < arr2.length) {
        if (CONDITION) {
            i++;
        } else {
            j++;
        }
    }
    if (i < arr1.length) {
        //do logic
        i++;
    }
    if (j < arr2.length) {
        //do logic
        i++;
    }
}

3. Sliding window

public int fn(int[] arr) {
    int left = 0;
    int curr = 0; 
    int ans = 0;
    for (int right = 0; right < arr.length; right++) {
        //do logic to "add" element at  arr[right] to curr
        while (WINDOW_IS_INVALID) {
            //do logic to "remove" element at arr[left] from curr
           left ++;
        }
        //update answer
    }
    return ans;
}

4. Build a prefix sum

public int[] fn(int[] arr) {
    int[] prefix = new int[arr.length];
    prefix[0] = arr[0];
    for (int i = 1; i < prefix.length; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    return prefix;
}

5. Effective string building

public String fn(char[] arr) {
    StringBuilder sb = new StringBuilder();
    for (char c: arr) {
        sb.append(c);
    }
    return sb.toString();
}

6. Linked list: fast and slow pointer

public int fn(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    int ans = 0;
    while (fast != null && fast.next != null) {
        //do logic
        slow = slow.next;
        fast = fast.next.next;
    }
    return ans;
}

7. Reversing a linked list

public ListNode fn(ListNode head) {
    if (head == null) return null;
    ListNode prev = null;
    ListNode curr = head;
    while (curr.next != null) {
        ListNode nextNode = head.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev;
}

8. Find the number of subarrays that fit an exact criteria

public int fn(int[] arr, int k) {
}

9. Monotonic increasing/decreasing stack

public int fn(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    int ans = 0;
    for (int num: arr) {
        while (!stack.isEmpty() && stack.peek() > num) {
            //do logic
            stack.pop();
        }
        stack.push(num);
    }
    return ans;
}

10. Binary tree: DFS (recursive)

public int dfs(TreeNode root) {
    if (root = null) return 0;
    int ans = 0;
    //do logic
    dfs(root.left);
    dfs(root.right);
    return ans;
}

11. Binary tree: DFS (iterative)

public int dfs(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    int ans = 0;
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        //do logic

    }
}