DSAWiser

DSA question set · 152 questions

Prefix Sum DSA Practice Questions

Explore 152 DSA questions in Prefix Sum. Practice with DSAWiser’s code editor and visualizer.

Prefix SumPrefix sumsPrefix countsPrefix / suffix sumsMultidimensional prefix sumsDifference arraysPrefix XORString range queriesDynamic programmingPrefix / suffix preprocessingBinary searchArithmetic sumsPrefix / suffix productsFrequency countingDynamic prefix sumsPoint updatesRange sumsOrdered prefix queriesMonotonic stacksPile prefix sumsHeapsRange updatesPersistent states

What’s in this set

The Prefix Sum collection contains 152 problems: 50 basic, 33 easy, 49 medium, 18 hard, 2 very hard. Choose a question at your current level, or follow the collection’s order below.

Topics in this collection include Prefix Sum, Prefix sums, Prefix counts, Prefix / suffix sums, Multidimensional prefix sums. Each question shows its own topics and difficulty so you can decide where to begin.

Practice with the code visualizer

  1. Open a question in the editor and read the statement, inputs, and expected output. Predict the result for a small example before writing code.
  2. Write a solution and run the examples. If a result differs from your prediction, reduce the input until you can follow each step.
  3. Step through your code in the visualizer. Use a breakpoint to inspect the state at a specific line, then compare it with your reasoning.

Questions in this set

152 total

