javaalgorithmtime-complexityspace-complexity# Find minimum cost to buy products

I am trying to solve this challenge:

You have a list of integers of size

`n`

, that represents costs of products. You have a`discountPrice`

which can be used at most`k`

times, to buy products.You can buy the products using any one of below options:

- Buy left most product and remove it from list
- Buy right most product and remove it from list
- Buy left most and right most products at a price of
`discountPrice`

, and remove both from list.Find the minimum price to purchase all products.

## Example 1:

- Input:
`cost = [1, 2, 3]`

,`discountPrice = 2`

, and`k = 1`

.- Expected output: 3.
Explanation:

- Purchase left most at price 1, then
`cost = [2,3]`

- Purchase left most and right most at discountPrice 3, then
`cost = []`

So minimum cost to buy products is 1+2 = 3

## Example 2:

- Input:
`cost = [9,11,13,15,17]`

,`discountPrice = 6`

,`k = 2`

- Expected output: 21
Explanation:

- Purchase left most at 9, then
`cost = [11,13,15,17]`

- Purchase left most and right most at discountPrice 6, then
`cost =`

[13,15]`- Purchase left most and right most at discountPrice 6, then
`cost =`

[]`So minimum cost to buy products is 9+6+6 = 21

## Example 3:

- Input:
`cost =`

[1,1,1]`,`

discountPrice = 3`,`

k = 1`- Expected: output = 3
## Constraints:

- 1 <=
`n`

<= 10^{5}- 1 <=
`discountPrice`

<= 10^{9}- 1 <=
`k`

<= 10^{5}- 1 <=
`cost[i]`

<= 10^{9}Input can be in any order, but has positive integers

Here is my approach using DP:

```
public static long solve(List<Integer> cost, int discountPrice, int k) {
int n = cost.size();
//dp[i][j] stores the minimum cost to buy products from index i to j without using discount
long[][] dp = new long[n][n];
// Base case: when there's only one product (i == j)
for (int i = 0; i < n; i++) {
dp[i][i] = cost.get(i);
}
// subproblems of increasing lengths
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1; // right index of the subproblem
// Option 1: Buy the leftmost
long option1 = cost.get(i) + dp[i + 1][j];
// Option 2: Buy the rightmost
long option2 = cost.get(j) + dp[i][j - 1];
// Option 3: Apply discountPrice (only if k > 0)
long option3 = Long.MAX_VALUE;
if (k > 0) {
option3 = discountPrice + ((length > 2) ? dp[i + 1][j - 1] : 0);
}
// Store the minimum of the three options
dp[i][j] = Math.min(option1, Math.min(option2, option3));
}
}
return dp[0][n - 1];
}
public static void main(String[] args) {
System.out.println(solve(List.of(1, 2, 3), 2, 1)); // Output: 3
System.out.println(solve(List.of(9, 11, 13, 15, 17), 6, 2)); // Output: 21
System.out.println(solve(List.of(1, 1, 1), 3, 1)); // Output: 3
}
```

The above DP algorithm is taking O(n^2) time and O(n^2) space where n is the size of input list.

I want to reduce both time and space complexity.

Solution

You can actually use your discount on any values you want, as long as the number of discounts used is pair\

For example, consider you have a list of 6 values and you want to apply discounts to the 1st, 3rd, 5th and 6th values. You can always represent it as a list [1, 0, 1, 0, 1, 1], and just when a value on either side is 0, you buy at full price from this side, else you use the discount so that it is used on two 1's.

Knowing this, you can just sort your values, and apply the discount to the next 2 biggest values as long as the total number of discounts is less than 2*k and using the discount will benefit you. The complexity is only **O(n log n)** because of sorting.
Here's how it would work on your second example:

first you choose 17 and 15, the 2 biggest numbers and use the discount on them, which benefits you. Then you use the discount on 13 and 11, which also benefits you. You have no more discounts left.

Of course, you cannot apply the discounts directly to the pairs of values chose by the algorithm, but we have demonstrated that there will be always a way to apply them as long as their total number is pair and less than 2k

- Replacement for the deprecated URL(URL context, String spec) constructor that also works with older Java versions
- How to use WebClient to execute synchronous request?
- SpringBoot 2 the elements were left unbound
- Manually converting a string to an integer in Java
- Java is asking to return a value even when the value is returned in the if-else ladder
- Bounded PriorityBlockingQueue
- HSEARCH000151: Unable to get input stream from object of type byte
- How to get a resources path after jlink-ing?
- Error - trustAnchors parameter must be non-empty
- Build WHERE clause dynamically based on filter in queryDSL
- Best practice to select data using Spring JdbcTemplate
- Doubling each letter in a String
- To find the next work day
- Create advanced search in JPA through user defined dynamic where clause conditions
- Flink task manager does not unload classes
- Implicit casts in Java (passing value type wrappers to methods expecting a regular Integer or Long)
- How do I send an e-mail in Java?
- In Java Failing to invoke method with parameters even though seems to match the getMethod() call
- SQL server hanged suddenly - all DB connections are active but no response - SQL server 2016
- In Java how to synchronize cache read and write operations
- Unable to connect to the remote Cassandra datacenter with the options provided in error
- Creating a hierarchy of Java subclasses
- how to return a list of employee's names with the highest pay rate in java
- "Unsupported class file error" on a Vaadin 14 project
- Does Spring @Transactional attribute work on a private method?
- How to create a BKS (BouncyCastle) format Java Keystore that contains a client certificate chain
- Prevent Kafka Streams Consumer from writing offsets / wait for one stream to consume all records before starting the second stream
- Why does my SQL while(set.next()) skips the first element?
- Combine multiple lists in Java
- How to map from Page<ObjectOne> to Page<ObjectTwo> in Spring Data 2?