Think Ahead, Look Back: The Magic of Prefix & Suffix Arrays

Photo by Cole Freeman on Unsplash

I have explored the problem solving technicque prefix and suffix. i’ll explain you one by one with example.

1- PrefixMax:

PrefixMax is a precomputation technique applied on a given integer array. For every index i, it stores the maximum element from the start of the array up to that index. Instead of repeatedly scanning the array to find the maximum, we precompute it once in O(n) time and reuse it in O(1) time for any index lookup.

For a given integer array array, prefixMax[i] represents the largest value among all elements from index 0 to index i. The first element is always the base case, since there are no elements to its left.

let array = [1,4,2,5,3,6,5,1,2,8,10,20,3,6,8,4,10];
let len = array.length;
let preFixMax=Array.from({length:len},()=>0);
// initial value of prefixmax array.
// [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

preFixMax[0]=a[0];

for(let i=1;i<len;i++){
   preFixMax[i]=Math.max(preFixMax[i-1], a[i]); // prefixmax/min
}

// after the complete rotation prefixmax array look like this.
// [1, 4, 4, 5, 5, 6, 6, 6, 6, 8, 10, 20, 20, 20, 20, 20, 20]

for more example and explanation you can visit gfg blog page: https://www.geeksforgeeks.org/dsa/prefix-sum-array-implementation-applications-competitive-programming/

2- SuffixMin: SuffixMin is a precomputation technique applied on a given integer array. For every index i, it stores the minimum element from that index to the end of the array. Instead of repeatedly scanning the array to find the minimum, we precompute it once in O(n) time and reuse it in O(1) time for any index lookup.

For a given integer array array, suffixMin[i] represents the smallest value among all elements from index i to index n-1. The last element is always the base case, since there are no elements to its right.

const suffixMin = Array.from({length:5},()=>1000000/Constraint);
let n=a.length;
// initial value of suffixmin array.
// [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

// base case: last element is min of itself
suffixMin[n-1] = a[n-1];

// fill right to left
for (let i = n-2; i >= 0; i--) {
 suffixMin[i] = Math.min(a[i], suffixMin[i+1]); // sffixmin/max
}
// after the complete rotation suffixmin array look like this.
// [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 10]

If you find more example and explanation you can visit gfg blog: https://www.geeksforgeeks.org/dsa/queries-to-find-the-maximum-and-minimum-array-elements-excluding-elements-from-a-given-range/

I hope you have understand the explanation. if any query let me know in the comment section.