00. Prefix Sum & Line Swipe

Prefix Sum

Theory

Description

The prefix sum technique allows for efficient range sum queries by precomputing cumulative sums in an array.

Steps

1. Build the Prefix Sum Array:
   Create a new array prefix where each element at index i stores the sum of elements from the start of the array up to index i:
   

   prefix[0] = arr[0]
   prefix[1] = arr[0] + arr[1]
   prefix[2] = arr[0] + arr[1] + arr[2] 
   

   And so on…
   Example:
   For arr = [3, 1, 4, 1, 5, 9], the prefix_sum array is [3, 4, 8, 9, 14, 23].

2. Answer Range Sum Queries:
   To find the sum of elements between indices i and j, use:
   sum(i, j) = prefix[j] - prefix[i-1]
   Example:
   For arr = [3, 1, 4, 1, 5, 9], the sum from index 2 to 4:
   sum(2, 4) = prefix[4] - prefix[1] = 14 - 4 = 10.

Note

If i = 0, simply return prefix[j].

Time & Space Complexity

• Time: O(n) for building the prefix sum array, O(1) per query.
• Space: O(n) for storing the prefix sum array.

Problems

1. Range Sum Query - Immutable (Leetcode:303)

Problem Statement

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.
• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Constraints:

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105
• 0 <= left <= right < nums.length
• At most 104 calls will be made to sumRange.

Code & Explanation

class NumArray:
    def __init__(self, nums: List[int]):
        self.prefix_sum = [0] * (len(nums) + 1)

        for i in range(len(nums)):
            self.prefix_sum[i + 1] = self.prefix_sum[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix_sum[right + 1] - self.prefix_sum[left]

Explanation

1. Constructor (__init__):

   • Initializes a list prefix_sum where prefix_sum[i] stores the sum of the elements from index 0 to i-1.
   • Builds this prefix_sum array by iterating over the input list nums.

2. Method sumRange(left, right) :

   • Returns the sum of the subarray between indices left and right by calculating the difference:
     prefix_sum[right+1] - prefix_sum[left].
   • This allows constant time O(1) querying of subarray sums after the initial setup.

Time & Space: O(n) preprocessing, O(1) per query; O(n) extra space for the prefix array.

2. Left and Right Sum Differences (Leetcode:2574)

Problem Statement

Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:

• answer.length == nums.length.
• answer[i] = |leftSum[i] - rightSum[i]|.

Where:

• leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
• rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.
  Return the array answer.

Example 1:

Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation: The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].

Example 2:

Input: nums = [1]
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0].
The array answer is [|0 - 0|] = [0].

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 105

Code & Explanation

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        left_sum = 0
        right_sum = sum(nums)
        answer = []

        for num in nums:
            left_sum += num
            answer.append(abs(left_sum - right_sum))
            right_sum -= num

        return answer

Explanation

1. Initialization :

   • left_sum = 0: Tracks the sum of elements before the current index.
   • right_sum = sum(nums): Initially holds the total sum of all elements.
   • answer = []: Stores the result.

2. Loop through nums :

   • For each element num:
   • Update left_sum: Add num to left_sum.
   • Calculate and append absolute difference: |left_sum - right_sum| is appended to answer.
   • Update right_sum: Subtract num from right_sum.

3. Return answer :

   • After the loop, return the computed differences in answer.

Time & Space: O(n) time for one pass; O(1) extra space (excluding the output array).

3. XOR Queries of a Subarray (Leetcode:1310)

Problem Statement

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).

Return an array answer where answer[i] is the answer to the ith query.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation: The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8

Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

• 1 <= arr.length, queries.length <= 3 * 104
• 1 <= arr[i] <= 109
• queries[i].length == 2
• 0 <= lefti <= righti < arr.length

Code & Explanation

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:

        prefix = [0] * (len(arr) + 1)
        answer = []

        for i in range(len(arr)):
            prefix[i + 1] = prefix[i] ^ arr[i]

        for left, right in queries:
            answer.append(prefix[right + 1] ^ prefix[left])

        return answer

Explanation

1. Initialization:

   • prefix = [0] * (len(arr) + 1): Create a list prefix to store the cumulative XOR of elements in the array. The extra element accounts for the starting point (index 0).
   • answer = []: This will store the result for each query.

