Mastering Single Pass Optimization in C++

Greedy Updates, Time–Space Analysis & Array Traversal Thinking

When I started solving array problems in C++, I noticed a pattern:
most beginner solutions use extra loops or extra space—but interviewers expect single pass optimized logic.

This article explains:

• What single pass optimization really means
• How greedy updates work
• How to analyze time & space complexity
• How to think logically while traversing arrays
• Common array traversal patterns with C++ examples

1️⃣ What is Single Pass Optimization?

Single pass optimization means:

Solving a problem by traversing the array only once (O(n) time),
without unnecessary loops or extra memory.

❌ Bad approach

for(...) { ... }
for(...) { ... }   // multiple passes

✅ Optimized approach

for(...) {
    // update everything in one loop
}

Why interviewers love it

Faster execution

Less memory usage

Shows strong logical thinking

2️⃣ The Core Idea: Greedy Update

A greedy update means:

At every step, make the best decision using current information.

You don’t store all values — you just update answers as you move forward.

3️⃣ Example 1: Find Minimum & Second Minimum (Single Pass)

❌ Naive Approach

Sort array → O(n log n)

Or two loops → O(n²)

✅ Optimized Single Pass Approach

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    vector<int> arr = {1, 33, 6, 10, 17};

    int mini = INT_MAX;
    int secondMini = INT_MAX;

    for (int x : arr) {
        if (x < mini) {
            secondMini = mini;  // greedy shift
            mini = x;
        }
        else if (x < secondMini && x != mini) {
            secondMini = x;
        }
    }

    cout << "Min: " << mini << endl;
    cout << "Second Min: " << secondMini << endl;
}

🔍 Greedy Logic Breakdown

If a new smaller value appears → push old min to second min

Otherwise → check if it fits second min

4️⃣ Time & Space Complexity Analysis

⏱ Time Complexity

One loop → O(n)

💾 Space Complexity

Only variables → O(1)

⚡ This is the best possible solution

5️⃣ How to Think Logically (Interview Mindset)

Before coding, ask yourself:

What values do I need to track?

Can I update them while traversing once?

Do I really need extra arrays or maps?

Mental Rule:

“Can this answer be updated step-by-step?”

If yes → single pass is possible.

6️⃣ Common Array Traversal Patterns

🔹 Pattern 1: Tracking Best / Worst

Used in:

Min / Max

Second largest

Stock buy & sell

best = min(best, current);

🔹 Pattern 2: Running Sum (Prefix Logic)

Used in:

Subarray sum

Kadane’s Algorithm

sum += arr[i];
maxSum = max(maxSum, sum);

🔹 Pattern 3: Count Frequencies

Used in:

Majority element

Duplicates

count[arr[i]]++;

🔹 Pattern 4: Two Variables Greedy Update

Used in:

Min & second min

Max profit

Increasing sequence checks

7️⃣ Example 2: Maximum Element (Simplest Greedy)

int maxVal = INT_MIN;

for (int x : arr) {
    if (x > maxVal) {
        maxVal = x;
    }
}

👉 One variable, one loop, greedy update.

8️⃣ How This Helps in Interviews (Zoho / Product Companies)

Interviewers test:

Can you reduce loops?

Can you optimize without sorting?

Can you explain your logic clearly?

If you say:

“I solved it in one traversal using greedy updates”

💥 That’s a strong signal.

9️⃣ Practice Problems (Must Try)

Try solving these only using one loop:

Find second largest element

Maximum subarray sum

Stock buy & sell profit

Check if array is sorted

Count even & odd numbers

🔚 Final Thoughts

Single pass optimization is not about memorizing tricks.
It’s about thinking while traversing.

🧠 Track only what matters
⚡ Update greedily
♻️ Avoid extra loops

Master this mindset, and array problems become easy and interview-ready.