[Java] ✅ ⬆️ | Binary Search | Intuition | Explanation | Easy | Step by Step
Binary Search for Earliest Second: \nThis solution starts by performing a binary search to find the earliest second (s) where it\'s possible to mark all indices
**Binary Search for Earliest Second:** \nThis solution starts by performing a binary search to find the earliest second (s) where it\'s possible to mark all indices in the given arrays.\n**Delay Marking as Much as Possible:** The idea is to delay marking indices until the latest possible moment while ensuring we have enough decrement operations available.\n**Latest Point to Mark an Index**: For each second up to s, we calculate the latest point where we can mark an index based on its last occurrence in the changeIndices array.\n**Store Decrement Operations:** Before the latest point, we store up as many decrement operations as possible. These operations are then used to decrease the value of nums[changeIndices[i]] when marking an index.\n**Check Decrement Operations:** When it\'s time to mark an index, we check whether we have enough decrement operations available to reduce the value of nums[changeIndices[i]]. If we don\'t have enough operations, it means it\'s not possible to mark all indices within s seconds, so we return false.\n**Return Result:** If we successfully mark all indices within s seconds, we return true. Otherwise, we continue with the binary search to find the earliest possible second.\n\n```\nclass Solution {\n    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {\n        int n = nums.length;\n        int[] changeIndicesAdjusted = Arrays.stream(changeIndices).map(index -> index - 1).toArray();\n        int low = 0, high = changeIndices.length - 1;\n        while (low < high) {\n            int mid = (low + high) / 2;\n            if (isPossible(nums, changeIndicesAdjusted, mid)) high = mid;\n            else low = mid + 1;\n        }\n\t\t// Delay Marking as Much as Possible\n        return isPossible(nums, changeIndicesAdjusted, low) ? low + 1 : -1;\n    }\n\n\t// isPossible method is called to check if it\'s possible to mark all indices in s seconds while delaying marking as much as possible.\n    private boolean isPossible(int[] nums, int[] changeIndices, int s) {\n        int n = nums.length;\n        int[] last = new int[n];\n        Arrays.fill(last, -1);\n        for (int i = 0; i <= s; i++) { // Latest Point to Mark an Index\n            last[changeIndices[i]] = i;\n        }\n        int marked = 0, operations = 0;\n        for (int i = 0; i <= s; i++) { // Store Decrement Operations\n            if (i == last[changeIndices[i]]) {\n                if (nums[changeIndices[i]] > operations) return false;\n                operations -= nums[changeIndices[i]];\n                marked++;\n            } else {\n                operations++;\n            }\n        }\n        return marked == n;\n    }\n}\n```\n\n**Time and Space Complexity:** The time complexity of the solution is O((n + m) * log(m)), where n is the length of the nums array and m is the length of the changeIndices array. The space complexity is O(n + m), where n is the length of the nums array and m is the length of the changeIndices array.\n\n![image](https://assets.leetcode.com/users/images/d8e70522-744d-42f0-b3a9-82c4c3d9665c_1708866963.8842509.png)\n\n**Please Upvote**\n
['Binary Tree', 'Java']