Learning Plan for Quick Mastery

Some readers have given me feedback: The content on this site is indeed solid. If you study it seriously, you can thoroughly master data structures and algorithms. However, their current problem is a lack of time. What should they do?

Is it possible to focus on the most essential skills first, to quickly enhance their abilities just before an interview, and then slowly learn the rest when they have more time?

I believe this is indeed a need for a considerable number of readers, so I have specifically created this quick mastery directory to meet these readers' demands.

The quick mastery directory cannot cover everything, so if you have ample time, I still recommend studying according to the Main Site Directory.

About the Problem Sets

Readers often ask about company-specific problem sets, so I'll elaborate here.

Different companies have different problem sets, with varying difficulty. The quick mastery directory includes essential algorithm patterns and classic algorithm problems, not limited to a specific company's problem set.

The purpose of this directory is to fundamentally tackle the core of algorithms, allowing you to confidently apply algorithm frameworks to independently solve medium-difficulty, frequently tested algorithm problems, rather than relying on luck and memorization to remember specific problem sets.

Some readers start preparing for algorithms by immediately practicing company-specific problem sets, which is incorrect. My suggestion is to first understand common algorithm frameworks, and then consider practicing problem sets.

No matter which company's problem set you work on, the algorithms themselves have only a few frameworks and patterns. Once you've mastered these, you can complete a problem set in at most two to three hours. There's nothing magical about it.

Problem sets have two main purposes:

1. Understanding the difficulty and algorithm types of a company's exam in advance. For example, if your company explicitly states that dynamic programming algorithms won't be tested, you can skip the dynamic programming section of this directory and focus on other algorithm skills.

2. Convenient for review. After mastering the algorithm frameworks, you can independently solve problems. At this point, you can practice the problem sets several times to test your learning outcomes and consolidate knowledge points.

Below is a summary of the exercise problem sets involved in this directory. Although there seem to be many problems, most are framework problems that you can easily solve after reading the articles below. There's no need to practice them separately. This problem set is only for the convenience of readers who have completed this directory to review:

The Quick Mastery problem set has been fully integrated with the site's plugins. After installing the Chrome plugin, you can view the site's solution explanations directly on the LeetCode problem pages. The problem list is also integrated into the VSCode plugin and Jetbrains plugin.

Principles of the Quick Mastery Directory

Why can the Quick Mastery Directory rapidly improve algorithm skills in a short time?

1. Unified Solution Style Based on Template Framework.

This Quick Mastery Directory is not just a simple list of problems. It summarizes a framework template for each algorithm, and problems are solved using a unified process framework. You learn true algorithm-solving skills rather than rote memorization, so you are not limited to specific problem lists but can independently tackle unseen problems with ease.

2. Gradual Progression, from Shallow to Deep, including Data Structures and Algorithms.

Algorithm technique A might be a fusion of algorithms B and C. If A is taught without any background context, it seems complex and elusive. However, if you fill in the basics of B and C, you can derive A yourself, making it straightforward. Many readers are intimidated by recursive algorithms, but I emphasize that the essence of algorithms is brute-force, and recursion is a classic brute-force method based on tree structures. Once you understand binary tree structures, you can grasp any recursive algorithm. Therefore, this directory starts with key data structures and then moves on to problem-solving. By solidifying the basics first, tackling problems becomes smooth and efficient.

3. Scientific Learning Methods with Rich Auxiliary Tools. Combining examples and exercises, with explanations followed by practice, supplemented by problem-solving plugins and visualization panels, all efforts are made to help readers reduce understanding costs and improve learning efficiency.

I must emphasize again, I fully understand that some readers are pressed for time, but don't rush into problem-solving without learning the framework.

The problem with just solving problem sets is over-reliance on luck. If you're lucky and encounter a familiar problem, you might recall the solution. Without luck, you'll need to rely on an algorithm framework, and without learning it, you may fail. A shaky foundation leads to instability. Initially investing time to solidify the basics ultimately saves time.

Let's begin. The Quick Mastery Directory is divided into "Data Structures" and "Algorithm Problem-Solving" sections. The data structures section generally does not involve algorithm problems and is relatively simple. The problem-solving section is key, requiring careful thought and hands-on practice.

