BInary Search. Explained Solution
\n\n# Approach\nThe problem is solved using a binary search approach. The main idea is to find the minimum number of seconds required to mark all indices in the
\n\n# Approach\nThe problem is solved using a binary search approach. The main idea is to find the minimum number of seconds required to mark all indices in the nums array.\n\n**Binary Search:** We perform a binary search over the range of seconds (from 1 to m). For each mid-point in the binary search, we check if it is possible to mark all indices in the nums array within that many seconds.\n\n**Checking Possibility:** To check if it is possible to mark all indices within a given number of seconds, we maintain a lastTimetoOperate array. This array stores the last second at which each index in the nums array can be operated on. If the current second is the last time to operate on an index and the number at that index is greater than the number of operations performed so far, it means we cannot mark all indices within the given seconds. If the number at the index is less than or equal to the operations performed, we mark that index and subtract the number at that index from the total operations performed.\n\n**Updating Operations:** If the current second is not the last time to operate on an index, we increment the operations performed.\n**Final Check:** If all indices are marked within the given seconds, we update our binary search range. If not, we continue our search.\n\n# Complexity\n**Time Complexity:** The time complexity is **O(m log m)**, where m is the length of the changeIndices array. This is because we perform a binary search over m seconds, and for each mid-point, we iterate over the changeIndices array.\n\n**Space Complexity:** The space complexity is **O(n)**, where n is the length of the nums array. This is because we maintain a lastTimetoOperate array of size n.\n\n# Code\n```\ntypedef long long int lli;\n\nclass Solution {\npublic:\n    bool isPossible(vector<int>& nums, vector<int>& changeIndices, lli mid){\n        lli n = nums.size();\n        lli m = changeIndices.size();\n        \n        vector<lli> lastTimetoOperate(n+1, -1);\n        for(lli i=0; i<mid; i++){\n            lastTimetoOperate[changeIndices[i]-1] = i; \n        }\n        \n        lli marked = 0;\n        lli operations = 0;\n        \n        for(lli i=0; i<mid; i++){\n            \n            if(i==lastTimetoOperate[changeIndices[i]-1])\n            {\n                if(nums[changeIndices[i]-1]>operations) return false;\n                operations -= nums[changeIndices[i]-1]; // changed to zero\n                marked++;\n            }\n            else{\n                operations++;\n            }\n        }\n        \n        return marked == n;\n    }\n    \n    \n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {\n        lli n = nums.size();\n        lli m = changeIndices.size();\n        \n        lli low = 0, high = m+1;\n        lli mid;\n        \n        while(low < high){\n            mid = low + (high-low)/2;\n            \n            if(isPossible(nums, changeIndices, mid)){\n                high = mid;\n            }\n            else{\n                low = mid+1;\n            }\n        }\n        \n        if(high == m+1) return -1;\n        \n        return high;\n    }\n};\n```
['C++']