Updating array values within a range
I have an array [1: N] that is initialized to MAXIMUM-VALUE.
I need to maintain a system where each user / bidder sets a range (low, high) of items and their bid for each item in that range. Its value is the same for every element in this range. I have to get the minimum bid for all the different items. After some bets, I need to get the array values.
I wrote the code, but it works in O (n ^ 2).
while(number_of_bids--)
{
cin>>low>>high>>bid_value;
while(low<=high && low<=N)
{
vs[low].cost=min(vs[low].cost,bid_value);
low++;
}
}
Example, if for array [1:10] and rate:
1 2 65
2 4 58
3 7 86
1 9 88
then the value of the array would be:
65, 58, 58, 58, 86, 86, 86, 88, 88, MAXIMUM-VALUE
Please suggest any algorithm that improves the time complexity.
source to share
You can do this using Structure and Index Mapping. Here's the explanation: First, let's build an array / vector of the range and rate structure. IN:
struct node{
int bid;
int left;
int right;
}arr[10005];
Now take the input rates in the array. Then sort the array using a rate comparator. How:
sort(arr,arr+n,comp)
// comparator function could be as :
bool comp(node c,node d)
{
return c.bid<d.bid;
}
Now create an auxiliary array to map the indices and initialize it to -1. Then traverse the structure array and fill the sub array on the right. IN:
int flag=0,count=0;
for(int i=0;i<n;i++){
flag=arr[i].left;
while(flag<n && flag<=arr[i].right){
if(aux_array[flag]==-1){
aux_array[flag] = arr[i].right;
flag++;count++;
}
else {
flag=aux_array[flag]+1;
}
if(count>=n) break;
}
if(count>=n) break;
}
Everything is now ready.
source to share
You can do this in O(N*lg N)
using a balanced binary tree (ordered set in C ++ or Java).
First, prepare an event list of the form: "index: i-th bid start" or "index: k-th bid ends" (the index is either the low or the high part of the range). Sorting the list by index.
Create a tree to store bids sorted by bid value.
Move the array from left to right. Whenever there is an event (or events) for the current cell in the array (events are stored in a separate sorted list), add or remove the bet specified in the event from the tree. Find the minimum bid in the tree for each cell. Store this value in a cell. If the tree is empty, exit the cell with MAXIMUM-VALUE
.
One subtlety here is how to handle duplicate claims. You can only store bet values (no ranges) in the tree, however your data structure must allow duplicates (multiset), and when deleting a bet, be sure to remove only one occurrence of that value. Alternatively, you can store individual bid IDs such as their position in the input, but order the tree by bid values.
Let be the N
size of your array, and M
be the number of bets.
This algorithm gives you the worst case O(N*lg M + M*lg M)
.
The sorting of betting events is obviously O(M*lg M)
.
Then the main loop has O(N)
iterations (array size) and for each cell we do one search to find the smallest bet that is O(lg M)
.
We also have to handle events O(M)
like adding or removing bets, each of which also takes time O(lg M)
.
Assuming that the number of bets M
is equal O(N)
(only under this assumption is your decision O(N^2)
), the whole algorithm O(N*lg N)
.
source to share