Learning Plan for Quick Mastery

Some readers have given feedback that the content on this site is indeed solid. If studied seriously, it is possible to fully master data structures and algorithms. However, their current issue is the lack of time. How can this be addressed?

Is it possible to focus on the essentials, first learning the must-know techniques, and quickly improve skills before gradually studying more in the future?

I believe this is a demand from a significant portion of readers. Therefore, I have specifically written this quick mastery directory to meet these readers' needs.

The quick mastery directory cannot cover everything, so if you have ample time, I still recommend learning in the order of the main site directory.

About Problem Sets

Readers often ask questions related to company problem sets, so I will elaborate here.

Different companies have different problem sets, with varying difficulty levels. The quick mastery directory includes must-know algorithm techniques and classic algorithm problems, not limited to any specific company’s problem set.

This directory aims to fundamentally tackle the tough challenge of algorithms, allowing you to independently solve medium-difficulty common algorithm problems with ease, rather than relying on luck and memorization of specific problem sets.

Some readers start preparing algorithms by directly tackling company problem sets, which is incorrect. My suggestion is to first understand the common algorithm frameworks, then consider practicing problem sets.

Regardless of the company’s problem set, algorithms are based on certain frameworks and techniques. Once you master these techniques, you can go through a problem set in just two to three hours at most, with no mystery involved.

Problem sets have only two values:

1. To understand the difficulty and types of algorithms a company might test. For example, if your company clearly states that dynamic programming algorithms will not be tested, you can skip that part in this directory and focus on other algorithm techniques.

2. For review purposes. After mastering the algorithm frameworks, you can independently solve problems, and then practice through problem sets to test learning outcomes and solidify knowledge points.

Below is a summary of the problem sets involved in this directory. Although there seem to be many problems, most are framework questions, and you can complete them all smoothly after learning the articles below, without needing to practice separately. This problem set is provided for review by readers who have completed this directory:

The Quick Mastery problem set is 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 the JetBrains plugin:

Principles of the Quick Mastery Catalog

Why can the Quick Mastery catalog rapidly enhance algorithm skills in a short time?

1. Template-based framework and unified solution style.

This catalog is not just a list of problems; it summarizes a set of framework templates for each algorithm. All exercises are solved using a unified framework. You learn genuine problem-solving skills rather than rote memorization, enabling you to independently tackle unfamiliar problems without being confined to a specific problem list.

2. Gradual progression from basic to advanced, including both data structures and algorithms.

An algorithm technique A might be derived from algorithms B and C. Without any background, directly learning A might seem esoteric. However, if you understand B and C, you can easily deduce A. For instance, many fear recursive algorithms; I often emphasize that the essence of algorithms is brute-force, and recursion is a classic brute-force method based on tree structures. Mastering binary tree structures allows you to excel in all recursive algorithms. This catalog starts with key data structures before tackling exercises, ensuring a strong foundation for efficient problem-solving.

3. Scientific learning methods and ample auxiliary tools. By combining examples and exercises, practicing after learning, and using problem-solving plugins and visualization panels, we strive to reduce comprehension costs and enhance learning efficiency.

I reiterate, I understand some readers are pressed for time, but do not skip frameworks and dive straight into problem-solving.

Relying solely on problem lists depends heavily on luck. Encountering a familiar problem might allow you to recall the solution, but without luck, solving requires algorithm frameworks. Without learning them, success is unlikely. A firm foundation saves time in the long run.

Let's begin. The Quick Mastery catalog is divided into "Data Structures" and "Algorithm Exercises" sections: the data structures section is simpler, focusing on fundamentals, while the exercises section is crucial, requiring thoughtful engagement and hands-on practice.

Data Structures

Arrays and Linked Lists

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

Principles and Applications of Hash Tables

As a quick mastery tutorial, we can skip the code implementations of the two methods for resolving hash collisions in hash tables, but 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 such as LinkedHashMap and ArrayHashMap. These structures add new features to hash tables. Understanding their principles will help you recognize these tools when encountering applicable scenarios.

Basics and Traversal of Binary Trees

Although this is just the basic knowledge section, the part on binary trees must be taken seriously. Especially the traversal of binary trees, which is key to understanding recursive thinking. Once you start practicing problems, all recursive algorithms are essentially traversals 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 Heaps

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

1. A priority queue is a data structure that automatically sorts, with the complexity of adding and removing elements being $O(\log N)$, implemented using a binary heap.

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

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

Use Cases for Segment Tree

Segment trees are a type of data structure that may be used in algorithm interviews to perform interval queries and updates with a time complexity of $O(\log N)$.

The above article mainly clarifies 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 efficiently solve the problem.

2. The reason why the query and update complexity of segment trees is $O(\log N)$. This point may be asked in interviews. The visualization panel on our site helps in understanding the underlying principles.

3. Segment trees can be implemented using a linked structure or an array. The array implementation of a segment tree requires four times the space during initialization.

For specific code implementations, you can save the AllInOneSegmentTree implementation provided at the end of Lazy Propagation in Segment Trees, which has all optimizations and APIs implemented. You can directly use it during interviews when needed.

Graph Structure

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

In essence, they are not very complex and are an extension of the binary tree structures discussed earlier. The following two articles provide general implementations of graph structures and templates for traversal algorithms.

Start Practicing

Begin your practice now. If this is your first time using an online coding platform, you may want to check LeetCode Guide to understand the basic rules of solving problems on LeetCode.

Linked List

The pattern of linked list problems is relatively fixed, mainly using the two-pointer technique.

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

Arrays

Techniques related to arrays mainly involve the two-pointer approach, which can be divided into different types such as fast and slow pointers, and left and right pointers. Classic two-pointer algorithms for arrays include binary search and sliding windows.

Some readers ask why there isn't a special topic on string algorithms, as 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 scenario
    // For example, if I want to record the frequency
    // of elements in the window, I would use a map
    // 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 scenario
    // For instance, if I want to record the frequency
    // of elements in the window, I would use a map
    // 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 scenario
    # For example, if I want to record the frequency
    # of elements in the window, I would use a map
    # 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 scenario
    // 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 scenario
    // 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 boundary
    // 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;
    }
}