Here’s the problem statement:
Given an array of integers that represents supermarket-purchase-points accumulated by customers. The points are arranged in the order of period of customer membership and no 2 members have the same points. Find the minimum number of free items that must be given out to the customers such that every customer receives at least an item and no customer gets more items than its immediate neighbour with more points and no customer gets less number of items than its immediate neighbour with lesser points.
For example:
The array: 100 50 25 12 17 60 70 120 55
Output: 25 since number of free items will be: [4 3 2 1 2 3 4 5 1]
Let’s dive into the solution:
It is interesting to note that at every index in the array, the number of items assigned depends on the points of the neighbouring indices and therefore number of items assigned to the neighbouring indices.
Realise that the local depressions in the given array i.e. indices with number of points less than that of its neighbours will get least number of free items and can safely be assigned 1 free item each.
Moving outwards from these depressions in both left and right directions as long as the values are increasing i.e. while(array[j-1]>array[j]) and while(array[j+1]>array[j]) respectively, the number of free items must increment by 1 i.e. freeItems[j -/+ 1] = freeItems[j]+1.
The indices beyond these left and right extensions of a local depression will be parts of extensions of other local depressions and will be assigned free items that way.
Also, note that the mt. tops in the array (i.e. the indices k where array[k]>array[k-1] and array[k]>array[k+1]) lie in 2 extensions: the right extension of a local depression on the the top’s left and the left extension of a local depression on the top’s right and must therefore get number of freeItems such that freeItems[k]>freeItems[k-1] and freeItems[k]>freeItems[k+1].
Therefore, while assigning freeItems during extensions we must set freeItems[j -/+ 1] = max(freeItems[j]+1, freeItems[j -/+ 1]).
Once the number of items is assigned to all indices, we just need to sum up the rewards and return the result.
Time Complexity: We visit each item at least once while finding local depressions.
Then every item is visited once again during extensions => totally 2 times
The mt. tops are visited during 2 extensions so they are totally visited 3 times. Therefore each element is visited at max 2 or 3 times and so time complexity is O(N).
Space complexity: O(N): to store the local depressions and the number of free items at the array indices
Here’s the code for this solution in Java:
public int minfreeItems(int[] points) {
int freeItems[] = new int[points.length];
int localDep[] = new int[points.length];
Arrays.fill(localDep, -1);
int p = 0;
//find lcoal mins
for(int i = 0;i<points.length;i++) {
if((((i-1)<0 || points[i]<points[i-1])) &&
((i+1)>=points.length || points[i]<points[i+1])) {
localDep[p++] = i;
}
}
int k = 0;
while(k<p) {
//left extension
int j = localDep[k]-1;
freeItems[localDep[k]] = 1;
while(j>=0 && points[j]>points[j+1]) {
freeItems[j] = Math.max(freeItems[j+1] + 1, freeItems[j]);
j--;
}
//right extension
j = localDep[k]+1;
while(j<points.length && points[j]>points[j-1]) {
freeItems[j] = Math.max(freeItems[j-1] + 1, freeItems[j]);
j++;
}
k++;
}
int minItems = 0;
for(int n: freeItems) {
minItems += n;
}
return minItems;
}
Another way to implement the above approach is:
Make a pass through the array from left to right and set freeItems only for those indices that should be filled during right extensions of local depressions (i.e. all inidices i where points[i]>points[i-1]) setting it = freeItems[i-1]+1
Make a pass through the array from right to left and set freeItems only for those indices that should be filled during left extension of a local depression (i.e. all inidices i where points[i]>points[i+1]) setting it = max(freeItems[i+1]+1, freeItems[i]). We use max() here for the same reason as in the first implementation.
This way every element’s both neighbours’ points will be considered.
Note that indices i for which neither points[i]>points[i-1] nor points[i]>points[i+1] i.e. the indices that are local depressions need to have freeItems[i] set to 1. We can do this at the beginning before starting the passes through the array.
Time Complexity: O(N) since we visit each element twice during the 2 passes.
Space complexity: O(N) since we store items assigned at each index
Here’s the code for this solution in Java:
public static int minfreeItems(int[] points) {
int freeItems[] = new int[points.length];
Arrays.fill(freeItems, 1);
for(int i = 1;i<points.length;i++) {
if(points[i]>points[i-1])
freeItems[i] = freeItems[i-1] + 1;
}
for(int i = points.length-2;i>=0;i--) {
if(points[i]>points[i+1]) {
freeItems[i] = Math.max(freeItems[i],freeItems[i+1] + 1);
}
}
int sum = 0;
for(int n: freeItems) {
sum += n;
}
return minItems;
}
}
Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding!
The Code Scribbbler 