Open a question in the editor to read its statement and examples. Sign in to practice.

  1. Inclusive Prefix Sum ArrayPrefix Sum · Prefix sumsBasic
  2. Single-Element Array Prefix SumPrefix Sum · Prefix sumsBasic
  3. Two-Element Array Prefix SumPrefix Sum · Prefix sumsBasic
  4. Three-Element Array Prefix SumPrefix Sum · Prefix sumsBasic
  5. Running Sum of Array of Identical ElementsPrefix Sum · Prefix sumsBasic
  6. Prefix Sum Array with a Leading ZeroPrefix Sum · Prefix sumsBasic
  7. Leading-Zero Prefix Array for a Single ElementPrefix Sum · Prefix sumsBasic
  8. Leading-Zero Prefix Array for a Non-Empty ArrayPrefix Sum · Prefix sumsBasic
  9. Add a Leading Zero to a Prefix Sum ArrayPrefix Sum · Prefix sumsBasic
  10. Remove the Leading Zero from a Prefix Sum ArrayPrefix Sum · Prefix sumsBasic
  11. Reconstruct Original Array from 0-Indexed Prefix Sum ArrayPrefix Sum · Prefix sumsBasic
  12. Reconstruct an Array from a Leading-Zero Prefix ArrayPrefix Sum · Prefix sumsBasic
  13. Validate Whether an Array is a Valid Prefix Sum of Non-Negative NumbersPrefix Sum · Prefix sumsBasic
  14. Validate Whether an Array is a Valid Prefix Sum of Strictly Positive NumbersPrefix Sum · Prefix sumsBasic
  15. Check if the Final Element Equals Total Array SumPrefix Sum · Prefix sumsBasic
  16. Single Range Sum from Index 0 to R using 0-Indexed Prefix SumPrefix Sum · Prefix sumsBasic
  17. Single Range Sum [L, R] using 0-Indexed Prefix SumPrefix Sum · Prefix sumsBasic
  18. Single Range Sum Using a Leading-Zero Prefix ArrayPrefix Sum · Prefix sumsBasic
  19. Single Element Range Sum [i, i] using Prefix Sum ArrayPrefix Sum · Prefix sumsBasic
  20. Total Array Sum Query via 0-Indexed Prefix SumPrefix Sum · Prefix sumsBasic
  21. Batch Range Sum Queries on 0-Indexed Prefix Sum ArrayPrefix Sum · Prefix sumsBasic
  22. Range Sum Query with 1-Based Query IndicesPrefix Sum · Prefix sumsBasic
  23. Prefix Count of Elements Greater Than a ThresholdPrefix Sum · Prefix counts · Prefix sumsBasic
  24. Check if Range Sum [L, R] is Positive, Negative, or ZeroPrefix Sum · Prefix sumsBasic
  25. Check if Subarray Sum [L, R] is Even or Odd using Prefix SumsPrefix Sum · Prefix sumsBasic
  26. Prefix Count of Zeros in ArrayPrefix Sum · Prefix counts · Prefix sumsBasic
  27. Prefix Count of Even NumbersPrefix Sum · Prefix counts · Prefix sumsBasic
  28. Prefix Count of Negative NumbersPrefix Sum · Prefix counts · Prefix sumsBasic
  29. Prefix Count of Target Element KPrefix Sum · Prefix counts · Prefix sumsBasic
  30. Range Count of Target Element K via Prefix Count ArrayPrefix Sum · Prefix counts · Prefix sumsBasic
  31. Basic Suffix Sum of 0-Indexed ArrayPrefix Sum · Prefix / suffix sumsBasic
  32. Single-Element Suffix Sum ArrayPrefix Sum · Prefix / suffix sumsBasic
  33. Suffix Sum Array via Reverse TraversalPrefix Sum · Prefix / suffix sumsBasic
  34. Check a Candidate Prefix/Suffix Sum Identity at an IndexPrefix Sum · Prefix / suffix sumsBasic
  35. Query Suffix Range Sum [L, N-1] using Prefix Sum ArrayPrefix Sum · Prefix / suffix sumsBasic
  36. Check if a Given Index i is an Equilibrium IndexPrefix Sum · Prefix / suffix sumsBasic
  37. Check Equal Split Point at Given IndexPrefix Sum · Prefix sumsBasic
  38. Find First Index where Prefix Sum Reaches or Exceeds TargetPrefix Sum · Prefix sumsBasic
  39. Maximum Prefix Sum in an ArrayPrefix Sum · Prefix sumsBasic
  40. Minimum Prefix Sum in an ArrayPrefix Sum · Prefix sumsBasic
  41. 2D Prefix Sum of 1x1 GridPrefix Sum · Multidimensional prefix sumsBasic
  42. 2D Prefix Sum of Single-Row MatrixPrefix Sum · Multidimensional prefix sumsBasic
  43. 2D Prefix Sum of Single-Column MatrixPrefix Sum · Multidimensional prefix sumsBasic
  44. 2D Prefix Sum of 2x2 MatrixPrefix Sum · Multidimensional prefix sumsBasic
  45. Subgrid Sum Using a Padded 2D Prefix MatrixPrefix Sum · Multidimensional prefix sumsBasic
  46. Difference Array of a Given ArrayPrefix Sum · Difference arrays · Prefix sumsBasic
  47. Prefix Sum of Difference ArrayPrefix Sum · Difference arrays · Prefix sumsBasic
  48. Single Range Addition via Difference Array MarkingPrefix Sum · Difference arrays · Prefix sumsBasic
  49. Prefix XOR ArrayPrefix Sum · Prefix XORBasic
  50. Range XOR Query using Prefix XOR ArrayPrefix Sum · Prefix XORBasic
  51. Find the Highest AltitudePrefix Sum · Prefix sumsEasy
  52. Minimum Value to Get Positive Step-by-Step SumPrefix Sum · Prefix sumsEasy
  53. Ant on the BoundaryPrefix Sum · Prefix sumsEasy
  54. Left and Right Sum DifferencesPrefix Sum · Prefix sumsEasy
  55. Find Pivot IndexPrefix Sum · Prefix / suffix sumsEasy
  56. Number of Ways to Split Array into Two Equal Sum SubarraysPrefix Sum · Prefix sumsEasy
  57. Number of Ways to Split Array Where Left Sum Greater Than or Equal Right SumPrefix Sum · Prefix sumsEasy
  58. Maximum Score After Splitting a StringPrefix Sum · Prefix sumsEasy
  59. Count Partitions with Even Sum DifferencePrefix Sum · Prefix counts · Prefix sumsEasy
  60. Batch Range Sum Queries on an Immutable ArrayPrefix Sum · Prefix sumsEasy
  61. Sum of All Odd Length SubarraysPrefix Sum · Prefix sumsEasy
  62. Count Vowel Strings in RangesPrefix Sum · Prefix counts · Prefix sumsEasy
  63. Range Count of Even Numbers in QueriesPrefix Sum · Prefix counts · Prefix sumsEasy
  64. Check if Subarray Sum Between Indices [L, R] Exceeds ThresholdPrefix Sum · Prefix sumsEasy
  65. Find the Distinct Difference ArrayPrefix Sum · Difference arrays · Prefix sumsEasy
  66. Maximum Population YearPrefix Sum · Prefix sumsEasy
  67. Check if Any Point Overlaps in Interval SystemPrefix Sum · Prefix sumsEasy
  68. Points That Intersect With CarsPrefix Sum · Prefix sumsEasy
  69. Check if Subarray with Sum Zero ExistsPrefix Sum · Prefix sumsEasy
  70. Find Subarrays With Equal SumPrefix Sum · Prefix sumsEasy
  71. Count Subarrays with Even SumPrefix Sum · Prefix counts · Prefix sumsEasy
  72. Longest Subsequence With Limited SumPrefix Sum · Prefix sumsEasy
  73. Partition Array Into Three Parts With Equal SumPrefix Sum · Prefix sumsEasy
  74. Defuse the BombPrefix Sum · Prefix sumsEasy
  75. Find the Original Array of Prefix XORPrefix Sum · Prefix XOREasy
  76. Check if Any Subarray XOR Equals ZeroPrefix Sum · Prefix XOREasy
  77. Check if All Rows Have Equal Prefix Sum at Column KPrefix Sum · Prefix sumsEasy
  78. Row-wise vs Column-wise Prefix Sum of a GridPrefix Sum · Multidimensional prefix sumsEasy
  79. Submatrix Sum of Top-Left to (R, C) for Multiple PointsPrefix Sum · Multidimensional prefix sumsEasy
  80. Maximum Sum Subarray of Fixed Size K via Prefix SumPrefix Sum · Prefix sumsEasy
  81. Character Frequency Queries on SubstringsPrefix Sum · Prefix counts · String range queriesEasy
  82. Exclusive Prefix Scan and Total SumPrefix Sum · Prefix sumsEasy
  83. Exact Match and Lower Bound in Positive Prefix SumsPrefix Sum · Prefix sumsEasy
  84. Subarray Sum Equals KPrefix Sum · Prefix sumsMedium
  85. Maximum Size Subarray Sum Equals KPrefix Sum · Prefix sumsMedium
  86. Continuous Subarray SumPrefix Sum · Prefix sumsMedium
  87. Contiguous Array with Maximum LengthPrefix Sum · Prefix sumsMedium
  88. Subarray Sums Divisible by K with Negative Modulo HandlingPrefix Sum · Prefix sumsMedium
  89. Binary Subarrays With SumPrefix Sum · Prefix sumsMedium
  90. Count Number of Nice SubarraysPrefix Sum · Prefix counts · Prefix sumsMedium
  91. Longest Well-Performing IntervalPrefix Sum · Prefix sumsMedium
  92. Make Sum Divisible by PPrefix Sum · Prefix sumsMedium
  93. Find Two Non-overlapping Subarrays Each With Target SumPrefix Sum · Prefix sumsMedium
  94. Maximum Sum Circular SubarrayPrefix Sum · Dynamic programming · Prefix / suffix preprocessingMedium
  95. Maximum Subarray Sum with One DeletionPrefix Sum · Dynamic programming · Prefix / suffix preprocessingMedium
  96. Minimum Operations to Reduce X to ZeroPrefix Sum · Prefix sumsMedium
  97. Plates Between CandlesPrefix Sum · Prefix counts · Prefix sumsMedium
  98. Number of Ways to Select BuildingsPrefix Sum · Prefix sumsMedium
  99. Minimum Size Subarray Sum with Target SPrefix Sum · Prefix sumsMedium
  100. Ways to Split Array Into Three SubarraysPrefix Sum · Prefix sumsMedium
  101. Maximum Value at a Given Index in a Bounded ArrayPrefix Sum · Binary search · Arithmetic sumsMedium
  102. Count Subarrays With Median KPrefix Sum · Prefix counts · Prefix sumsMedium
  103. Max Consecutive Ones III via Prefix Sum of ZerosPrefix Sum · Prefix sumsMedium
  104. Car PoolingPrefix Sum · Difference arrays · Prefix sumsMedium
  105. Describe the PaintingPrefix Sum · Difference arrays · Prefix sumsMedium
  106. Minimum Number of Increments on Subarrays to Form a Target ArrayPrefix Sum · Prefix sumsMedium
  107. Check if Array is Good After Range DecrementsPrefix Sum · Difference arrays · Prefix sumsMedium
  108. Shifting Letters IIPrefix Sum · Prefix sumsMedium
  109. Count Submatrices with All OnesPrefix Sum · Multidimensional prefix sumsMedium
  110. Find the Longest Substring Containing Vowels in Even CountsPrefix Sum · Prefix counts · Prefix sumsMedium
  111. Count Triplets That Can Form Two Arrays of Equal XORPrefix Sum · Prefix XORMedium
  112. Minimum Average DifferencePrefix Sum · Prefix sumsMedium
  113. Product of Array Except SelfPrefix Sum · Prefix / suffix productsMedium
  114. Sum of Absolute Differences in a Sorted ArrayPrefix Sum · Prefix sumsMedium
  115. Shifting Letters using Suffix Sum of ShiftsPrefix Sum · Prefix / suffix sumsMedium
  116. Range Addition on 1D ArrayPrefix Sum · Difference arrays · Prefix sumsMedium
  117. Corporate Flight BookingsPrefix Sum · Difference arrays · Prefix sumsMedium
  118. Find the Student that Will Replace the ChalkPrefix Sum · Prefix sumsMedium
  119. Count Subarrays Where Number of 1s Equals Number of 0sPrefix Sum · Prefix counts · Prefix sumsMedium
  120. Count Subarrays with Sum Equal to Subarray LengthPrefix Sum · Prefix counts · Prefix sumsMedium
  121. XOR Queries of a SubarrayPrefix Sum · Prefix XORMedium
  122. Number of Subarrays with Odd SumPrefix Sum · Prefix sumsMedium
  123. Range Sum Query 2D - ImmutablePrefix Sum · Multidimensional prefix sumsMedium
  124. Matrix Block SumPrefix Sum · Multidimensional prefix sumsMedium
  125. Minimum Penalty for a ShopPrefix Sum · Prefix sumsMedium
  126. Count Beautiful Substrings IPrefix Sum · Prefix counts · Prefix sumsMedium
  127. Range Add Operations on 2D MatrixPrefix Sum · Difference arrays · Prefix sumsMedium
  128. Maximum White Tiles Covered by a CarpetPrefix Sum · Prefix sumsMedium
  129. Count Subarrays with XOR Equal to KPrefix Sum · Prefix XOR · Frequency countingMedium
  130. Dynamic Point Assignment and Range Sum QueriesPrefix Sum · Dynamic prefix sums · Point updates · Range sumsMedium
  131. Interleaved Range Addition and Point QueriesPrefix Sum · Difference arrays · Dynamic prefix sumsMedium
  132. Block Prefix Scan with Carry PropagationPrefix Sum · Prefix sumsMedium
  133. Shortest Subarray with Sum at Least KPrefix Sum · Prefix sums · Ordered prefix queriesHard
  134. Count of Range SumPrefix Sum · Prefix sums · Ordered prefix queriesHard
  135. Maximum Sum of 3 Non-Overlapping SubarraysPrefix Sum · Prefix sumsHard
  136. Split Array Largest SumPrefix Sum · Prefix sumsHard
  137. Max Sum of Rectangle No Larger Than KPrefix Sum · Prefix sumsHard
  138. Kth Smallest Subarray SumPrefix Sum · Prefix sumsHard
  139. Maximum Achievable Frequency After Bounded AdjustmentsPrefix Sum · Prefix sumsHard
  140. Beautiful Towers IIPrefix Sum · Monotonic stacks · Prefix / suffix preprocessingHard
  141. Maximum Value of K Coins From PilesPrefix Sum · Dynamic programming · Pile prefix sumsHard
  142. Minimum Cost to Split an ArrayPrefix Sum · Dynamic programming · Prefix / suffix preprocessingHard
  143. Minimum Difference in Sums After Removal of ElementsPrefix Sum · Heaps · Prefix / suffix preprocessingHard
  144. Count Subarrays With More Ones Than ZerosPrefix Sum · Prefix sums · Ordered prefix queriesHard
  145. Maximum Total Sum of Three Fixed-Length Windows with Negative ValuesPrefix Sum · Prefix sumsHard
  146. Number of Submatrices That Sum to TargetPrefix Sum · Multidimensional prefix sumsHard
  147. Maximum Submatrix Sum in Matrix with Row Prefix SumsPrefix Sum · Multidimensional prefix sumsHard
  148. Interleaved Range Addition and Range Sum QueriesPrefix Sum · Dynamic prefix sums · Range updates · Range sumsHard
  149. Streaming Range Sums with Persistent SnapshotsPrefix Sum · Persistent states · Range sumsHard
  150. Dynamic 3D Point Assignment and Cuboid SumsPrefix Sum · Multidimensional prefix sumsHard
  151. Fully Persistent Dynamic Prefix Sum Structure with Version BranchingPrefix Sum · Persistent states · Range sumsVery hard
  152. Dynamic 2D Range Add and 2D Range Sum Query StructurePrefix Sum · Difference arrays · Prefix sumsVery hard