Data Structures

Array and Linked List

Introduces the basic concepts of arrays and linked lists, which are relatively simple. The main focus is the technique of circular arrays, which allows for insertion and deletion at the head of the array with a time complexity of $O(1)$.

Principles and Applications of Hash Tables

As a quick mastery tutorial, we can skip the implementation of the two methods to resolve hash collisions in hash tables. However, understanding the principles of hash tables is essential.

Hash tables can be combined with arrays and doubly linked lists to form more powerful data structures like LinkedHashMap and ArrayHashMap. These structures add new features to hash tables, and understanding their principles is necessary.

Basics and Traversal of Binary Trees

Although this is just an introductory chapter, the section on binary trees must be emphasized, especially the traversal of binary trees, as it is key to understanding recursive thinking. When starting to tackle problems, the essence of all recursive algorithms is the traversal of binary trees.

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        // visit the cur node
        System.out.println(cur.val);

        // add the left and right children of cur to the queue
        if (cur.left != null) {
            q.offer(cur.left);
        }
        if (cur.right != null) {
            q.offer(cur.right);
        }
    }
}

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        // visit the cur node
        std::cout << cur->val << std::endl;
        
        // add the left and right children of cur to the queue
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    while q:
        cur = q.popleft()
        # visit cur node
        print(cur.val)

        # add cur's left and right children to the queue
        if cur.left is not None:
            q.append(cur.left)
        if cur.right is not None:
            q.append(cur.right)

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []*TreeNode{}
    q = append(q, root)
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        // visit cur node
        fmt.Println(cur.Val)
        
        // add cur's left and right children to the queue
        if cur.Left != nil {
            q = append(q, cur.Left)
        }
        if cur.Right != nil {
            q = append(q, cur.Right)
        }
    }
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    q.push(root);
    while (q.length !== 0) {
        var cur = q.shift();
        // visit cur node
        console.log(cur.val);

        // add cur's left and right children to the queue
        if (cur.left !== null) {
            q.push(cur.left);
        }
        if (cur.right !== null) {
            q.push(cur.right);
        }
    }
}

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // record the current level being traversed (root node is considered as level 1)
    int depth = 1;

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // visit the cur node and know its level
            System.out.println("depth = " + depth + ", val = " + cur.val);

            // add the left and right children of cur to the queue
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        depth++;
    }
}

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    // record the current level being traversed (the root node is considered as level 1)
    int depth = 1;

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // visit the cur node, knowing its level
            cout << "depth = " << depth << ", val = " << cur->val << endl;

            // add the left and right children of cur to the queue
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
}

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    # record the current depth being traversed (root node is considered as level 1)
    depth = 1

    while q:
        sz = len(q)
        for i in range(sz):
            cur = q.popleft()
            # visit cur node and know its depth
            print(f"depth = {depth}, val = {cur.val}")

            # add cur's left and right children to the queue
            if cur.left is not None:
                q.append(cur.left)
            if cur.right is not None:
                q.append(cur.right)
        depth += 1

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []*TreeNode{root}
    // record the current depth being traversed (root node is considered as level 1)
    depth := 1

    for len(q) > 0 {
        // get the current queue length
        sz := len(q)
        for i := 0; i < sz; i++ {
            // dequeue the front of the queue
            cur := q[0]
            q = q[1:]
            // visit the cur node and know its depth
            fmt.Printf("depth = %d, val = %d\n", depth, cur.Val)

            // add cur's left and right children to the queue
            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right)
            }
        }
        depth++
    }
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    let q = [];
    q.push(root);
    // record the current depth (root node is considered as level 1)
    let depth = 1;

    while (q.length !== 0) {
        let sz = q.length;
        for (let i = 0; i < sz; i++) {
            let cur = q.shift();
            // visit the cur node and know its depth
            console.log("depth = " + depth + ", val = " + cur.val);

            // add the left and right children of cur to the queue
            if (cur.left !== null) {
                q.push(cur.left);
            }
            if (cur.right !== null) {
                q.push(cur.right);
            }
        }
        depth++;
    }
};

