Skip to content

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 & Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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]
Explaination

  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.

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 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
Explaination

  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.

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 & Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
Explaination:

  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.

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 & Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
Explaination:

  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.

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

Problem Statement

6. Increment Submatrices by One (Leetcode:2536)

Problem Statement

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

Problem Statement

8. Power of Heroes (Leetcode:2681)

Problem Statement

9. Minimum Cost to Make Array Equal (Leetcode:2448)

Problem Statement

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

Code & Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
Explaination:

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

Problem Statement

Code & Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
Explaination:

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

Problem Statement

Code & Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        prev = points[0][1]
        arrows = 1

        for start, end in sorted(points)[1:]:
            if start>prev :
                prev = end
                arrows+=1

            prev = min(end, prev)
        return arrows
Explaination:

4.Car Pooling (Leetcode:1094)

Problem Statement

Code & Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
Explaination:

5. My Calendar II (Leetcode:731)

Problem Statement

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

Problem Statement

7. My Calendar III (Leetcode:732)

Problem Statement

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

Problem Statement