2. Build Prefix XOR Array:

   • For each element arr[i] in the array, compute the cumulative XOR up to that index:
   • prefix[i + 1] = prefix[i] ^ arr[i]: This updates the prefix list, where each entry at i + 1 holds the XOR of all elements from the start of the array up to index i.

3. Process Queries:

   • For each query [left, right], calculate the XOR of elements from index left to right:
   • answer.append(prefix[right + 1] ^ prefix[left]): This uses the precomputed prefix array. The XOR of the subarray from left to right is found by subtracting the prefix XORs at left and right + 1.

4. Return the Answer:

   • The final answer list contains the result for each query, which is the XOR of the elements in the subarray defined by left and right.

Time & Space: O(n + q) time for n elements and q queries; O(n) extra space for the prefix XOR array.

4. Subarray Sum Equals K (Leetcode:560)

Problem Statement

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

Code & Explanation

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        prefix_sum = 0
        dictionary = {0:1}  # Start with {0:1} to handle subarrays starting from the beginning

        for num in nums:
            prefix_sum += num  # Update prefix sum
            diff = prefix_sum - k  # Find the difference between the current prefix sum and target k
            if diff in dictionary:  # If this diff has been seen before, increment count
                count += dictionary[diff]
            dictionary[prefix_sum] = dictionary.get(prefix_sum, 0) + 1  # Update the dictionary

        return count

Explanation

1. Initialization:

   • count = 0: To store the number of valid subarrays.
   • prefix_sum = 0: To keep track of the cumulative sum as we iterate through the array.
   • dictionary = {0: 1}: This keeps track of how many times a certain prefix sum has occurred.
   • We start with {0: 1} because a sum of 0 is possible before we start processing the array.

2. Iterate through the array:

   • For each element num in the array, update the prefix_sum by adding num to it.
   • Compute the difference diff = prefix_sum - k. If diff exists in the dictionary, it means there are subarrays whose sum equals k, and their count is stored in the dictionary.
   • Increment count by the number of times diff has occurred.
   • Update the dictionary by increasing the count of prefix_sum.

3. Return the count:

   • This gives the total number of subarrays whose sum equals k.

Time & Space: O(n) time for a single pass; O(n) extra space for the prefix-sum frequency map.

5. Product of Array Except Self (Leetcode:238)

Problem Statement

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up:

Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Code & Explanation

Approach 1

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    answer = [1] * n

    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]

    return answer

Explanation:

1. First pass (prefix products):
2. Initialize answer to all 1s and walk left to right.

3. At index i, store the product of everything to the left in answer[i], then update running prefix.

4. Second pass (suffix products):

5. Walk right to left with a running suffix product.

6. Multiply answer[i] by the suffix product of all elements to the right.

7. Why it works:

8. Each index gets (product of left side) × (product of right side) without division.
9. Time is O(n) and extra space is O(1) excluding the output array.

Time & Space: O(n) time, two passes; O(1) extra space (output array not counted).

6. Increment Submatrices by One (Leetcode:2536)

Problem Statement

You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes.

You are also given a 2D integer array query. For each query[i] = [row1i, col1i, row2i, col2i], you should do the following operation:

Add 1 to every element in the submatrix with the top left corner (row1i, col1i) and the bottom right corner (row2i, col2i). That is, add 1 to mat[x][y] for all row1i <= x <= row2i and col1i <= y <= col2i.

Return the matrix mat after performing every query.

Example 1:

Input: n = 3, queries = [[1,1,2,2],[0,0,1,1]]
Output: [[1,1,0],[1,2,1],[0,1,1]]
Explanation: The diagram above shows the initial matrix, the matrix after the first query, and the matrix after the second query.
- In the first query, we add 1 to every element in the submatrix with the top left corner (1, 1) and bottom right corner (2, 2).
- In the second query, we add 1 to every element in the submatrix with the top left corner (0, 0) and bottom right corner (1, 1).

Example 2:

Input: n = 2, queries = [[0,0,1,1]]
Output: [[1,1],[1,1]]
Explanation: The diagram above shows the initial matrix and the matrix after the first query.
- In the first query we add 1 to every element in the matrix.