class State {
    TreeNode node;
    int depth;

    State(TreeNode node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<State> q = new LinkedList<>();
    // the path weight sum of the root node is 1
    q.offer(new State(root, 1));

    while (!q.isEmpty()) {
        State cur = q.poll();
        // visit the cur node, while knowing its path weight sum
        System.out.println("depth = " + cur.depth + ", val = " + cur.node.val);

        // add the left and right child nodes of cur to the queue
        if (cur.node.left != null) {
            q.offer(new State(cur.node.left, cur.depth + 1));
        }
        if (cur.node.right != null) {
            q.offer(new State(cur.node.right, cur.depth + 1));
        }
    }
}

class State {
public:
    TreeNode* node;
    int depth;

    State(TreeNode* node, int depth) : node(node), depth(depth) {}
};

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<State> q;
    // the path weight sum of the root node is 1
    q.push(State(root, 1));

    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        // visit the cur node, while knowing its path weight sum
        cout << "depth = " << cur.depth << ", val = " << cur.node->val << endl;

        // add the left and right children of cur to the queue
        if (cur.node->left != nullptr) {
            q.push(State(cur.node->left, cur.depth + 1));
        }
        if (cur.node->right != nullptr) {
            q.push(State(cur.node->right, cur.depth + 1));
        }
    }
}

class State:
    def __init__(self, node, depth):
        self.node = node
        self.depth = depth

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    # the path weight sum of the root node is 1
    q.append(State(root, 1))

    while q:
        cur = q.popleft()
        # visit the cur node, and know its path weight sum
        print(f"depth = {cur.depth}, val = {cur.node.val}")

        # add the left and right child nodes of cur to the queue
        if cur.node.left is not None:
            q.append(State(cur.node.left, cur.depth + 1))
        if cur.node.right is not None:
            q.append(State(cur.node.right, cur.depth + 1))

type State struct {
    node  *TreeNode
    depth int
}

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []State{{root, 1}}

    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        // visit the cur node, also know its path weight sum
        fmt.Printf("depth = %d, val = %d\n", cur.depth, cur.node.Val)

        // add cur's left and right children to the queue
        if cur.node.Left != nil {
            q = append(q, State{cur.node.Left, cur.depth + 1})
        }
        if cur.node.Right != nil {
            q = append(q, State{cur.node.Right, cur.depth + 1})
        }
    }
}

function State(node, depth) {
    this.node = node;
    this.depth = depth;
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    // @visualize bfs
    var q = [];
    // the path weight sum of the root node is 1
    q.push(new State(root, 1));

    while (q.length !== 0) {
        var cur = q.shift();
        // visit the cur node, while knowing its path weight sum
        console.log("depth = " + cur.depth + ", val = " + cur.node.val);

        // add the left and right children of cur to the queue
        if (cur.node.left !== null) {
            q.push(new State(cur.node.left, cur.depth + 1));
        }
        if (cur.node.right !== null) {
            q.push(new State(cur.node.right, cur.depth + 1));
        }
    }
};

Principles of Binary Heap

The key application of binary heap is the priority queue. As a quick mastery tutorial, we can skip the implementation of the priority queue, but it is important to understand the following key points:

1. A priority queue is a data structure that can automatically sort, with a complexity of $O(\log N)$ for adding or removing elements, using a binary heap underneath.

2. A binary heap is a complete binary tree with special properties.

3. The core methods of priority queue (binary heap) are swim and sink, which are used to maintain the properties of the binary heap.

Use Cases of Segment Trees

Segment trees are a data structure that may be used in algorithm coding interviews. They can perform range queries and point updates in $O(\log N)$ time complexity.

The above article mainly explains the following points:

1. The functionality and use cases of segment trees. When you encounter similar scenarios, you will know that this special data structure can be used to solve problems efficiently.

2. Why the query and update complexity of segment trees is $O(\log N)$. This may be asked in interviews. The visualization panel on this site makes it easy to understand the underlying principles.

