5

I have an array of size n+1 where I wish to store the least cost of purchasing n items(i^th index stores cost of i^th item).

There are m different sellers: each seller provides item L to item R (where L,R>=1 and L,R<=n) for a cost of C each.

To create the least cost array I did the following:

for (int i=1; i<=m; i++) {
    int L = L of i^th seller
    int R = R of i^th seller
    int C = selling price of i^th seller
    for (int j=L; j<=R; j++) {
        if (leastCost[j]==0 || leastCost[j]>C) {
            leastCost[j]=C
    }
}

Constructing this array is O(n*m) and accessing this array is O(1).

For very large values of n and m, is there a better way to construct the least cost array?

Perhaps a different approach of not storing it in an array and something else so that overall time complexity is reduced?

Improve this question
5
  • I don't know where you got O(n^2) from. I get O(n * m). Which is completely different. When you consider how many elements you actually need to access (read from), this should be optimal. Unless there is any additional information you have to start with... Commented Jul 13, 2015 at 4:35
  • I corrected it. Is this really optimal? even for very huge n and m? there's nothing else I can add. Commented Jul 13, 2015 at 4:40
  • @Aron too high? And yes, Aron is right. Your seller table has m sellers, and n prices (average). So this is n*m. You need to go through each element at least once, so (n*m) is optimal (unless you have a quantum computer). Commented Jul 13, 2015 at 4:49
  • 1
    You can use Segment tree, so the time complexity will be O(m log n) for creating the tree, and each query will be O(log n) Commented Jul 13, 2015 at 5:07
  • @Gsquare The best optimization is Using the greedy approach which i have shown in my solution. Commented Jul 13, 2015 at 8:30

3 Answers 3

Reset to default
1

Definitely, we can do better than O(n*m) and also the solution is very simple.

Following is the pseudocode to solve this problem:

Construct a MIN-HEAP of the sellers based on their costs c.

Construct another array x[1...n] with its each element set to 0 initially.

Do the following initializations:
 count=0

while(count < n)
{
 S = EXTRACT_MIN(Heap)
 if(count==0)
 {            
  for(j=S.L to S.R)
  {
   leastCost[j]=S.c
   ++count
   x[j]=S.R
  } 
 }
 else
 {
  for(j=S.L;j<=S.R;++j)
  {
   if(x[j]!=0)
   {
    i=x[j] and continue;
   }
   else 
   {
    leastCost[j]=S.c
    ++count
    x[j]=S.R
   }
  }
 }
}

Explanation

The best optimization that we can achieve in this problem is that we skip all those array indices that are already filled because they already have least cost.

x the helper array: The array x helps us to skip all the array indices which have already been filled because:

x[i] stores the index j such that i to j already have least cost filled in the array so this is the reason for using the conditional statement:

if(x[i]!=0)
{
 i=x[i] and continue;
}

So basically it is helping us to jump straight to the index which is not filled.

MIN-HEAP: It allows us to find the minimum cost c of all the costs present in time O(logm).

Time Complexity

Since we access the array leastCost at most n times therefore for accessing the array : O(n)

Building the heap takes O(m)

In Worst Case all the sellers will contribute to some indices and there will be exact m EXTRACT_MIN(Heap) operations and each takes O(logm) time so time for this is: O(m*logm).

Therefore total Time Complexity=O(n + mlogm + m) = O(n + mlogm).

By the way, If I was using C language, I would use struct for Seller and if Java then a class for Seller.Feel free for any queries.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

@PhamTrung Allow me to clear your doubt. Everytime the inner loop is executed, it increments the variable that controls the outer loop which the variable count. This is the reason for my time complexity.
@PhamTrung Nested loops does not always mean quadratic time. It will only be quadratic if the variables that control the inner and outer loop are independent of each other.
I see, but how do you handle this case? (5 , 5 , 1) , (4, 5, 2) , (3, 5 , 3) .... (1, 5 , 5), (5, 6, 7) .... (5,10, 10) . With n = 10, and each seller is represented as (L, R, C). Clearly, the total time complexity will be 2*(1 + 2 + ... + n/2) = O(n^2) as at iteration, you can only update one item, and you still need to iterate through all range.
Time complexity is 2*(1 + 2 + ... + n/2) * log m = O(n ^2 log m) to be exact for above case.
@PhamTrung Please revise your basics. Big O is a notation used for ASYMPTOTIC ANALYSIS and not what you are calculating in your expressions.
|
1

You can use some form of stack here

1st sort all sellers by L. and by C desc if L equal.

Then starting from 1st seller(with min Li)

If stack is empty put him to the stack. If there are no more sellers with

(Lj == Li)

then cost[Li] = C[i] and Li++ (in stack)

if there is entry with Lj == Li then

  • if Rj < Ri and Cj > Ci skip

  • if Rj < Ri and Cj < Ci add this seller to stack

  • if Rj > Ri and Cj > Ci then pop current seller(i), add this seller(j) and add seller(i)

Improve this answer

1 Comment

I'm not sure how this works. Could you give some working code or a better pseudocode?
0

This problem is a classic problem Range minimum query, which you can use Segment tree to obtain a solution which has time complexity O(m log n) to create the tree and O(log n) for each query.

More details:

We using a tree to represent the minimum price for each item from 1 to n.

For each seller, we update the tree:

tree.update(L, R, C);

Finally, to get the min value for item i, we query the tree:

tree.getMin(i, i);

As both update and getMin has time complexity O(log n), the time complexity for the whole program is O(max(m,n) log n). You don't need to modify anything from the original Segment tree implementation.

Improve this answer

2 Comments

I do not have range queries. How do I construct the segment tree for this particular case?
@Gsquare : each seller provides item L to item R : from L to R, update value C (if possible), these are the range queries. And for each item i, the query is get min of the range (i, i), which has time complexity O(log n).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.