Constraints:

1 <= n <= 500
1 <= queries.length <= 10^4
0 <= row1i <= row2i < n
0 <= col1i <= col2i < n

Code & Explanation

Approach 1

def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
    diff = [[0] * (n + 1) for _ in range(n + 1)]

    for r1, c1, r2, c2 in queries:
        diff[r1][c1] += 1
        if c2 + 1 < n:
            diff[r1][c2 + 1] -= 1
        if r2 + 1 < n:
            diff[r2 + 1][c1] -= 1
        if r2 + 1 < n and c2 + 1 < n:
            diff[r2 + 1][c2 + 1] += 1

    mat = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            top = mat[i-1][j] if i > 0 else 0
            left = mat[i][j-1] if j > 0 else 0
            corner = mat[i-1][j-1] if i > 0 and j > 0 else 0
            mat[i][j] = diff[i][j] + top + left - corner

    return mat

Explanation:

1. 2D difference array:
2. For each query rectangle, add +1 at top-left and apply -1 at the boundaries just outside the rectangle.

3. This marks where increments start and stop without updating every cell.

4. Prefix reconstruction:

5. Convert the difference grid into the final matrix using 2D prefix sums:
   mat[i][j] = diff[i][j] + mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1].

6. Why it works:

7. Each query costs O(1) marking time instead of O(n²) brute-force updates.
8. Overall complexity is O(n² + q) for q queries on an n × n matrix.

Time & Space: O(n² + q) time; O(n²) extra space for the difference and result grids.

7. Range Sum Query 2D - Immutable (Leetcode:304)

Problem Statement

Given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:
NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

You must design an algorithm where sumRegion works on O(1) time complexity.

Example 1:

Input:
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output:
[null, 8, 11, 12]
Explanation:
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-10^4 <= matrix[i][j] <= 10^4
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
At most 10^4 calls will be made to sumRegion.

Code & Explanation

Approach 1

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):

        if not matrix or not matrix[0]:
            return

        m, n = len(matrix), len(matrix[0])
        # Create prefix sum matrix with an extra row and column
        self.prefixSum = [[0] * (n + 1) for _ in range(m + 1)]

        # Compute prefix sums
        for i in range(m):
            for j in range(n):
                self.prefixSum[i+1][j+1] = (
                    matrix[i][j]
                    + self.prefixSum[i][j+1]
                    + self.prefixSum[i+1][j]
                    - self.prefixSum[i][j]
                )

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (
            self.prefixSum[row2+1][col2+1]
            - self.prefixSum[row1][col2+1]
            - self.prefixSum[row2+1][col1]
            + self.prefixSum[row1][col1]
        )


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

Explanation:

1. Build 2D prefix sums:

2. Use an extra row and column of zeros so rectangle sums can be computed with inclusion-exclusion.

3. Query in O(1):

4. For rectangle (row1, col1) to (row2, col2), subtract the top and left strips and add back the overlapping corner:
   prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1].

5. Why it works:

6. Preprocessing takes O(mn); each sumRegion call is constant time.

Time & Space: O(mn) preprocessing, O(1) per query; O(mn) extra space for the 2D prefix grid.

8. Power of Heroes (Leetcode:2681)

Problem Statement

You are given a 0-indexed integer array nums representing the strength of some heroes. The power of a group of heroes is defined as follows:

Let i0, i1, ... ,ik be the indices of the heroes in a group. Then, the power of this group is max(nums[i0], nums[i1], ... ,nums[ik])2 * min(nums[i0], nums[i1], ... ,nums[ik]).

Return the sum of the power of all non-empty groups of heroes possible. Since the sum could be very large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [2,1,4]
Output: 141
Explanation:
1st group: [2] has power = 22 * 2 = 8.
2nd group: [1] has power = 12 * 1 = 1.
3rd group: [4] has power = 42 * 4 = 64.
4th group: [2,1] has power = 22 * 1 = 4.
5th group: [2,4] has power = 42 * 2 = 32.
6th group: [1,4] has power = 42 * 1 = 16.
​​​​​​​7th group: [2,1,4] has power = 42​​​​​​​ * 1 = 16.
The sum of powers of all groups is 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141.

