3 Approaches | Brute Force -> optimize | C++ | Python | BEST explanation
Approach-1: using recursion\n# Intuition\nAs mentioned in the problem, at every second we have 3 choices:\n- Choose an index i in the range [1, n] and decrement
# Approach-1: using recursion\n# Intuition\nAs mentioned in the problem, at every second we have 3 choices:\n- Choose an index i in the range [1, n] and decrement nums[i] by 1.\n- If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s].\n- Do nothing.\n\nThe last choice of no use. So we can neglect it. Based on the first two choice you can easily create recursion tree. \n\nIn the solution, we have a variable ***decreamentCount*** that keeps track of among all the seconds that have been past how many of those have not been used to mark any index in nums array. \nWhilest the variable ***markCount*** is used to keep track of among all the seconds that have been past, how many of those have been used to mark the indices in the nums array.\n\nSuppose you are at the i<sup>th</sup> second, and the values of decreamentCount = **d**, markCount = **m**, changeIndices[i] = **c**, nums[c] = **value**. \nthen, if (d >= value)   => you can mark index c of nums. \nelse you have only one option which is to use the current second to decrease the value of any element in nums. i.e., we can say that d has increased here.\n\nTo not mark the already mark index we are using a **mark** array.\n# Complexity\n- Time complexity: **O(2<sup>M</sup>)**\n\n- Space complexity: **O(N)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` C++ []\nclass Solution {\n    vector<bool> mark;\n    int solve(vector<int>& nums, vector<int>& changeIndices, int s=0, int decrementCount=0, int markCount=0) \n    {\n        int n = nums.size(), m = changeIndices.size();\n        if(markCount == n) return s;\n        if(s >= m) return INT_MAX;\n\n        int ans = solve(nums, changeIndices, s+1, decrementCount+1, markCount);\n        if(!mark[changeIndices[s]] && decrementCount >= nums[changeIndices[s]-1]) \n        {\n            mark[changeIndices[s]] = true;\n            ans = min(ans, solve(nums, changeIndices, s+1, decrementCount - nums[changeIndices[s]-1], markCount+1));\n            mark[changeIndices[s]] = false;\n        }\n\n        return ans;\n    }\npublic:\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {\n        mark.resize(nums.size()+1, false); \n        int ans = solve(nums, changeIndices); \n        return ans == INT_MAX ? -1 : ans; \n    }\n};\n```\n``` Python []\nclass Solution:\n    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:\n        mark = [False] * (len(nums) + 1)\n\n        def solve(nums, changeIndices, s=0, decrementCount=0, markCount=0):\n            n = len(nums)\n            m = len(changeIndices)\n            if markCount == n:\n                return s\n            if s >= m:\n                return float(\'inf\')\n\n            ans = solve(nums, changeIndices, s+1, decrementCount+1, markCount)\n            if not mark[changeIndices[s]] and decrementCount >= nums[changeIndices[s]-1]:\n                mark[changeIndices[s]] = True\n                ans = min(ans, solve(nums, changeIndices, s+1, decrementCount - nums[changeIndices[s]-1], markCount+1))\n                mark[changeIndices[s]] = False\n\n            return ans\n\n        ans = solve(nums, changeIndices)\n        return ans if ans != float(\'inf\') else -1\n\n```\n\n# Approach-2: using two loops\n# Intuition\nIn the second approach, for every i<sup>th</sup> second, We are just checking that is it possible to mark all indices or not. the first second when it is possible will be the answer. And if there does not exists any such second, answer will be -1.\n\nIn order to check that we can mark all indices in i seconds. We use the following algorithm:\n\n# Complexity\n- Time complexity: **O(M<sup>2</sup>)**\n\n- Space complexity: **O(M)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) \n    {\n        int n = nums.size(), m = changeIndices.size();\n\n        for(int i=0; i<m; i++) \n        {\n            int extra = 0;\n            vector<bool> mark(n, false);\n            int markCount = 0;\n            for(int j=i; j>=0; j--) \n            {\n                int indx = changeIndices[j]-1;\n                \n                if(!mark[indx] && j + extra >= nums[indx]) {\n                    mark[indx] = true;\n                    extra -= nums[indx];\n                    markCount ++;\n                } else if(mark[indx]) {\n                    extra = min(extra+1, 0);\n                }\n            }\n\n            return i+1;\n        }\n\n        return -1;\n    }\n};\n``` \n``` Python []\nclass Solution:\n    def earliestSecondToMarkIndices(self, nums, changeIndices):\n        n = len(nums)\n        m = len(changeIndices)\n\n        for i in range(m):\n            extra = 0\n            mark = [False] * n\n            markCount = 0\n            for j in range(i, -1, -1):\n                indx = changeIndices[j] - 1\n                \n                if not mark[indx] and j + extra >= nums[indx]:\n                    mark[indx] = True\n                    extra -= nums[indx]\n                    markCount += 1\n                elif mark[indx]:\n                    extra = min(extra + 1, 0)\n\n            if markCount == n:\n                return i+1\n\n        return -1\n\n```\n\n# Approach-3: using Binary Search\n# Intuition\nThe above code can be written using binary search, as after a particular second **l**, You can always mark all indices of nums. So the earliest Second is the s.\n# Complexity\n- Time complexity: **O(M*log(M))**\n\n- Space complexity: **O(M)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` C++ []\nclass Solution {\n    bool predicateFunction(vector<int>& nums, vector<int>& changeIndices, int i) \n    {\n        int n = nums.size(), m = changeIndices.size(), ans = INT_MAX;\n        int extra = 0;\n        vector<bool> mark(n, false);\n        int markCount = 0;\n        for(int j=i; j>=0; j--) \n        {\n            int indx = changeIndices[j]-1;\n            \n            if(!mark[indx] && j + extra >= nums[indx]) {\n                mark[indx] = true;\n                extra -= nums[indx];\n                markCount ++;\n            } else if(mark[indx]) {\n                extra = min(extra+1, 0);\n            }\n        }\n        return markCount == n;\n    }\npublic:\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) \n    {\n        int m = changeIndices.size(), ans = INT_MAX;\n\n        int l=0, h=m-1, mid;\n        while(h-l > 1) \n        {\n            mid = (l+h)>>1;\n            if(predicateFunction(nums, changeIndices, mid)) {\n                h = mid;\n            } else {\n                l = mid+1;\n            }\n        }\n        if(predicateFunction(nums, changeIndices, l)) return l+1;\n        else if(predicateFunction(nums, changeIndices, h)) return h+1;\n        return -1;\n    }\n};\n``` \n``` Python []\nclass Solution:\n    def earliestSecondToMarkIndices(self, nums, changeIndices):\n        def predicateFunction(nums, changeIndices, i):\n            n = len(nums)\n            extra = 0\n            mark = [False] * n\n            markCount = 0\n            for j in range(i, -1, -1):\n                indx = changeIndices[j] - 1\n                \n                if not mark[indx] and j + extra >= nums[indx]:\n                    mark[indx] = True\n                    extra -= nums[indx]\n                    markCount += 1\n                elif mark[indx]:\n                    extra = min(extra + 1, 0)\n            return markCount == n\n\n        m = len(changeIndices)\n        l, h = 0, m - 1\n        while h - l > 1:\n            mid = (l + h) >> 1\n            if predicateFunction(nums, changeIndices, mid):\n                h = mid\n            else:\n                l = mid + 1\n        if predicateFunction(nums, changeIndices, l):\n            return l + 1\n        elif predicateFunction(nums, changeIndices, h):\n            return h + 1\n        return -1\n\n```\n
['Binary Search', 'Recursion', 'Python', 'C++', 'Python3']