Of course! The term "single pass" in programming refers to an algorithm that processes a collection of data (like a list or string) by iterating through it only one time.

This is often contrasted with a "two-pass" or "multi-pass" approach, where you might iterate through the data once to do one thing, and then iterate through it again to do another.

The primary advantage of a single-pass algorithm is its efficiency. If you have a list of n items, a single-pass algorithm has a time complexity of O(n), which is optimal for this type of problem. A two-pass algorithm would be O(2n), which simplifies to O(n) but is still roughly twice as slow in practice.

The Classic Example: Finding the Maximum Value

This is the most straightforward example to understand the concept.

The "Two-Pass" (or Naive) Way (Incorrect but illustrative)

Imagine you were told to find the maximum value in a list, but you had a weird rule: you could only look at one number at a time and had to remember it.

• Pass 1: Go through the list and write down every number on a separate piece of paper. (This is like list.copy()).
• Pass 2: Now, go through your new list of papers to find the biggest one.

This is two passes. You've iterated through the original data's values twice.

The "Single-Pass" Way (Correct and Efficient)

This is how you'd actually do it. You only need to look at the list once.

1. Assume the first number is the biggest one you've seen so far. Store it in a variable, let's call it max_value.
2. Go through the list a single time, from the second number to the end.
3. For each number, compare it to max_value.
   • If the current number is greater than max_value, you've found a new "biggest" number! Update max_value to be this new number.
4. After you've looked at every number once, max_value will hold the true maximum.

You've solved the problem by iterating through the list exactly one time.

Python Code for Single-Pass Maximum

def find_max_single_pass(numbers):
    """
    Finds the maximum value in a list of numbers in a single pass.
    """
    # Handle the edge case of an empty list
    if not numbers:
        return None
    # 1. Assume the first number is the max to start
    max_value = numbers[0]
    # 2. Iterate through the rest of the list ONCE
    # We can start from the second element (index 1)
    for number in numbers[1:]:
        # 3. Compare and update if we find a larger number
        if number > max_value:
            max_value = number
    # 4. After the loop, max_value holds the result
    return max_value
# --- Example Usage ---
my_list = [3, 41, 12, 9, 74, 15]
max_num = find_max_single_pass(my_list)
print(f"The list is: {my_list}")
print(f"The maximum value found in a single pass is: {max_num}") 
# Output: The maximum value found in a single pass is: 74

More Advanced Single-Pass Examples

Single-pass algorithms are fundamental in many areas, especially with data streams where you can't go back.

Finding the First Unique Character in a String

Problem: Given a string, find the index of the first character that does not repeat anywhere else in the string. (e.g., in "leetcode", 'l' is the first unique character).

Two-Pass Approach:

1. Pass 1: Count the frequency of every character (e.g., using a dictionary).
2. Pass 2: Iterate through the string again and return the first character whose count in your dictionary is 1.

Single-Pass Approach (with a clever trick): We can simulate a single pass by storing the index of each character as we see it. If we see a character again, we can mark it as "not unique".

def first_uniq_char(s: str) -> int:
    """
    Finds the index of the first non-repeating character in a string
    using a single conceptual pass with a dictionary.
    """
    # Dictionary to store the index of each character.
    # If a character is seen again, its value will be -1.
    char_index_map = {}
    # Pass 1: Store the index of the first occurrence of each character.
    # If we see it again, we invalidate it by setting its index to -1.
    for i, char in enumerate(s):
        if char in char_index_map:
            # We've seen this character before, so it's not unique.
            char_index_map[char] = -1
        else:
            # First time seeing this character, store its index.
            char_index_map[char] = i
    # Now, find the smallest index that is not -1.
    # This is effectively the "second pass" but it's over the
    # (at most 26) unique characters, not the whole string, so it's O(1).
    min_unique_index = float('inf')
    for index in char_index_map.values():
        if index != -1 and index < min_unique_index:
            min_unique_index = index
    return min_unique_index if min_unique_index != float('inf') else -1
# --- Example Usage ---
my_string = "loveleetcode"
index = first_uniq_char(my_string)
print(f"The string is: '{my_string}'")
print(f"The index of the first unique character is: {index}")
# Output: The index of the first unique character is: 0 (for 'l')

Note: While this solution iterates through the string once and then the dictionary of unique characters once, it's often considered a single-pass algorithm because the second part is over a fixed-size set (e.g., 26 for lowercase English letters), making its complexity O(1).

The "Best Time to Buy and Sell Stock" Problem

Problem: You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy and a different day in the future to sell. Return the maximum profit you can achieve from this transaction. If no profit can be achieved, return 0.

Two-Pass Approach:

1. Pass 1: Find the minimum price in the entire list.
2. Pass 2: Find the maximum price that occurs after the minimum price you found.

Single-Pass Approach: We can find the answer in one go by keeping track of the minimum price we've seen so far and calculating the potential profit at each step.

def max_profit_single_pass(prices):
    """
    Calculates the maximum profit from a list of stock prices in a single pass.
    """
    if not prices:
        return 0
    # Initialize the minimum price to the first price
    min_price_so_far = prices[0]
    # Initialize max profit to 0 (no profit is possible)
    max_profit = 0
    # Iterate through the prices starting from the second day
    for price in prices[1:]:
        # 1. Update the minimum price seen so far
        if price < min_price_so_far:
            min_price_so_far = price
        # 2. Otherwise, check if selling at the current price
        #    gives a better profit than we've seen before.
        else:
            current_profit = price - min_price_so_far
            if current_profit > max_profit:
                max_profit = current_profit
    return max_profit
# --- Example Usage ---
stock_prices = [7, 1, 5, 3, 6, 4]
profit = max_profit_single_pass(stock_prices)
print(f"The stock prices are: {stock_prices}")
print(f"The maximum profit is: {profit}")
# Output: The maximum profit is: 5 (buy at 1, sell at 6)

Key Takeaway

When you hear "single pass," think efficiency and state tracking. The core idea is to iterate through your data just once, and during that single iteration, keep track of the necessary information (like a running minimum, a maximum value, or counts) to solve the problem by the end of the loop.