3. Segment trees can be implemented using linked structures or arrays. Why does the array-based implementation require 4 times the space during initialization?

As for the specific code implementation, you usually won't need to write it from scratch. You can refer to the code template provided in Segment Tree Code Implementation and use it directly when needed.

Graph Structures

Graph algorithms are a vast topic, but as part of the foundational data structures chapter, we only need to understand the logical representation and concrete implementation of graphs, as well as graph traversal algorithms.

It's not overly complex, essentially an extension of the binary tree structure discussed earlier. The following two articles provide a general implementation of graph structures and templates for traversal algorithms.

Start Practicing Problems

Now let's start practicing problems. If you are new to online coding platforms, you may first want to check LeetCode Guidelines to understand the basic rules of using LeetCode.

Linked Lists

The patterns for problems related to linked lists are relatively fixed, primarily involving the two-pointer technique.

An advanced technique for singly linked lists is recursive operations, though this approach is typically only mentioned during interviews. In written exams, standard pointer operations are usually sufficient.

Arrays

Techniques related to arrays mainly involve the two-pointer method, which can be categorized into fast-slow pointers and left-right pointers. Classic array two-pointer algorithms include binary search and sliding window.

Some readers ask why there is no special topic on string algorithms. This is because strings are essentially character arrays, and string algorithms are fundamentally array algorithms.

// Pseudocode framework of sliding window algorithm
void slidingWindow(String s) {
    // Use an appropriate data structure to record the data in
    // the window, which can vary according to the specific
    // For example, if I want to record the
    // frequency of elements in the window, I would
    // If I want to record the sum of elements in the window, I could just use an int
    Object window = ...
    
    int left = 0, right = 0;
    while (right < s.length()) {
        // c is the character that will be added to the window
        char c = s[right];
        window.add(c)
        // Expand the window
        right++;
        // Perform a series of updates to the data within the window
        ...

        // *** Position of debug output ***
        // Note that in the final solution code, do not use print
        // Because IO operations are time-consuming and may cause timeouts
        printf("window: [%d, %d)\n", left, right);
        // ***********************

        // Determine whether the left side of the window needs to shrink
        while (left < right && window needs shrink) {
            // d is the character that will be removed from the window
            char d = s[left];
            window.remove(d)
            // Shrink the window
            left++;
            // Perform a series of updates to the data within the window
            ...
        }
    }
}

// Pseudocode framework of sliding window algorithm
void slidingWindow(string s) {
    // Use an appropriate data structure to record the
    // data in the window, varying with the specific
    // For instance, if I want to record the
    // frequency of elements in the window, I would
    // If I want to record the sum of elements in the window, I can simply use an int
    auto window = ...

    int left = 0, right = 0;
    while (right < s.size()) {
        // c is the character that will be entering the window
        char c = s[right];
        window.add(c);
        // Expand the window
        right++;

        // Perform a series of updates to the data within the window
        ...

        // *** position of debug output ***
        printf("window: [%d, %d)\n", left, right);
        // Note that printing should be avoided in the final solution code
        // Because IO operations are time-consuming and may cause timeouts

        // Determine whether the left side of the window needs to shrink
        while (window needs shrink) {
            // d is the character that will be removed from the window
            char d = s[left];
            window.remove(d);
            // Shrink the window
            left++;

            // Perform a series of updates to the data within the window
            ...
        }
    }
}

# Pseudocode framework for sliding window algorithm
def slidingWindow(s: str):
    # Use an appropriate data structure to record the data
    # in the window, which can vary depending on the
    # For example, if I want to record the
    # frequency of elements in the window, I would
    # If I want to record the sum of elements in the window, I could just use an int
    window = ...

    left, right = 0, 0
    while right < len(s):
        # c is the character that will be added to the window
        c = s[right]
        window.add(c)
        # Expand the window
        right += 1
        # Perform a series of updates on the data within the window
        ...

        # *** position for debug output ***
        # Note that you should not print in the final solution code
        # because IO operations are time-consuming and may cause timeouts
        # print(f"window: [{left}, {right})")
        # ***********************

        # Determine whether the left side of the window needs to be contracted
        while left < right and window needs shrink:
            # d is the character that will be removed from the window
            d = s[left]
            window.remove(d)
            # Shrink the window
            left += 1
            # Perform a series of updates on the data within the window
            ...