Example 2:

Input: nums = [1,1,1]
Output: 7
Explanation: A total of 7 groups are possible, and the power of each group will be 1. Therefore, the sum of the powers of all groups is 7.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

Code & Explanation

Approach 1

def sumOfPower(self, nums: List[int]) -> int:
    MOD = 10**9 + 7
    nums.sort()
    res = 0
    prefixSum = 0

    for x in nums:
        contribution = (x * x % MOD) * ((x + prefixSum) % MOD) % MOD
        res = (res + contribution) % MOD
        prefixSum = (prefixSum * 2 + x) % MOD

    return res

Explanation:

1. Sort heroes:

2. After sorting, when x is processed in ascending order, every earlier value can be the minimum of a group whose maximum is x.

3. Prefix contribution:

4. For current max x, groups with min x contribute x² × x.
5. Groups with an earlier minimum contribute x² × (earlier min value).

6. prefixSum tracks the sum of all valid minimums from previous elements, doubled at each step because each earlier hero can either be included or excluded.

7. Modulo arithmetic:

8. Apply % (10⁹ + 7) after each multiplication/addition to avoid overflow.

Time & Space: O(n log n) time for sorting; O(1) extra space.

Problems at a glance

LC	Problem
303	1. Range Sum Query - Immutable	↗
2574	2. Left and Right Sum Differences	↗
1310	3. XOR Queries of a Subarray	↗
560	4. Subarray Sum Equals K	↗
238	5. Product of Array Except Self	↗
2536	6. Increment Submatrices by One	↗
304	7. Range Sum Query 2D - Immutable	↗
2681	8. Power of Heroes	↗
2848	1. Points That Intersect With Cars	↗
1893	2. Check if All the Integers in a Range Are Covered	↗
452	3. Minimum Number of Arrows to Burst Balloons	↗
1094	4. Car Pooling	↗
731	5. My Calendar II	↗
2251	6. Number of Flowers in Full Bloom	↗
732	7. My Calendar III	↗
1326	8. Minimum Number of Taps to Open to Water a Garden	↗
1851	9. Minimum Interval to Include Each Query	↗
218	10. The Skyline Problem	↗

---

Line Sweep

Theory

Description

The Line Sweep Algorithm is a powerful technique used in computational geometry. It's an efficient way to solve problems like detecting intersections, finding the closest pair of points, or calculating the convex hull. Let’s break down the core concepts of this algorithm to understand how it works.

What is the Sweep Line?

The sweep line is an imaginary vertical line that moves across a plane from left to right. As it moves, it sweeps through the objects in its path, processing important events at each step. Imagine it like a curtain slowly moving across a stage, revealing different parts of a scene. In the context of algorithms, this "curtain" moves across the plane, checking and reacting to specific points where events occur.

The sweep line doesn’t just move randomly—it advances through key points, called events, which are defined based on the specific problem being solved. By focusing on these events, the algorithm can efficiently process only the relevant parts of the data.

What are Events?

An event is a point on the plane where something significant happens as the sweep line moves. These events are the heart of the algorithm because they trigger actions like adding or removing objects, or checking for interactions. Depending on the problem you're solving, events could include:

• Start events: The beginning of an object, such as the left endpoint of a line segment or the opening of a rectangle.
• End events: The end of an object, like the right endpoint of a line segment or the closing of a rectangle.
• Intersection events: When two objects, like two line segments, intersect or overlap.

The sweep line processes these events in order, one by one, and each event may lead to an update in the algorithm’s state—whether it’s adding a new object, removing one, or checking for an intersection.

How Does it Work?

Here’s how the line sweep algorithm works in practice:

• Sort the events: The first step is to sort all the events in order of their position along the x-axis (left to right). For example, if you are working with line segments, this would mean sorting by the x-coordinate of the start and end points of each segment.

• Process events in order: The sweep line starts at the leftmost event and moves to the right. For each event, you do something specific:

• When the sweep line reaches a start event (like the left endpoint of a line segment), the segment is added to a list of active objects.
• When the sweep line reaches an end event (like the right endpoint), that segment is removed from the list of active objects.
• At each step, the algorithm may check for intersections or other interactions between active objects (e.g., checking if newly added segments intersect with others already in the list).

