Accumulate Minimum

Accumulate minimum involves finding the running minimum value as elements are processed in a sequence.

For a sequence a1, a2, …, an, the accumulate minimum is:

min = a1 for i from 2 to n: if (ai < min) min = ai

This maintains the smallest value seen so far as elements are processed.

Applications include tracking historical minima in statistics, signal processing, and visualization.

Example in Java:

1
2
3
4
5
6
7
8

int[] a = {10, -5, 0, 20, 15};

int min = a[0];
for(int i=1; i < a.length; i++) {
  if(a[i] < min) min = a[i];
}

// min = -5

Example in C++:

1
2
3
4
5
6
7
8

vector<double> a{1.5, 0.2, 3.4, -0.1, 2.6};

double min = a[0];
for(int i=1; i < a.size(); i++) {
  min = fmin(min, a[i]);
}

// min = -0.1

Example in Python:

1
2
3
4
5
6
7

a = [10, 50, 30, -10, 60]

min_val = a[0]
for i in range(1, len(a)):
  min_val = min(min_val, a[i]) 

# min_val = -10

In summary, accumulate minimum maintains the smallest value seen so far in a sequence. It aids in tracking historical minima.

Accumulate Minimum

Concept

Accumulate Minimum refers to the process of iterating through an array or list to find the minimum element. Unlike other “accumulate” concepts, this process doesn’t involve summing but identifies the smallest element. This is particularly useful in optimization problems, search algorithms, and data analysis to find the least value in a dataset.

Why is it Important?

• Optimization: Useful in identifying the minimum cost or distance.
• Data Analysis: Helps in understanding the lower bounds of datasets.
• Search Algorithms: Integral in algorithms like Dijkstra’s for finding the shortest path.

Formula

The formula to find the Accumulated Minimum ( M ) of an array ( A ) of length ( n ) is:

[ M = \min(A[0], A[1], \ldots, A[n-1]) ]

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Main {
    public static int accumulateMinimum(int[] A) {
        int min = Integer.MAX_VALUE;
        for (int num : A) {
            if (num < min) {
                min = num;
            }
        }
        return min;
    }

    public static void main(String[] args) {
        int[] A = {5, 2, 9, 1, 5, 6};
        int result = accumulateMinimum(A);
        System.out.println("Accumulated Minimum: " + result);
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <algorithm>
using namespace std;

int accumulateMinimum(int A[], int n) {
    int min = INT_MAX;
    for (int i = 0; i < n; ++i) {
        if (A[i] < min) {
            min = A[i];
        }
    }
    return min;
}

int main() {
    int A[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(A)/sizeof(A[0]);
    int result = accumulateMinimum(A, n);
    cout << "Accumulated Minimum: " << result << endl;
    return 0;
}

Python

1
2
3
4
5
6

def accumulate_minimum(A):
    return min(A)

A = [5, 2, 9, 1, 5, 6]
result = accumulate_minimum(A)
print(f"Accumulated Minimum: {result}")

Key Takeaways

• Accumulate Minimum is a simple but effective method for identifying the smallest element in a data set.
• It is a fundamental concept used in a variety of computational problems from optimization to data analysis.
• The operation is computationally efficient and can be executed in O(n) time for an array of length n.