Forget Complex Algorithms: The One, One-and-Two, Multiple Pass Solution is Here!

Alright, folks! Let’s talk about algorithm efficiency, but in a way that won’t make your brain melt and not waste time and get straight to the point. But, what's a "pass" anyway? In algorithms, a “pass” simply means how many times the algorithm needs to read or iterate through your input data (like an array, file, or stream) to get the job done. The fewer passes, the faster (and usually more memory-efficient) the algorithm is. Okay, let's go ahead 1. One Pass Algorithms: The “Grab and Go” of Algorithms. The goal: To solve the problem in one pass through the data without storing it in memory (or with minimal use of additional memory). Complexity: Time: O(n) Memory: O(1) or O(k), where k is a constant (for example, for storing multiple variables). When is it applied? When the current state is sufficient (for example, maximum, amount, counter). When it is possible to update the result at each step without referring to the previous data. In streaming processing tasks where data cannot be saved (for example, big data). Well, I have an example of the implementation of the algorithm "Finding the maximum in an array" in java. int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } Nuances: If the array is empty, you need to process it separately (throw an exception or return Integer.MIN_VALUE). It can be adapted to search for the minimum, sum, average value. 1.2 The Boyer-Moore algorithm for majority element search Condition: The element occurs > n/2 times. Idea: We go through the array, we keep the counter of the "candidate". If we see another element, we decrease the counter. If the counter is 0, we change the candidate. class Solution { public int majorityElement(int[] nums) { int candidate = 0; int count = 0; for (int num : nums) { if (count == 0) { candidate = num; } if (num == candidate) { count++; } else { count--; } } return candidate; } } Nuances: If the majority element is guaranteed to be present, no verification is needed. If not, a second pass is required to count the occurrences. 2. One-and-Two-Pass Algorithms The goal is to first collect information in one pass, then use it in the second pass. Complexity: Time: O(n) Memory: O(n) (usually a hash table or array is used). When is it applied? When you need to remember the positions of the elements (for example, Two Sum). When the result depends on the left and right parts of the array (for example, Product Except Self) Two Sum problem class Solution { public int[] twoSum(int[] nums, int target) { Map valueToIndex = new HashMap(); for (int i = 0; i < nums.length; i++) { valueToIndex.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (valueToIndex.containsKey(complement) && valueToIndex.get(complement) != i) { return new int[]{i, valueToIndex.get(complement)}; } } throw new IllegalArgumentException("No two sum solution"); } } 3. Multiple-Pass Algorithms (Multi-Pass algorithms) Purpose: Multiple passes are required (usually >2) due to complex logic. Complexity: Time: O(kn), where k is the number of passes. Memory: O(1) or O(n). When is it applied? In Radix Sort tasks. In linked list tasks (cycle search, palindrome). In tasks with data separation (Dutch National Flag). Dutch National Flag (split into 3 parts) Condition: Divide the array into pivot elements. Algorithm: The low pointer is the end of the < pivot> section. The mid pointer is the current element. The high pointer indicates the beginning of the section > pivot. int low = 0, mid = 0, high = nums.length - 1; while (mid

Apr 21, 2025 - 18:25

Forget Complex Algorithms: The One, One-and-Two, Multiple Pass Solution is Here!

Alright, folks! Let’s talk about algorithm efficiency, but in a way that won’t make your brain melt and not waste time and get straight to the point.

But, what's a "pass" anyway?
In algorithms, a “pass” simply means how many times the algorithm needs to read or iterate through your input data (like an array, file, or stream) to get the job done. The fewer passes, the faster (and usually more memory-efficient) the algorithm is.

Okay, let's go ahead

1. One Pass Algorithms: The “Grab and Go” of Algorithms.

The goal: To solve the problem in one pass through the data without storing it in memory (or with minimal use of additional memory).

Complexity:

Time: O(n)
Memory: O(1) or O(k), where k is a constant (for example, for storing multiple variables).

When is it applied?

When the current state is sufficient (for example, maximum, amount, counter).
When it is possible to update the result at each step without referring to the previous data.
In streaming processing tasks where data cannot be saved (for example, big data).

Well, I have an example of the implementation of the algorithm "Finding the maximum in an array" in java.

int max = arr[0];
for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}

Nuances:

If the array is empty, you need to process it separately (throw an exception or return Integer.MIN_VALUE).
It can be adapted to search for the minimum, sum, average value.

1.2 The Boyer-Moore algorithm for majority element search
Condition:
The element occurs > n/2 times.

Idea:

We go through the array, we keep the counter of the "candidate".
If we see another element, we decrease the counter.
If the counter is 0, we change the candidate.

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }

            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}

Nuances:

If the majority element is guaranteed to be present, no verification is needed.
If not, a second pass is required to count the occurrences.

2. One-and-Two-Pass Algorithms

The goal is to first collect information in one pass, then use **it in the **second pass.

Complexity:

Time: O(n)
Memory: O(n) (usually a hash table or array is used).

When is it applied?

When you need to remember the positions of the elements (for example, Two Sum).

When the result depends on the left and right parts of the array (for example, Product Except Self)

Two Sum problem

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map valueToIndex = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            valueToIndex.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if (valueToIndex.containsKey(complement) && valueToIndex.get(complement) != i) {
                return new int[]{i, valueToIndex.get(complement)};
            }
        }

        throw new IllegalArgumentException("No two sum solution");
    }
}

3. Multiple-Pass Algorithms (Multi-Pass algorithms)

Purpose:

Multiple passes are required (usually >2) due to complex logic. Complexity:
Time: O(kn), where k is the number of passes.

Memory:
O(1) or O(n).

When is it applied?

In Radix Sort tasks.
In linked list tasks (cycle search, palindrome).
In tasks with data separation (Dutch National Flag).

Dutch National Flag (split into 3 parts)
Condition:
Divide the array into pivot elements.

Algorithm:

The low pointer is the end of the < pivot> section.
The mid pointer is the current element.
The high pointer indicates the beginning of the section > pivot.

int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
    if (nums[mid] < pivot) {
        swap(nums, low++, mid++);
    } else if (nums[mid] == pivot) {
        mid++;
    } else {
        swap(nums, mid, high--);
    }
}

Nuances:

If the pivot is not set, you can take the median or the first element.
Used in QuickSort for optimization.

Searching for the beginning of a cycle in a linked list (Floyd's Algorithm)

Formula:

Detect the cycle (turtle and hare).
Find the beginning of the cycle (after the meeting, reset the turtle to the head).

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) break;
}
if (fast == null || fast.next == null) return null;
slow = head;
while (slow != fast) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

Nuances:

If the loop covers the entire list, the beginning of the loop is head.
If the list is empty, you need to return null.

see u later guys!!)