By sorting and processing events in this way, the algorithm can handle complex geometric problems without having to check every possible pair of objects, which would be much slower.

Problems

1. Points That Intersect With Cars (Leetcode:2848)

Problem Statement

You are given a 0-indexed 2D integer array nums representing the coordinates of the cars parking on a number line.
For any index i, nums[i] = [starti, endi] where starti is the starting point of the ith car and endi is the ending point of the ith car.

Return the number of integer points on the line that are covered with any part of a car.

Example 1:

Input: nums = [[3,6],[1,5],[4,7]]
Output: 7
Explanation: All the points from 1 to 7 intersect at least one car, therefore the answer would be 7.

Example 2:

Input: nums = [[1,3],[5,8]]
Output: 7
Explanation: Points intersecting at least one car are 1, 2, 3, 5, 6, 7, 8. There are a total of 7 points, therefore the answer would be 7.

Constraints:

1 <= nums.length <= 100
nums[i].length == 2
1 <= starti <= endi <= 100

Code & Explanation

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:

        line = [0] * 102
        points_on_line = 0

        for start,end in nums:
            line[start] += 1
            line[end + 1] -= 1

        for i in range(1, 102):
            line[i] += line[i - 1]
            if line[i] != 0:
                points_on_line += 1

        return points_on_line

Explanation:

1. Mark interval boundaries:

2. For each car [start, end], add +1 at start and -1 at end + 1.

3. Prefix sweep:

4. Prefix sum over the difference array gives how many cars cover each integer point.

5. Count covered points:

6. Any position with a non-zero prefix value is covered by at least one car.

Time & Space: O(n + U) time where U is the coordinate range; O(U) extra space for the difference array.

2. Check if All the Integers in a Range Are Covered (Leetcode:1893)

Problem Statement

You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [starti, endi]represents an inclusive interval between starti and endi.

Return true if each integer in the inclusive range [left, right] is covered by at least one interval in ranges. Return false otherwise.

An integer x is covered by an interval ranges[i] = [starti, endi] if starti <= x <= endi.

Example 1:

Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
Output: true
Explanation: Every integer between 2 and 5 is covered:
- 2 is covered by the first range.
- 3 and 4 are covered by the second range.
- 5 is covered by the third range.

Example 2:

Input: ranges = [[1,10],[10,20]], left = 21, right = 21
Output: false
Explanation: 21 is not covered by any range.

Constraints:

1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50

Code & Explanation

class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        line = [0] * 52

        for start,end in ranges:
            line[start]+=1
            line[end+1]-=1

        for i in range(1, 52):
            line[i] += line[i - 1]

        for i in range(left, right+1):
            if line[i]<1:
                return False

        return True

Explanation:

1. Build coverage counts:

2. Use the same difference-array technique: +1 at each interval start, -1 just after each end.

3. Sweep to get active coverage:

4. Prefix sum converts boundary marks into the number of intervals covering each integer.

5. Validate query range:

6. Return false if any integer in [left, right] has coverage < 1; otherwise return true.

Time & Space: O(r + U) time for r ranges over coordinate universe U; O(U) extra space.

3. Minimum Number of Arrows to Burst Balloons (Leetcode:452)

Problem Statement

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

1 <= points.length <= 10^5
points[i].length == 2
-2^31 <= xstart < xend <= 2^31 - 1

Code & Explanation

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda interval: interval[1])

        arrows = 0
        arrow_position = float("-inf")

        for start, end in points:
            if start > arrow_position:
                arrows += 1
                arrow_position = end

        return arrows

Explanation:

1. Sweep intervals by end point:

2. Sort balloons by right endpoint so the sweep line processes expiring intervals in order.

3. Place arrows at sweep events:

4. Track the current arrow position.

5. When a balloon starts after that position, shoot a new arrow at its end.

6. Why it works:

7. Processing intervals in sweep order and placing each arrow as far right as possible maximizes overlap with future balloons.

Time & Space: O(n log n) time for sorting; O(1) extra space.

4. Car Pooling (Leetcode:1094)

