[C++] Brute Force vs. Single Pass Solution Compared and Explained, 100% Time, ~80% Space
Given the constraints, we can easily afford to go for a brute force-ish solution first (a fully legitimate approach during any interview, as long as you keep th
Given the constraints, we can easily afford to go for a brute force-ish solution first (a fully legitimate approach during any interview, as long as you keep the computationt time reasonable - I wouldn\'t do this if either the queue length or the amount of tickets each queuer might buy were in the order of billions!), so we will go for it first.\n\nIn order to solve our problem we will first of all declare an accumulator variable `res`, initially set to `0` and that will store how many turns we have to wait until the `k`th slot has bought all his tickets.\n\nWe will then have an outer loop just to check that - `ts[k]` still having pending tickets to buy and inside it we will run another one, using the pointer `i` to parse `ts` until `ts[k]` is not `0` and in which we will:\n* check if the currently pointed element `ts[i]` still has elements to remove and, in case:\n\t* decrease `ts[i]` by `1`;\n\t* increase `res` by `1`.\n\nOnce done, we can just `return` `res` :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int timeRequiredToBuy(vector<int>& ts, int k) {\n        // support variables\n        int res = 0;\n        // running loops until we get all our tickets\n        while (ts[k]) {\n            // running one loop\n            for (int i = 0, lmt = ts.size(); i < lmt && ts[k]; i++) {\n                // decreasing one slot and increasing res, if the slot still queues\n                if (ts[i]) {\n                    ts[i]--;\n                    res++;\n                }\n            } \n        }\n        return res;\n    }\n};\n```\n\nBut, wait a minute \uD83E\uDD14 ...\n\nDo we really need to decrease all the cells one by one?\n\nWell, probably not, since we might quickly notice that the waiting time each slot to the left of `k` contributes is equal to the minimum between its current value and `ts[k]`, that we will call `target` for convenience; and it\'s almost the same for all the elements to the right of it, being the minimum between its current value and `target - 1` (since we will go and touch them always after having decreased `ts[k]`.\n\nSo, we can put this into code and get much better performance with this version:\n\n```cpp\nclass Solution {\npublic:\n    int timeRequiredToBuy(vector<int>& ts, int k) {\n        // support variables\n        int res = 0, target = ts[k];\n        // parsing the queue\n        for (int i = 0, lmt = ts.size(); i < lmt; i++) {\n            // getting the minimum between the current value and what we need to get\n            res += min(ts[i], target - (i > k));\n        }\n        return res;\n    }\n};\n```\n\nFinal micro-optimised version to avoid one conditional inside the loop (which probably would not even shine in terms of performance compared to allocating variables for a sole `for` loop unless we were to get really big ranges):\n\n```cpp\nclass Solution {\npublic:\n    int timeRequiredToBuy(vector<int>& ts, int k) {\n        // support variables\n        int res = 0, target = ts[k];\n        // parsing the queue up to k, included\n        for (int i = 0; i <= k; i++) {\n            // getting the minimum between the current value and target\n            res += min(ts[i], target);\n        }\n        // parsing the queue up from  k, excluded\n        target--;\n        for (int i = k + 1, lmt = ts.size(); i < lmt; i++) {\n            // getting the minimum between the current value and target\n            res += min(ts[i], target);\n        }\n        return res;\n    }\n};\n```
['Queue', 'C', 'C++']