LeetCode 1094: Car Pooling
A clear explanation of determining if a car can transport all passengers using a difference array for passenger count tracking.
Tag
Prefix-Sum
34 notes
LeetCode 1074: Number of Submatrices That Sum to Target
A clear explanation of counting submatrices with a given sum using 2D prefix sums combined with the subarray sum equals k technique.
LeetCode 1031: Maximum Sum of Two Non-Overlapping Subarrays
A clear explanation of finding two non-overlapping subarrays with maximum combined sum using prefix sums and running maximums.
LeetCode 1004: Max Consecutive Ones III
A clear explanation of finding the longest subarray of ones by flipping at most k zeros using a sliding window.
LeetCode 548: Split Array with Equal Sum
A clear explanation of splitting an array into four equal-sum parts using prefix sums and set-based search.
LeetCode 523: Continuous Subarray Sum
A clear explanation of detecting a subarray whose sum is a multiple of k using prefix sums and modular arithmetic.
LeetCode 304: Range Sum Query 2D - Immutable
A clear explanation of Range Sum Query 2D - Immutable using a 2D prefix sum matrix for constant-time rectangle queries.
LeetCode 974: Subarray Sums Divisible by K
A clear explanation of counting subarrays whose sum is divisible by k using prefix sums and remainder frequencies.
LeetCode 848: Shifting Letters
A clear explanation of the Shifting Letters problem using suffix sums and modulo arithmetic.
LeetCode 829: Consecutive Numbers Sum
A clear explanation of the Consecutive Numbers Sum problem using arithmetic series formulas and divisibility analysis.
LeetCode 903: Valid Permutations for DI Sequence
A clear explanation of counting valid DI permutations using dynamic programming and prefix sums.
LeetCode 1000: Minimum Cost to Merge Stones
A clear explanation of merging consecutive stone piles with minimum cost using interval dynamic programming.
LeetCode 862: Shortest Subarray with Sum at Least K
A clear explanation of finding the shortest non-empty subarray with sum at least k using prefix sums and a monotonic deque.
LeetCode 930: Binary Subarrays With Sum
A clear explanation of solving Binary Subarrays With Sum using prefix sums and a frequency map.
LeetCode 825: Friends Of Appropriate Ages
A counting solution for computing how many directed friend requests are allowed by age rules.
LeetCode 813: Largest Sum of Averages
A dynamic programming and prefix sum solution for partitioning an array into adjacent groups with maximum total average.
LeetCode 798: Smallest Rotation with Highest Score
A clear explanation of finding the smallest rotation with maximum score using a difference array.
LeetCode 724: Find Pivot Index
A clear explanation of finding the leftmost pivot index using prefix sums and a running left sum.
LeetCode 644: Maximum Average Subarray II
A binary search solution for finding the maximum average of any contiguous subarray with length at least k.
LeetCode 629: K Inverse Pairs Array
A dynamic programming solution for counting permutations of 1 to n with exactly k inverse pairs.
LeetCode 560: Subarray Sum Equals K
A clear explanation of Subarray Sum Equals K using prefix sums and a hash map to count matching subarrays in linear time.
LeetCode 554: Brick Wall
A clear explanation of Brick Wall using prefix sums and a hash map to find the best vertical cut position.
LeetCode 528: Random Pick with Weight
A clear explanation of weighted random sampling using prefix sums and binary search.
LeetCode 525: Contiguous Array
A clear explanation of finding the longest contiguous subarray with equal numbers of 0 and 1 using prefix sums and a hash map.
LeetCode 517: Super Washing Machines
A clear explanation of balancing dresses across washing machines using greedy prefix flow.
LeetCode 571: Find Median Given Frequency of Numbers
A clear explanation of Find Median Given Frequency of Numbers using cumulative frequency and SQL window functions.
LeetCode 497: Random Point in Non-overlapping Rectangles
A clear explanation of uniformly picking an integer point from non-overlapping rectangles using prefix sums and binary search.
LeetCode 437: Path Sum III
Count downward paths in a binary tree whose values sum to targetSum using DFS and prefix sums.
LeetCode 370: Range Addition
A clear explanation of applying many range updates efficiently using a difference array and prefix sums.
LeetCode 363: Max Sum of Rectangle No Larger Than K
A clear explanation of reducing a 2D rectangle problem to a 1D prefix-sum problem with binary search.
LeetCode 327: Count of Range Sum
A clear explanation of Count of Range Sum using prefix sums and merge sort counting.
LeetCode 325: Maximum Size Subarray Sum Equals k
A clear explanation of Maximum Size Subarray Sum Equals k using prefix sums and earliest-index hashing.
LeetCode 303: Range Sum Query - Immutable
A clear explanation of Range Sum Query - Immutable using prefix sums for constant-time range queries.
Prefix Sum Array
Precompute cumulative sums to answer range sum queries in constant time.