Problem Statement

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Example 2:

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Constraints:

1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengersi <= 100
0 <= fromi < toi <= 1000
1 <= capacity <= 10^5

Code & Explanation

class Solution(object):
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        locations = [0] * 1001
        for numPassengers, start, end in trips:
            locations[start] += numPassengers
            locations[end] -= numPassengers

        for numPassengers in locations:
            capacity -= numPassengers
            if capacity < 0: 
                return False

        return True

Explanation:

1. Passenger difference array:

2. Add passengers at pickup location start and subtract them at drop location end.

3. Simulate the route:

4. Sweep from left to right, reducing remaining capacity by the net passenger change at each stop.

5. Feasibility check:

6. If capacity ever goes negative, the trips cannot all be served.

Time & Space: O(t + L) time for t trips over L locations; O(L) extra space for the difference array.

5. My Calendar II (Leetcode:731)

Problem Statement

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).

The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.

Implement the MyCalendarTwo class:

• MyCalendarTwo() Initializes the calendar object.
• boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input:
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output:
[null, true, true, true, false, true, true]
>Explanation:
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking. myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Constraints:

0 <= start < end <= 109
At most 1000 calls will be made to book.

Code & Explanation

Approach 1

from collections import defaultdict

class MyCalendarTwo:
    def __init__(self):
        self.timeline = defaultdict(int)

    def book(self, startTime: int, endTime: int) -> bool:
        self.timeline[startTime] += 1
        self.timeline[endTime] -= 1

        ongoing = 0
        for time in sorted(self.timeline):
            ongoing += self.timeline[time]
            if ongoing >= 3:
                self.timeline[startTime] -= 1
                self.timeline[endTime] += 1
                return False

        return True

# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)

Explanation:

1. Mark booking events:

2. Add +1 at startTime and -1 at endTime on a timeline difference map.

3. Sweep active bookings:

4. Sort timeline keys and walk left to right, accumulating the current overlap count.

5. Reject triple bookings:

6. If any point reaches overlap >= 3, roll back the new booking and return false.

Time & Space: O(k log k) per book call where k is distinct timeline keys; O(k) extra space.

6. Number of Flowers in Full Bloom (Leetcode:2251)

Problem Statement

You are given a 0-indexed 2D integer array flowers, where flowers[i] = [starti, endi] means the ith flower will be in full bloom from starti to endi (inclusive). You are also given a 0-indexed integer array people of size n, where people[i] is the time that the ith person will arrive to see the flowers.

Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the ith person arrives.

Example 1:
Input: flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
Output: [1,2,2,2]
Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.

Example 2:

Input: flowers = [[1,10],[3,3]], people = [3,3,2]
Output: [2,2,1]
Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.

Constraints:

1 <= flowers.length <= 5 * 10^4
flowers[i].length == 2
1 <= starti <= endi <= 10^9
1 <= people.length <= 5 * 10^4
1 <= people[i] <= 10^9

Code & Explanation

Approach 1

def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:

    events: List[Tuple[int, int, int]] = []

    # Encode flower bloom events
    for start, end in flowers:
        events.append((start, 1, -1))       # +1 bloom starts at start time
        events.append((end + 1, -1, -1))    # -1 bloom ends just after end time

    # Encode people's arrival events
    for idx, arrival_time in enumerate(people):
        events.append((arrival_time, 2, idx))  # 2 = person arrives

    # Sort all events:
    # - First by time
    # - Then by event type: start (1), person (2), end (-1) in that order
    events.sort()

    blooming_flowers = 0
    result = [0] * len(people)

    for time, event_type, idx in events:
        if event_type == 2:  # person arrival
            result[idx] = blooming_flowers
        else:
            blooming_flowers += event_type  # +1 for start, -1 for end

    return result

Explanation:

1. Create mixed events:

2. Flower start adds +1, flower end adds -1 at end + 1, and each person arrival is a query event.

3. Sort events:

4. Process all events in time order so the active bloom count is always correct when a person arrives.

5. Answer queries during sweep:

6. Maintain blooming_flowers while sweeping; when a person event is seen, record the current count in result.

Time & Space: O((f + p) log (f + p)) time for f flowers and p people; O(f + p) extra space for events.

