850. Rectangle Area II
Problem Description
The task is to compute the total area covered by a set of rectangles in a 2D plane. Each rectangle is defined by its bottom-left and top-right corners. A crucial aspect of the problem is that if rectangles overlap, the overlapping area should only be counted once. This means that simply summing the areas of all rectangles will not suffice, as it could result in double-counting areas where rectangles intersect.
Intuition
To handle the complexity of overlapping rectangles, we break down the problem: First, we consider all edges of the rectangles (both left and right edges). These edges define "events" where we either start counting an area (left edge) or stop counting an area (right edge). To deal with vertical overlaps efficiently, we employ a sweep line algorithm with a segment tree.
The main idea is to sort the rectangle edges by their x-coordinates. As we sweep through the plane horizontally (left to right), we keep track of the y-coordinates of rectangle sides that are currently active, using a data structure that allows us to add or remove intervals (in this case, the y-intervals) efficiently. This is where the segment tree comes in handy. It allows us to add intervals (when we encounter a left edge) and remove intervals (when we encounter a right edge) while also keeping track of the total length of the covered interval on the y-axis at each step.
The segment tree is initialized with all unique y-coordinates of the rectangles to manage the intervals. We represent each segment tree node with the information of its y-interval, the count of how many rectangles are currently covering this interval (which can be incremented or decremented), and the length of the interval that is covered at least once.
When we move from one event to the next (from one x-coordinate to the next), we multiply the distance we have traveled on the x-axis with the total length of all the intervals that are currently covered on the y-axis. This gives us the area covered between these two x-coordinates, taking into account the vertical overlaps. We accumulate this area as we sweep through the events.
Finally, due to the possibility of very large numbers, the area is computed modulo 109 + 7, a computational technique used to keep the numbers within manageable limits while performing arithmetic operations.
Learn more about Segment Tree and Line Sweep patterns.
Which of these pictures shows the visit order of a depth-first search?
Solution Approach
The implementation follows a comprehensive approach leveraging several computer science concepts, particularly the sweep line algorithm and segment tree data structure. Here's how we translate our intuition into a concrete solution:
-
Event Collection and Sorting:
- Create a list,
segs, to represent the start and end events of the rectangles' y-intervals with their corresponding x-coordinates and an operation flag (1 for start, -1 for end). - Populate another set,
alls, with all unique y-coordinates in preparation for building the segment tree.
- Create a list,
-
Segment Tree Setup:
- Initialize the segment tree,
SegmentTree, using the sorted list derived from the set of y-coordinates. - The tree structure is set up such that each node represents an interval with its bounds and maintains the total covered length and count of overlaps within that interval.
- Initialize the segment tree,
-
Sweep Line Algorithm:
- Sort
segsbased on x-coordinates to ensure that we process events in the correct order. - Iterate through the events in
segs. At each step, perform the following:- Update the area by adding the product of the distance between the current x-coordinate and the previous one (
x - segs[i - 1][0]) with the current covered length from the segment tree (found intree.length). - Modify the segment tree to reflect the current event using
tree.modifymethod. This method adjusts the coverage count of relevant y-intervals based on whether it's a start or an end event (kis 1 when a rectangle begins and -1 when it ends).
- Update the area by adding the product of the distance between the current x-coordinate and the previous one (
- After each modification of the segment tree, rightly update the covered length of intervals.
- Sort
-
Calculate the Final Area:
- Since the area might be vast, we take the modulo of the sum with
10^9 + 7as per the problem's requirement before returning it as the result.
- Since the area might be vast, we take the modulo of the sum with
From the code, we observe:
- The
modifymethod on the segment tree adjusts thecntfor each node (interval), and subsequently updates thelengththat represents how much of each node's interval is covered. - The
pushupmethod is responsible for updating thelengthof a node based on whether the node itself is covered or its child nodes are covered.
The solution makes efficient use of a segment tree to manage the y-intervals while sweeping through the x-coordinates, ensuring no overlapping area on the y-axis is counted more than once. By accumulating the areas of y-intervals as we progress along the x-axis, we obtain the total area covered by the rectangles without double-counting overlaps.
Breadth first search can be used to find the shortest path between two nodes in a directed graph.
Example Walkthrough
Let us consider a set of three rectangles in a 2D plane with their corresponding bottom-left (bl) and top-right (tr) coordinates specified as follows:
- Rectangle 1: bl(1,1), tr(3,3)
- Rectangle 2: bl(2,2), tr(5,5)
- Rectangle 3: bl(4,0), tr(6,2)
Each rectangle can be represented by two events: the start of the rectangle (left edge) and the end of the rectangle (right edge). We would thus have the following edges:
- Rectangle 1 Start:
(1, (1, 3), 1)where1is the x-coordinate,(1, 3)the y-interval, and1the operation flag. - Rectangle 1 End:
(3, (1, 3), -1) - Rectangle 2 Start:
(2, (2, 5), 1) - Rectangle 2 End:
(5, (2, 5), -1) - Rectangle 3 Start:
(4, (0, 2), 1) - Rectangle 3 End:
(6, (0, 2), -1)
For events, we have two arrays:
- Segs (for events):
[(1, (1, 3), 1), (2, (2, 5), 1), (3, (1, 3), -1), (4, (0, 2), 1), (5, (2, 5), -1), (6, (0, 2), -1)] - Alls (for y-coordinates):
[0, 1, 2, 3, 5]
We then sort segs based on x-coordinates and alls to prepare for building the segment tree.
Next, we construct the segment tree with alls and initialize all cnt to 0, as initially, no intervals are covered.
Now, let's process each event in segs:
-
Process the first event (Rectangle 1 Start at x=1). After adding the y-interval (1,3) to the segment tree, the active intervals are [1,3]. The total area is still zero since we don't have a previous x-coordinate to compare with just yet.
-
Move to the next event (Rectangle 2 Start at x=2). Update the current covered length and y-intervals to include [2,5], along with the previous [1,3]. The area added is the covered length from the segment tree multiplied by the x-distance traveled (2-1=1). So, the area at this point accounts for a vertical strip from x=1 to x=2.
-
Proceed to the third event (Rectangle 1 End at x=3). Remove the y-interval (1,3). The area added is the covered length (now excluding [1,3] but still including [2,5]) multiplied by the x-distance (3-2=1).
-
Do the same for the next events, always updating the area with the product of the x-distance traveled and the covered length from the segment tree.
Finally, the total area is accumulated by adding the segments' areas while accounting for overlaps in y-intervals, and the result is then taken modulo (10^9 + 7).
This example shows the essence of the sweep line algorithm with the segment tree data structure to calculate the total area covered by overlapping rectangles without double-counting any overlapping sections.
Solution Implementation
1from typing import List
2
3class Node:
4 def __init__(self):
5 # Initialize the left and right pointers of the segment
6 self.left = self.right = 0
7 # Initialize the segment count and the total length of segments covered
8 self.count = self.total_length = 0
9
10class SegmentTree:
11 def __init__(self, nums: List[int]):
12 # Set the number of elements in the nums list
13 n = len(nums) - 1
14 # Store the nums list
15 self.nums = nums
16 # Initialize the segment tree with nodes
17 self.tree = [Node() for _ in range(n << 2)]
18 # Build the segment tree
19 self.build(1, 0, n - 1)
20
21 def build(self, index: int, left: int, right: int):
22 # Set the range for this node
23 self.tree[index].left, self.tree[index].right = left, right
24 # If it is not a leaf node
25 if left != right:
26 # Calculate mid point to divide the range
27 mid = (left + right) >> 1
28 # Recursively build the left and right subtrees
29 self.build(index << 1, left, mid)
30 self.build(index << 1 | 1, mid + 1, right)
31
32 def modify(self, index: int, left: int, right: int, value: int):
33 if self.tree[index].left >= left and self.tree[index].right <= right:
34 # If the range is covered, update count
35 self.tree[index].count += value
36 else:
37 # If range covers partially, propagate the modification to children
38 mid = (self.tree[index].left + self.tree[index].right) >> 1
39 if left <= mid:
40 self.modify(index << 1, left, right, value)
41 if right > mid:
42 self.modify(index << 1 | 1, left, right, value)
43 # After modification, update the length of covered segments
44 self.pushup(index)
45
46 def pushup(self, index: int):
47 if self.tree[index].count:
48 # If count is non-zero, use the actual length
49 self.tree[index].total_length = self.nums[self.tree[index].right + 1] - self.nums[self.tree[index].left]
50 elif self.tree[index].left == self.tree[index].right:
51 # If it is a leaf node with zero count
52 self.tree[index].total_length = 0
53 else:
54 # If not, the length is the sum of lengths of the children
55 self.tree[index].total_length = self.tree[index << 1].total_length + self.tree[index << 1 | 1].total_length
56
57 @property
58 def length(self) -> int:
59 # Return total length of the segments represented by the tree
60 return self.tree[1].total_length
61
62class Solution:
63 def rectangleArea(self, rectangles: List[List[int]]) -> int:
64 # Initialize segments for y-coordinates and set of all y-coordinates
65 segments = []
66 all_y = set()
67 # Collect segments and unique y-coordinates
68 for x1, y1, x2, y2 in rectangles:
69 # Collect opening and closing segments
70 segments.append((x1, y1, y2, 1))
71 segments.append((x2, y1, y2, -1))
72 # Collect unique y-coordinates
73 all_y.update([y1, y2])
74
75 # Sort segments by x-coordinate and all_y by value
76 segments.sort()
77 all_y = sorted(all_y)
78
79 # Create a segment tree instance
80 tree = SegmentTree(all_y)
81 # Map the y-coordinates to index in Segment Tree
82 y_to_index = {y: index for index, y in enumerate(all_y)}
83
84 # Initialize the answer to 0
85 answer = 0
86 for i, (x, y1, y2, value) in enumerate(segments):
87 if i:
88 # Accumulate area between two x-coordinates
89 answer += tree.length * (x - segments[i - 1][0])
90 # Modify the segment tree to update counts
91 tree.modify(1, y_to_index[y1], y_to_index[y2] - 1, value)
92
93 # Return the final answer modulo 1e9+7
94 answer %= int(1e9 + 7)
95 return answer
961import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4import java.util.TreeSet;
5
6class Node {
7 // Variables representing the interval's left and right boundaries,
8 // active count (how many rectangles cover this interval), and the
9 // total length covered by rectangles in this interval.
10 int left, right, count, length;
11}
12
13class SegmentTree {
14 private Node[] tree;
15 private int[] coordinates;
16
17 // Constructor initializes the segment tree with given coordinates.
18 public SegmentTree(int[] coordinates) {
19 this.coordinates = coordinates;
20 int n = coordinates.length - 1;
21 tree = new Node[n << 2]; // Size of segment tree array.
22 for (int i = 0; i < tree.length; ++i) {
23 tree[i] = new Node();
24 }
25 build(1, 0, n - 1);
26 }
27
28 // Build the segment tree recursively.
29 private void build(int u, int left, int right) {
30 tree[u].left = left;
31 tree[u].right = right;
32 if (left != right) {
33 int mid = (left + right) >> 1;
34 build(u << 1, left, mid);
35 build(u << 1 | 1, mid + 1, right);
36 }
37 }
38
39 // Update the segment tree by incrementing/decrementing counts over the interval [l, r].
40 public void modify(int u, int l, int r, int k) {
41 if (tree[u].left >= l && tree[u].right <= r) {
42 tree[u].count += k;
43 } else {
44 int mid = (tree[u].left + tree[u].right) >> 1;
45 if (l <= mid) {
46 modify(u << 1, l, r, k);
47 }
48 if (r > mid) {
49 modify(u << 1 | 1, l, r, k);
50 }
51 }
52 pushUp(u);
53 }
54
55 // Push up the changes in the segment tree from children to parent.
56 private void pushUp(int u) {
57 if (tree[u].count > 0) {
58 tree[u].length = coordinates[tree[u].right + 1] - coordinates[tree[u].left];
59 } else if (tree[u].left == tree[u].right) {
60 tree[u].length = 0;
61 } else {
62 tree[u].length = tree[u << 1].length + tree[u << 1 | 1].length;
63 }
64 }
65
66 // Query the total covered length in the segment tree.
67 public int query() {
68 return tree[1].length;
69 }
70}
71
72class Solution {
73 private static final int MOD = (int) 1e9 + 7;
74
75 // Computes the area of the union of rectangles provided in the input.
76 public int rectangleArea(int[][] rectangles) {
77 int n = rectangles.length;
78 int[][] segments = new int[n << 1][4];
79 int i = 0;
80 TreeSet<Integer> yCoordinates = new TreeSet<>();
81
82 // Discretize the y-coordinates and prepare the segments.
83 for (int[] rect : rectangles) {
84 int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
85 segments[i++] = new int[] {x1, y1, y2, 1}; // 'Start' segment.
86 segments[i++] = new int[] {x2, y1, y2, -1}; // 'End' segment.
87 yCoordinates.add(y1);
88 yCoordinates.add(y2);
89 }
90
91 // Sort segments by their x-coordinate.
92 Arrays.sort(segments, (a, b) -> a[0] - b[0]);
93
94 // Map the discrete y-coordinate to its index.
95 Map<Integer, Integer> map = new HashMap<>(yCoordinates.size());
96 i = 0;
97 int[] nums = new int[yCoordinates.size()];
98 for (int y : yCoordinates) {
99 map.put(y, i);
100 nums[i++] = y;
101 }
102
103 SegmentTree tree = new SegmentTree(nums);
104 long area = 0; // Use long to avoid overflow before taking modulo.
105
106 // Traverse segments and actualize the total covered length accordingly.
107 for (i = 0; i < segments.length; ++i) {
108 int[] segment = segments[i];
109 int x = segment[0], y1 = segment[1], y2 = segment[2], k = segment[3];
110 if (i > 0) {
111 area += (long) tree.query() * (x - segments[i - 1][0]);
112 }
113 tree.modify(1, map.get(y1), map.get(y2) - 1, k);
114 }
115 area %= MOD; // Take modulo to fit into the specified range.
116 return (int) area; // Cast back to int since result is now within int range.
117 }
118}
1191#include <vector>
2#include <set>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8// Definition of the Node class representing each segment tree node
9class Node {
10public:
11 int left, right, count, length;
12};
13
14// Definition of the SegmentTree class for handling interval modification and querying
15class SegmentTree {
16private:
17 vector<Node*> treeNodes; // Stores pointers to nodes of the segment tree
18 vector<int> sortedUniqueYCoordinates; // All unique y-coordinates sorted in ascending order
19
20 // Push up the calculated length from child nodes to the current node
21 void pushUp(int index) {
22 if (treeNodes[index]->count)
23 treeNodes[index]->length = sortedUniqueYCoordinates[treeNodes[index]->right + 1] - sortedUniqueYCoordinates[treeNodes[index]->left];
24 else if (treeNodes[index]->left == treeNodes[index]->right)
25 treeNodes[index]->length = 0;
26 else
27 treeNodes[index]->length = treeNodes[index << 1]->length + treeNodes[index << 1 | 1]->length;
28 }
29
30 // Build the segment tree
31 void build(int index, int left, int right) {
32 treeNodes[index]->left = left;
33 treeNodes[index]->right = right;
34 if (left != right) {
35 int mid = (left + right) >> 1;
36 build(index << 1, left, mid);
37 build(index << 1 | 1, mid + 1, right);
38 }
39 }
40
41public:
42 // Constructor initializes the segment tree
43 SegmentTree(vector<int>& nums) {
44 sortedUniqueYCoordinates = nums;
45 int n = nums.size() - 1;
46 treeNodes.resize(n << 2);
47 for (int i = 0; i < treeNodes.size(); ++i) treeNodes[i] = new Node();
48 build(1, 0, n - 1);
49 }
50
51 // Modify the count of nodes within a range [left, right] by value 'k'
52 void modify(int index, int left, int right, int k) {
53 if (treeNodes[index]->left >= left && treeNodes[index]->right <= right)
54 treeNodes[index]->count += k;
55 else {
56 int mid = (treeNodes[index]->left + treeNodes[index]->right) >> 1;
57 if (left <= mid) modify(index << 1, left, right, k);
58 if (right > mid) modify(index << 1 | 1, left, right, k);
59 }
60 pushUp(index);
61 }
62
63 // Query the total covered length in the segment tree
64 int query() {
65 return treeNodes[1]->length;
66 }
67};
68
69class Solution {
70public:
71 // Mod value to be used for obtaining the result within integer bounds
72 const int mod = 1e9 + 7;
73
74 // Function to calculate the area of rectangles
75 int rectangleArea(vector<vector<int>>& rectangles) {
76 int n = rectangles.size();
77 vector<vector<int>> segments(n << 1);
78 set<int> yAxisValues;
79 int index = 0;
80
81 // Extract and store rectangle coordinates, also populating the set
82 for (auto& rectangle : rectangles) {
83 int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
84 segments[index++] = {x1, y1, y2, 1};
85 segments[index++] = {x2, y1, y2, -1};
86 yAxisValues.insert(y1);
87 yAxisValues.insert(y2);
88 }
89
90 // Sort the segments by x-coordinate
91 sort(segments.begin(), segments.end());
92
93 // Map each y-coordinate to an index for array representation in the segment tree
94 unordered_map<int, int> y_to_index;
95 index = 0;
96 for (int yValue : yAxisValues) y_to_index[yValue] = index++;
97
98 // Converts the set of y-coordinates into a sorted vector
99 vector<int> sortedYCoords(yAxisValues.begin(), yAxisValues.end());
100
101 // Initialize the segment tree
102 SegmentTree* tree = new SegmentTree(sortedYCoords);
103
104 long long answer = 0;
105 // Go through all segments, modifying the count in the segment tree, updating the answer
106 for (int i = 0; i < segments.size(); ++i) {
107 auto& segment = segments[i];
108 int x = segment[0], y1 = segment[1], y2 = segment[2], k = segment[3];
109 if (i > 0) answer += (long long) tree->query() * (x - segments[i - 1][0]);
110 tree->modify(1, y_to_index[y1], y_to_index[y2] - 1, k);
111 }
112
113 // Return the final area modulo mod
114 answer %= mod;
115 return (int) answer;
116 }
117};
1181type Node = {
2 left: number;
3 right: number;
4 count: number;
5 length: number;
6};
7
8// Initialize a treeNodes array to hold the Node objects (Segment Tree)
9let treeNodes: Node[] = [];
10
11// Sorted unique y-coordinates used to determine the intervals
12let sortedUniqueYCoordinates: number[] = [];
13
14// Function to "push up" the calculated length from the child nodes to the current node
15function pushUp(index: number): void {
16 if (treeNodes[index].count > 0) {
17 treeNodes[index].length = sortedUniqueYCoordinates[treeNodes[index].right + 1] - sortedUniqueYCoordinates[treeNodes[index].left];
18 } else if (treeNodes[index].left === treeNodes[index].right) {
19 treeNodes[index].length = 0;
20 } else {
21 treeNodes[index].length = treeNodes[2 * index].length + treeNodes[2 * index + 1].length;
22 }
23}
24
25// Function to build the segment tree recursively for a given index and ranges [left, right]
26function build(index: number, left: number, right: number): void {
27 treeNodes[index] = { left, right, count: 0, length: 0 }; // Initialize the node
28 if (left !== right) {
29 const mid: number = Math.floor((left + right) / 2);
30 build(2 * index, left, mid);
31 build(2 * index + 1, mid + 1, right);
32 }
33}
34
35// Function to modify the count of nodes within a given range [left, right]
36function modify(index: number, left: number, right: number, deltaCount: number): void {
37 if (treeNodes[index].left >= left && treeNodes[index].right <= right) {
38 treeNodes[index].count += deltaCount;
39 } else {
40 const mid: number = Math.floor((treeNodes[index].left + treeNodes[index].right) / 2);
41 if (left <= mid) modify(2 * index, left, right, deltaCount);
42 if (right > mid) modify(2 * index + 1, left, right, deltaCount);
43 }
44 pushUp(index);
45}
46
47// Queries the total length that's covered in the segment tree
48function query(): number {
49 return treeNodes[1].length;
50}
51
52// Defines a constant mod value for integer boundary results
53const MOD: number = 1e9 + 7;
54
55// Function that calculates the area of rectangles
56function rectangleArea(rectangles: number[][]): number {
57 const n: number = rectangles.length;
58 const segments: number[][] = new Array(n * 2);
59 const yAxisValues: Set<number> = new Set();
60 let index: number = 0;
61
62 // Extract and store rectangle coordinates into segments and populate the set with y-axis values
63 rectangles.forEach(rectangle => {
64 const [x1, y1, x2, y2] = rectangle;
65 segments[index++] = [x1, y1, y2, 1];
66 segments[index++] = [x2, y1, y2, -1];
67 yAxisValues.add(y1);
68 yAxisValues.add(y2);
69 });
70
71 // Sort the segments based on the x-coordinate (along x-axis)
72 segments.sort((a, b) => a[0] - b[0]);
73
74 // Map y-coordinates to indices for array representation in the segment tree
75 const yAxisToIndex: Map<number, number> = new Map();
76 index = 0;
77 yAxisValues.forEach(yValue => yAxisToIndex.set(yValue, index++));
78
79 // Convert the set of y-coordinates to a sorted array
80 sortedUniqueYCoordinates = Array.from(yAxisValues).sort((a, b) => a - b);
81
82 // Initialize the segment tree with the y-coordinates
83 build(1, 0, sortedUniqueYCoordinates.length - 1);
84
85 let answer: number = 0;
86 segments.forEach((segment, i) => {
87 const [x, y1, y2, k] = segment;
88 if (i > 0) {
89 const width = x - segments[i - 1][0];
90 answer += query() * width;
91 answer %= MOD; // Make sure to calculate modulo at each step to prevent overflow
92 }
93 modify(1, yAxisToIndex.get(y1)!, yAxisToIndex.get(y2)! - 1, k);
94 });
95
96 return answer;
97}
98What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Time and Space Complexity
Time Complexity
The time complexity of the code can be broken down into several parts:
-
Initialization of the Segment Tree (
__init__andbuild):- The Segment Tree
buildfunction is called recursively and divides the range[l, r]into two halves each time. This division happens until each leaf represents a single element, which requiresO(log n)time for each interval, withnbeing the number of uniqueyvalues. - Since there's a total of
O(n)uniqueyvalues to build the tree with, the initialization time complexity isO(n log n).
- The Segment Tree
-
Modification of the Segment Tree (
modify):- The
modifyfunction is called for each x-coordinate in the list of segments. There are2nx-coordinates because each rectangle contributes two (start and end), which makes itO(m), wheremis twice the number of rectangles. - Within the
modifyfunction, in the worst case, we update nodes all the way from the root to the leaves, and potentially all leaves in unbalanced cases. The tree has a height ofO(log n), therefore the complexity of each modification isO(log n). - This operation is repeated
O(m)times (once for each distinct x-coordinate), leading to a time complexity ofO(m log n)for all modifications.
- The
-
Computation of the Total Length (in the loop within
rectangleArea):- We iterate through the sorted segments, and for each one, we update the tree and calculate the covered length. There are
2nsegments, so the loop runsO(m)times. - For each iteration, we calculate the covered length, which involves querying the root of the Segment Tree, which is an
O(1)operation. - The complexity of this part is dominated by the number of segments, which is
O(m).
- We iterate through the sorted segments, and for each one, we update the tree and calculate the covered length. There are
Overall, the time complexity is composed of the sum of the complexities of each part. Therefore, the final time complexity is primarily governed by the modify operation and is O(m log n) + O(n log n) + O(m), where m is twice the number of rectangles and n is the number of unique y values. Since O(m) is a subset of O(m log n), the overall time complexity simplifies to O(m log n).
Space Complexity
For space complexity:
-
Space for the Segment Tree (
tr):- A Segment Tree for
nelements generally requires4nspace because it is a full binary tree, which amounts toO(n)space.
- A Segment Tree for
-
Space for Miscellaneous Variables and Data Structures (
segs,alls,m):- The
segslist stores the start and end points of the segments and requires2mspaces (since there aremrectangles and each rectangle contributes two segments). - The
allsset stores sorted uniqueyvalues and requiresO(n)space. - The mapping
malso requiresO(n)space.
- The
Taking into consideration the maximum space required at any point in the program, the space complexity is O(n) + O(2m) + O(n) + O(n), which is O(n + m) overall. Here m is twice the number of rectangles, and n is the number of unique y values.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Line Sweep Introduction The primary motivation for this algorithm is for geometry related problems that we encounter in computer science Deeply rooted in geometric problem solving it has become an essential tool for tackling questions related to shapes lines or points on a Cartesian plane At its heart the line
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.