// Pseudocode framework for sliding window algorithm
func slidingWindow(s string) {
    // Use an appropriate data structure to record the data in
    // the window, which can vary according to the specific
    // For example, if I want to record the frequency of elements in the window, I use a map
    // If I want to record the sum of elements in the window, I can just use an int
    var window = ...

    left, right := 0, 0
    for right < len(s) {
        // c is the character to be moved into the window
        c := rune(s[right])
        window[c]++
        // Expand the window
        right++
        // Perform a series of updates to the data within the window
        ...

        // *** debug output location ***
        // Note that in the final solution code, do not print
        // Because IO operations are time-consuming and may cause timeouts
        fmt.Println("window: [",left,", ",right,")")
        // ***********************

        // Determine whether the left window needs to shrink
        for left < right && window needs shrink {
            // d is the character to be moved out of the window
            d := rune(s[left])
            window[d]--
            // Shrink the window
            left++
            // Perform a series of updates to the data within the window
            ...
        }
    }
}

// Pseudocode framework for sliding window algorithm
var slidingWindow = function(s) {
    // Use an appropriate data structure to record the data
    // in the window, which can vary according to the
    // For example, if I want to record the frequency of elements in the window, I use a map
    // If I want to record the sum of the elements in the window, I can just use an int
    var window = ...;

    var left = 0, right = 0;
    while (right < s.length) {
        // c is the character that will be moved into the window
        var c = s[right];
        window.add(c);
        // Expand the window
        right++;
        // Perform a series of updates on the data within the window
        ...

        // *** debug output position ***
        // Note that in the final solution code, do not print
        // Because IO operations are time-consuming and may cause timeouts
        console.log("window: [%d, %d)\n", left, right);
        // *********************

        // Determine whether the left side of the window needs to shrink
        while (window needs shrink) {
            // d is the character that will be moved out of the window
            var d = s[left];
            window.remove(d);
            // Shrink the window
            left++;
            // Perform a series of updates on the data within the window
            ...
        }
    }
};

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // return directly
            return mid;
        }
    }
    // return directly
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // do not return, lock the left boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // check if nums[left] is the target
    return nums[left] == target ? left : -1;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // do not return, lock the right boundary
            left = mid + 1;
        }
    }
    // since the while loop ends with right == left -
    // 1 and we are now looking for the right boundary
    // it's easier to remember to use right instead of left - 1
    if (right < 0 || right >= nums.length) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

int binary_search(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // return directly
            return mid;
        }
    }
    // return directly
    return -1;
}

int left_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // do not return, lock the left boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    if (left < 0 || left >= nums.size()) {
        return -1;
    }
    // check if nums[left] is target
    return nums[left] == target ? left : -1;
}

int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // do not return, lock the right boundary
            left = mid + 1;
        }
    }
    // since the while loop ends when right == left
    // - 1, and we are now finding the right
    // so it's easier to remember to use right instead of left - 1
    if (right < 0 || right >= nums.size()) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

def binary_search(nums: List[int], target: int) -> int:
    # set left and right indexes
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        elif nums[mid] == target:
            # found the target value
            return mid
    # target value not found
    return -1

def left_bound(nums: List[int], target: int) -> int:
    # set left and right indexes
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        elif nums[mid] == target:
            # target exists, narrow the right boundary
            right = mid - 1
    # determine if the target exists
    if left < 0 or left >= len(nums):
        return -1
    # determine if the left boundary found is the target value
    return left if nums[left] == target else -1

def right_bound(nums: List[int], target: int) -> int:
    # set left and right indexes
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        elif nums[mid] == target:
            # target exists, narrow the left boundary
            left = mid + 1
    # determine if the target exists
    if right < 0 or right >= len(nums):
        return -1
    # determine if the right boundary found is the target value
    return right if nums[right] == target else -1

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] == target {
            // return directly
            return mid
        }
    }
    // return directly
    return -1
}