7. My Calendar III (Leetcode:732)

Problem Statement

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

• MyCalendarThree() Initializes the object.
• int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]
Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

Constraints:

0 <= startTime < endTime <= 10^9
At most 400 calls will be made to book.

Code & Explanation

Approach 1

class MyCalendarThree:

    def __init__(self):
        self.timeline = defaultdict(int)
        self.max_overlap = 0

    def book(self, startTime: int, endTime: int) -> int:
        self.timeline[startTime] += 1
        self.timeline[endTime] -= 1

        # Sweep line
        ongoing = 0
        for time in sorted(self.timeline):
            ongoing += self.timeline[time]
            self.max_overlap = max(self.max_overlap, ongoing)

        return self.max_overlap

# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)

Explanation:

1. Timeline difference map:

2. +1 at startTime, -1 at endTime marks where active bookings change.

3. Sweep active bookings:

4. Sort all timeline keys and walk left to right, accumulating the current overlap count.

5. Track maximum k-booking:

6. After each book call, update and return the highest overlap seen so far.

Time & Space: O(k log k) per book call; O(k) extra space for the timeline map.

8. Minimum Number of Taps to Open to Water a Garden (Leetcode:1326)

Problem Statement

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e., the length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Constraints:

1 <= n <= 104
ranges.length == n + 1
0 <= ranges[i] <= 100

Code & Explanation

Approach 1

def minTaps(self, n: int, ranges: List[int]) -> int:
    intervals = []

    for i, r in enumerate(ranges):
        left = max(0, i - r)
        right = min(n, i + r)
        if left <= right:
            intervals.append((left, right))

    intervals.sort()
    taps_opened = 0
    current_end = 0
    next_end = 0
    index = 0

    while current_end < n:
        while index < len(intervals) and intervals[index][0] <= current_end:
            next_end = max(next_end, intervals[index][1])
            index += 1

        if next_end == current_end:
            return -1

        taps_opened += 1
        current_end = next_end

    return taps_opened

Explanation:

1. Convert taps to intervals:
2. Tap i with range r covers [max(0, i - r), min(n, i + r)].

3. Sort intervals by start so the sweep line can process them in order.

4. Sweep from left to right:

5. At each covered position, collect all intervals that start before the current coverage ends and track the farthest reachable point.

6. Take minimum jumps:

7. Open one tap per sweep jump. If coverage cannot advance, return -1.

Time & Space: O(n log n) time for sorting intervals; O(n) extra space.

9. Minimum Interval to Include Each Query (Leetcode:1851)

Problem Statement

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

Constraints:

• 1 <= intervals.length <= 105
• 1 <= queries.length <= 105
• intervals[i].length == 2
• 1 <= lefti <= righti <= 107
• 1 <= queries[j] <= 107

Code & Explanation

Approach 1Approach 2

import heapq

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort(key=lambda interval: interval[1] - interval[0])
        sorted_queries = sorted((query, index) for index, query in enumerate(queries))

        result = [-1] * len(queries)
        min_heap = []
        interval_index = 0

        for query, query_index in sorted_queries:
            while interval_index < len(intervals) and intervals[interval_index][0] <= query:
                left, right = intervals[interval_index]
                heapq.heappush(min_heap, (right - left + 1, right))
                interval_index += 1

            while min_heap and min_heap[0][1] < query:
                heapq.heappop(min_heap)

            if min_heap:
                result[query_index] = min_heap[0][0]

        return result

Explanation:

1. Sort intervals by size:

2. Smaller intervals are considered first when multiple intervals cover a query.

3. Process queries in increasing order:

4. Add every interval whose left endpoint is <= query into a min heap keyed by interval size.

5. Remove expired intervals:

6. Pop intervals whose right endpoint is < query.
7. The heap top gives the smallest valid interval size, or -1 if the heap is empty.

