> For the complete documentation index, see [llms.txt](https://gl01.gitbook.io/gfg-editorials/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://gl01.gitbook.io/gfg-editorials/2023/06-2023-june-15/16-minimum-time.md).

# 16. Minimum Time

The problem can be found at the following link: [Question Link](https://practice.geeksforgeeks.org/problems/95bb244da24edd6214086ff934886ccda6ed9da8/1)

## My Approach

To find the minimum time required to collect fruits from different locations, I have used the following approach:

* First, I create a container called `col` to store the minimum and maximum values for each fruit type.
* Then, I create a vector called `type` to store the different types of fruits we have.
* Using a loop, I iterate through the locations and types. For each fruit type, I update the minimum and maximum values in the `col` container.
* Additionally, I add type 0 to `col` with a value of 0, since we start from 0, and type 1000002 with a value of 0, since we end at 0.
* Next, I iterate through the `col` container and store the different fruit types in the `type` vector.
* I calculate the total number of fruit types we have, `tsz`.
* Using the `dp` array, I implement a tabulation-based dynamic programming approach to optimize the solution. The `dp` array is initialized to store the minimum time for each fruit type and position.
* I iterate through the `type` vector in reverse order and calculate the minimum time required to reach the end from each position.
* Finally, I return the minimum time between the two possible starting positions, `dp[0][0]` and `dp[0][1]`.

## Time and Auxiliary Space Complexity

* **Time Complexity**: `O(N)`, where `N` is the number of locations. The loop to process the locations and types runs in `O(N)` time. The loop to calculate the minimum time using dynamic programming also takes `O(N)` time.
* **Auxiliary Space Complexity**: `O(N)` since we use additional space to store the `col` container and the `type` vector.

## Code (C++)

```cpp
class Solution {
public:
    long long minTime(int n, vector<int>& locations, vector<int>& types) {
        map<int, vector<int>> col;
        vector<int> type;
        
        for (int i = 0; i < n; ++i) {
            if (col.find(types[i]) == col.end()) {
                col[types[i]] = vector<int>(2, locations[i]);
            } else {
                col[types[i]][0] = min(col[types[i]][0], locations[i]);
                col[types[i]][1] = max(col[types[i]][1], locations[i]);
            }
        }

        col[0] = vector<int>(2, 0);
        col[1000002] = vector<int>(2, 0);

        for (auto i : col)
            type.push_back(i.first);

        int tsz = type.size();
        long long dp[tsz + 1][2], lastval, offset;
        dp[tsz][0] = dp[tsz][1] = 0;

        for (int i = tsz - 1; i >= 0; --i) {
            for (int li = 1; li >= 0; --li) {
                auto loc = col[type[i]];

                lastval = col[type[i - 1]][li];
                offset = abs(loc[0] - loc[1]);

                dp[i][li] = offset + min(dp[i + 1][1] + abs(lastval - loc[0]), dp[i + 1][0] + abs(lastval - loc[1]));
            }
        }

        return min(dp[0][0], dp[0][1]);
    }
};
```

## Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our [discussion section](https://github.com/getlost01/gfg-potd/discussions). We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a `⭐ star` to the [getlost01/gfg-potd](https://github.com/getlost01/gfg-potd) repository.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gl01.gitbook.io/gfg-editorials/2023/06-2023-june-15/16-minimum-time.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.