3228. Maximum Number of Operations to Move Ones to the End
Approach
For each 1 count zeros to its right; sum = total operations.
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.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Stacks support LIFO (last-in, first-out) operations in O(1). Key patterns: balanced parentheses, next greater element (monotonic stack), function call simulation, and undo/redo. A monotonic stack maintains a strictly increasing or decreasing order to answer range queries efficiently.
// Approach: For each 1 count zeros to its right; sum = total operations.
// Time: O(n) Space: O(1)
public class Solution
{
public int MaxOperations(string s)
{
int ans = 0;
int ones = 0;
for (int i = 0; i < s.Length; ++i)
{
if (s[i] == '1')
++ones;
else if (i == s.Length - 1 || s[i + 1] == '1')
ans += ones;
}
return ans;
}
}