func leftBound(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] == target {
            // do not return, lock the left boundary
            right = mid - 1
        }
    }
    // determine if target exists in nums
    if left < 0 || left >= len(nums) {
        return -1
    }
    // determine if nums[left] is target
    if nums[left] == target {
        return left
    }
    return -1
}

func rightBound(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] == target {
            // do not return, lock the right boundary
            left = mid + 1
        }
    }
    
    if right < 0 || right >= len(nums) {
        return -1
    }
    if nums[right] == target {
        return right
    }
    return -1
}

var binary_search = function(nums, target) {
    var left = 0, right = nums.length - 1; 
    while(left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // return directly
            return mid;
        }
    }
    // return directly
    return -1;
}

var left_bound = function(nums, target) {
    var left = 0, right = nums.length - 1;
    while (left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // do not return, lock the left boundary
            right = mid - 1;
        }
    }
    // determine if target exists in nums
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // check if nums[left] is the target
    return nums[left] == target ? left : -1;
}

var right_bound = function(nums, target) {
    var left = 0, right = nums.length - 1;
    while (left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // do not return, lock the right boundary
            left = mid + 1;
        }
    }
    // since the loop ends when right == left - 1 and we are looking for the right boundary
    // so using right instead of left - 1 is easier to remember
    if (right < 0 || right >= nums.length) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

class NumArray {
    // prefix sum array
    private int[] preSum;

    // input an array to construct the prefix sum
    public NumArray(int[] nums) {
        // preSum[0] = 0, to facilitate the calculation of accumulated sums
        preSum = new int[nums.length + 1];
        // calculate the accumulated sums of nums
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    // query the sum of the closed interval [left, right]
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

#include <vector>

class NumArray {
    // prefix sum array
    std::vector<int> preSum;

    // input an array to construct the prefix sum
    public:
    NumArray(std::vector<int>& nums) {
        // preSum[0] = 0, to facilitate the calculation of accumulated sums
        preSum.resize(nums.size() + 1);
        // calculate the accumulated sums of nums
        for (int i = 1; i < preSum.size(); i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    // query the sum of the closed interval [left, right]
    int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
};

class NumArray:
    # prefix sum array
    def __init__(self, nums: List[int]):
        # input an array to construct the prefix sum
        # preSum[0] = 0, to facilitate the calculation of accumulated sums
        self.preSum = [0] * (len(nums) + 1)
        # calculate the accumulated sums of nums
        for i in range(1, len(self.preSum)):
            self.preSum[i] = self.preSum[i - 1] + nums[i - 1]

    # query the sum of the closed interval [left, right]
    def sumRange(self, left: int, right: int) -> int:
        return self.preSum[right + 1] - self.preSum[left]

type NumArray struct {
    // prefix sum array
    PreSum []int
}

// input an array to construct the prefix sum
func Constructor(nums []int) NumArray {
    // PreSum[0] = 0, to facilitate the calculation of accumulated sums
    preSum := make([]int, len(nums)+1)
    // calculate the accumulated sums of nums
    for i := 1; i < len(preSum); i++ {
        preSum[i] = preSum[i-1] + nums[i-1]
    }
    return NumArray{PreSum: preSum}
}

// query the sum of the closed interval [left, right]
func (this *NumArray) SumRange(left int, right int) int {
    // The following line includes the missing comment:
    // PreSum[0] = 0, to facilitate the calculation of accumulated sums
    return this.PreSum[right+1] - this.PreSum[left] // Here we are using the prefix sum property, no need to repeat the comment here.
}

var NumArray = function(nums) {
    // prefix sum array
    let preSum = new Array(nums.length + 1).fill(0);

    // preSum[0] = 0, to facilitate the calculation of accumulated sums
    preSum[0] = 0;

    // input an array to construct the prefix sum
    for (let i = 1; i < preSum.length; i++) {
        // calculate the accumulated sums of nums
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }

    this.preSum = preSum;
};

// query the sum of the closed interval [left, right]
NumArray.prototype.sumRange = function(left, right) {
    return this.preSum[right + 1] - this.preSum[left];
};

class NumMatrix {
    // preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    private int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0) return;
        // construct the prefix sum matrix
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // calculate the sum of elements for each matrix [0, 0, i, j]
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
            }
        }
    }

    // calculate the sum of elements in the submatrix [x1, y1, x2, y2]
    public int sumRegion(int x1, int y1, int x2, int y2) {
        // the sum of the target matrix is obtained by operations on four adjacent matrices
        return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
    }
}

#include <vector>

class NumMatrix {
    // preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    std::vector<std::vector<int>> preSum;

public:
    NumMatrix(std::vector<std::vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if (m == 0 || n == 0) return;
        // construct the prefix sum matrix
        preSum.resize(m + 1, std::vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // calculate the sum of elements for each matrix [0, 0, i, j]
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
            }
        }
    }
    
