1769. Minimum Number of Operations to Move All Balls to Each Box
Approach
Two-pass prefix scan (left-to-right then right-to-left) accumulating count and moves.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
A prefix sum array pre-computes cumulative values so any range query is answered in O(1). The classic sum of range [l, r] = prefix[r+1] - prefix[l]. 2D prefix sums extend this to matrix sub-rectangle queries. Combine with a hash map for "subarray sum equals k" problems.
// Approach: Two-pass prefix scan (left-to-right then right-to-left) accumulating count and moves.
// Time: O(n) Space: O(n)
public class Solution
{
public int[] MinOperations(string boxes)
{
int[] ans = new int[boxes.Length];
for (int i = 0, count = 0, moves = 0; i < boxes.Length; ++i)
{
ans[i] += moves;
count += boxes[i] == '1' ? 1 : 0;
moves += count;
}
for (int i = boxes.Length - 1, count = 0, moves = 0; i >= 0; --i)
{
ans[i] += moves;
count += boxes[i] == '1' ? 1 : 0;
moves += count;
}
return ans;
}
}