Prefix Sums
Precompute sums of arrays to quickly calculate sum of ranges.
Prefix Sums is a technique where you precompute the cumulative sum of an array. Each element in the resulting array represents the sum of all elements up to that index. Imagine you’re keeping a running total of your daily expenses—this running total lets you quickly determine how much you spent over any given period without summing each day individually. With Prefix Sums, you can answer range sum queries in constant time.
To create a Prefix Sum array, you iterate through your input array just once. Start with the first element, and for every subsequent element, add its value to the sum computed so far. This generates an array where the value at each index represents the total sum from the start up to that index.
For instance, given an array [a0, a1, a2, …, an], you would build the prefix sum array as follows: prefix[0] = a0 and for each i ≥ 1, prefix[i] = prefix[i - 1] + ai.
Once you have the Prefix Sum array, answering range sum queries becomes extremely efficient. To find the sum of elements between indices l and r, simply subtract the prefix sum at l - 1 from the prefix sum at r. If l is 0, the sum is just the prefix sum at r.
This method reduces the time complexity for each query from O(n) to O(1) after the initial O(n) preprocessing.
The idea behind Prefix Sums is simple yet powerful. You begin by iterating over the original array just once to compute a new array where each element is a cumulative total. This precomputation allows you to capture the sum of elements from the start up to any index efficiently.
When a range query is issued, the algorithm quickly determines the sum over that range by subtracting the prefix sum just before the start of the range from the prefix sum at the end. This avoids the need to sum the elements repeatedly for each query. In cases where the query starts at index 0, no subtraction is needed—the prefix sum directly gives the answer.
With only one pass over the data for preprocessing and constant time for each subsequent query, Prefix Sums offer a great balance between time and space complexity. This technique is particularly useful in scenarios where multiple range queries are executed on the same dataset.
1. Initialize Pointers
slow and fast pointers at head. Starting fast at head.next instead causes slow to land one position earlier - useful for finding the left-middle node in even-length linked lists. Both methods work for cycle detection, starting positions only affect where pointers meet.2. Move at Different Speeds
slow one step and fast two steps to find the middle. Adjusting fast to three steps finds the first third, four steps the first quarter, and so on. Always check if fast and fast.next exist to avoid null pointer exceptions and detect the end of the list.3. Check for Intersection
fast reaches null or fast.next is null, slow will be at the middle position.4. Process Result
slow to head and move both pointers one step until they meet again to find the cycle start. For middle finding, slow is already at the middle node.Many algorithmic challenges involve computing the sum of a subarray or range. Recognizing that repeatedly summing portions of an array can be inefficient, Prefix Sums provide an elegant solution. This pattern is not only popular in dynamic programming and cumulative frequency analysis but is also used in conjunction with techniques like difference arrays to solve more advanced problems.
Mastering Prefix Sums can drastically optimize solutions for a wide variety of problems. Here are some key best practices:
Completed | Title | Status | Notes | Solution | |
|---|---|---|---|---|---|
Easy | |||||
Medium |