    // calculate the sum of elements in the submatrix [x1, y1, x2, y2]
    int sumRegion(int x1, int y1, int x2, int y2) {
        // the sum of the target matrix is obtained by operations on four adjacent matrices
        return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
    }
};

class NumMatrix:
    # preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    def __init__(self, matrix: List[List[int]]):
        m = len(matrix)
        n = len(matrix[0])
        if m == 0 or n == 0:
            return
        # construct the prefix sum matrix
        self.preSum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # calculate the sum of elements for each matrix [0, 0, i, j]
                self.preSum[i][j] = (self.preSum[i - 1][j] + self.preSum[i][j - 1] +
                                     matrix[i - 1][j - 1] - self.preSum[i - 1][j - 1])

    # calculate the sum of elements in the submatrix [x1, y1, x2, y2]
    def sumRegion(self, x1: int, y1: int, x2: int, y2: int) -> int:
        # the sum of the target matrix is obtained by operations on four adjacent matrices
        return (self.preSum[x2 + 1][y2 + 1] - self.preSum[x1][y2 + 1] -
                self.preSum[x2 + 1][y1] + self.preSum[x1][y1])

type NumMatrix struct {
    // preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    preSum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m := len(matrix)
    if m == 0 {
        return NumMatrix{}
    }
    n := len(matrix[0])
    if n == 0 {
        return NumMatrix{}
    }
    // construct the prefix sum matrix
    preSum := make([][]int, m+1)
    for i := range preSum {
        preSum[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            // calculate the sum of elements for each matrix [0, 0, i, j]
            preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1]
        }
    }
    return NumMatrix{preSum: preSum}
}

// calculate the sum of elements in the submatrix [x1, y1, x2, y2]
func (this *NumMatrix) SumRegion(x1, y1, x2, y2 int) int {
    // the sum of the target matrix is obtained by operations on four adjacent matrices
    return this.preSum[x2+1][y2+1] - this.preSum[x1][y2+1] - this.preSum[x2+1][y1] + this.preSum[x1][y1]
}

var NumMatrix = function(matrix) {
    let m = matrix.length, n = matrix[0].length;
    // preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    this.preSum = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
    if (m == 0 || n == 0) return;
    // construct the prefix sum matrix
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // calculate the sum of elements for each matrix [0, 0, i, j]
            this.preSum[i][j] = this.preSum[i-1][j] + this.preSum[i][j-1] + matrix[i - 1][j - 1] - this.preSum[i-1][j-1];
        }
    }
};

NumMatrix.prototype.sumRegion = function(x1, y1, x2, y2) {
    // calculate the sum of elements in the submatrix [x1, y1, x2, y2]
    // the sum of the target matrix is obtained by operations on four adjacent matrices
    return this.preSum[x2+1][y2+1] - this.preSum[x1][y2+1] - this.preSum[x2+1][y1] + this.preSum[x1][y1];
};

// Difference Array Utility Class
class Difference {
    // difference array
    private int[] diff;
    
    // input an initial array, range operations will be performed on this array
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // construct the difference array based on the initial array
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    // increment the closed interval [i, j] by val (can be negative)
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    // return the result array
    public int[] result() {
        int[] res = new int[diff.length];
        // construct the result array based on the difference array
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}