Understanding One-Pass Algorithms and Greedy Strategies

Jason Yang
27 Nov, 2025
Updated 26 Mar, 2026
Views —

In software engineering—especially when processing large-scale data or building performance-critical systems—one of the most important constraints is this:

How many times will you read the data?

As the size of the input data ( $N$ ) grows, the difference between reading the data twice ( $O(N^2)$ or simply ( $2N$ ) versus reading it just once ( $O(N)$ ) directly affects system latency and overall performance.
Today, let’s explore the elegance of One-Pass algorithms and the greedy mindset that makes them possible.

1. What Is a One-Pass Algorithm?

A One-Pass algorithm is exactly what it sounds like:
You scan a data stream or array exactly once from start to finish and compute the desired result.

Key characteristics:

No Backtracking
Once the index moves past position $i$ , it never goes back to $i-1$ .
Memory Efficiency
You don’t need to load the entire dataset into memory.
You simply process data as it flows in, which often enables $O(1)$ space complexity.

2. How Can You Know the Answer from a Single Pass? (The Power of State)

If you never revisit past data, how can you compute a global optimum?

The secret is maintaining just enough state.

Instead of storing the entire history, you only keep a compact summary—
the information needed to make future decisions.

“Forget the irrelevant details of the past, and carry forward only the essential clues.”

3. The Role of Greedy Algorithms

If One-Pass defines the form, Greedy defines the logic inside it.

A Greedy algorithm always makes the best local choice at the moment, without pausing to consider the entire future. Surprisingly, for many problems, these locally optimal choices accumulate into a globally optimal solution.

Inside a One-Pass loop, the greedy pattern usually looks like this:

Read a new data item.
Evaluate which choice is better right now:

Should we include this item in the current best structure?
Or should we start fresh from here?

Update the state and move on.

4. A Classic Example: Maximum Subarray Sum (Kadane’s Algorithm)

Consider the well-known problem:

Find the contiguous subarray with the maximum sum.

Example input:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]

The brute-force way checks every possible interval → $O(N^2)$ .

But with a greedy insight—
“If the current running sum becomes negative, there is no benefit in carrying it forward.”
— we reduce it to $O(N)$ with a single pass.

public int maxSubArray(int[] nums) {
    int currentSum = 0; // Running sum of the current subarray
    int maxSum = nums[0]; // Best sum seen so far

    for (int num : nums) {
        // Greedy choice:
        // 1. Extend the previous sum with num
        // 2. Or start a new subarray at num
        currentSum = Math.max(num, currentSum + num);

        // Update global maximum
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

이 알고리즘은 배열을 단 한 번 순회( $O(N)$ )하며, 각 단계에서 “가져갈까, 버릴까”라는 탐욕적 선택을 통해 전체 최댓값을 완벽하게 찾아냅니다.

Step-by-Step Execution Log

Input Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Logic: currentSum = Math.max(num, currentSum + num)

Final Result

Final Maximum Subarray Sum: 6
Subarray: [4, -1, 2, 1] (indices 3 to 6)

“Look at step 4: carrying the previous sum (−2) is worse than starting fresh with 4.
This is the greedy moment where the algorithm ‘lets go of the past.’”

5. Why One-Pass Matters

⚡ Performance

A quadratic algorithm $O(N^2)$ may run trillions of operations on a dataset of one million items.
A One-Pass algorithm?
Just one million operations.

🔄 Streaming / Real-Time Processing

You can process data as it arrives—log streams, network packets, sensor input—without waiting for the full dataset.

✨ Simplicity

The entire solution often reduces to a single, clean loop with minimal state.
Beautiful and elegant.

6. Conclusion

The One-Pass + Greedy approach doesn’t work for every problem—
for example, when decisions must be revisited or when global sorting is required.

But whenever a problem can be solved by remembering only the best information so far, this combination becomes one of the most powerful tools in an engineer’s arsenal.

It allows us to solve complex problems in the most simple, efficient, and elegant way possible.

The catch is knowing when a greedy choice is actually optimal rather than just convenient. For how to prove it — the exchange argument — and the interview problems that hinge on it, see Greedy Algorithms: When the Obvious Choice Is Right.

#Algorithm