Time & Space: O(n log n + q log q) time; O(n + q) extra space for the heap and result.

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        events = []
        for left, right in intervals:
            size = right - left + 1
            events.append((left, 1, size, right))
            events.append((right + 1, 0, size, right))

        indexed_queries = sorted((query, index) for index, query in enumerate(queries))
        events.sort()
        result = [-1] * len(queries)

        active_sizes = []
        event_index = 0
        query_index = 0

        while query_index < len(indexed_queries):
            query, original_index = indexed_queries[query_index]

            while event_index < len(events) and events[event_index][0] <= query:
                _, event_type, size, _ = events[event_index]
                if event_type == 1:
                    active_sizes.append(size)
                else:
                    active_sizes.remove(size)
                event_index += 1

            if active_sizes:
                result[original_index] = min(active_sizes)

            query_index += 1

        return result

Explanation:

1. Create sweep events:

2. Interval start adds its size to the active set; interval end removes it at right + 1.

3. Sort events and queries:

4. Walk both lists in time order so each query sees exactly the intervals covering it.

5. Track active interval sizes:

6. The answer for a query is the minimum size among currently active intervals.

Time & Space: O((n + q) log (n + q)) time; O(n + q) extra space for events.

10. The Skyline Problem (Leetcode: 218)

Problem Statement

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

• lefti is the x coordinate of the left edge of the ith building.
• righti is the x coordinate of the right edge of the ith building.
• heighti is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]

Example 1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

Constraints:

• 1 <= buildings.length <= 104
• 0 <= lefti < righti <= 231 - 1
• 1 <= heighti <= 231 - 1
• buildings is sorted by lefti in non-decreasing order.

Code & Explanation

Approach 1Approach 2

import heapq
from collections import defaultdict

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        events = []
        for left, right, height in buildings:
            events.append((left, -height, right))
            events.append((right, 0, 0))
        events.sort()

        result = []
        max_heap = [(0, float("inf"))]
        removed = defaultdict(int)
        index = 0

        while index < len(events):
            x = events[index][0]

            while index < len(events) and events[index][0] == x:
                _, neg_height, end = events[index]
                if neg_height != 0:
                    heapq.heappush(max_heap, (neg_height, end))
                index += 1

            while max_heap[0][1] <= x:
                removed[max_heap[0]] += 1
                heapq.heappop(max_heap)

            while max_heap and removed[max_heap[0]] > 0:
                removed[max_heap[0]] -= 1
                heapq.heappop(max_heap)

            current_height = -max_heap[0][0]
            if not result or result[-1][1] != current_height:
                result.append([x, current_height])

        return result

Explanation:

1. Convert buildings to events:
2. A start event uses negative height so taller buildings are processed first at the same x-coordinate.

3. An end event marks where a building stops contributing height.

4. Sweep with a max heap:

5. The heap stores active building heights and their end coordinates.

6. Lazy deletion removes buildings whose right edge has passed the sweep line.

7. Emit key points:

8. Whenever the maximum active height changes, append [x, new_height] to the answer.

Time & Space: O(n log n) time for sorting events and heap operations; O(n) extra space.

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        if not buildings:
            return []

        def merge(left_skyline, right_skyline):
            result = []
            left_index = right_index = 0
            left_height = right_height = 0

            while left_index < len(left_skyline) or right_index < len(right_skyline):
                left_x = left_skyline[left_index][0] if left_index < len(left_skyline) else float("inf")
                right_x = right_skyline[right_index][0] if right_index < len(right_skyline) else float("inf")

                if left_x <= right_x:
                    x, left_height = left_skyline[left_index]
                    left_index += 1
                else:
                    x, right_height = right_skyline[right_index]
                    right_index += 1

                max_height = max(left_height, right_height)
                if not result or result[-1][1] != max_height:
                    result.append([x, max_height])

            return result

        mid = len(buildings) // 2
        if mid == 0:
            left, right, height = buildings[0]
            return [[left, height], [right, 0]]

        left_half = self.getSkyline(buildings[:mid])
        right_half = self.getSkyline(buildings[mid:])
        return merge(left_half, right_half)

Explanation:

1. Divide and conquer:

2. Split the building list in half and recursively compute each half's skyline.

3. Merge two skylines:

4. Walk both skylines in x-order, tracking the current height from each side.

5. Keep only height changes:

6. Append a point only when the combined maximum height changes, producing the final contour.

Time & Space: O(n log n) time via divide-and-conquer; O(n) extra space for recursion stack and merged results.