Java | Binary Search Solution | Beats 90.4% Submissions🔥🔥
Intuition: Binary Search\n Describe your first thoughts on how to solve this problem. \n\n# Complexity\n- Time complexity: O(mlogm)\n Add your time complexity h
# Intuition: Binary Search\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Complexity\n- Time complexity: $$O(mlogm)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {\n        int n = nums.length;\n        int m = changeIndices.length;\n\n        for(int i = 0; i < m; i++){\n            changeIndices[i]--;\n        }\n        \n        int s = m + 1;\n        int left = 0, right = m - 1;\n        while(left <= right){\n            int mid = left + ((right - left) >> 1);\n            \n            if(isPossible(mid, nums, changeIndices) == 0){\n                s = mid;\n                right = mid - 1;\n            } else {\n                left = mid + 1;\n            }\n        }\n        return s == m + 1 ? -1 : s + 1;\n    }\n    \n    public int isPossible(int mid, int nums[], int changeIndices[]){\n        int n = nums.length;\n        int m = changeIndices.length;\n\n        int iP[] = new int[n];\n        Arrays.fill(iP, -1);\n\n        int coversAllIndices = 0;\n        for(int i = mid; i >= 0 ; i--){\n            int idx = changeIndices[i];\n            if(iP[idx] == -1){\n                iP[idx] = i;\n                coversAllIndices++;\n            }\n        }\n\n        if(coversAllIndices != n) return -1;\n        // System.out.println(mid + " " + Arrays.toString(iP));\n\n        int power = 0;\n        for(int i = 0; i <= mid; i++){\n            int idx = changeIndices[i];\n            if(iP[idx] == i){\n                if(power >= nums[idx]){\n                    power -= nums[idx];\n                } else {\n                    return -1;\n                }\n            } else {\n                power++;\n            }\n        }\n\n        return 0;\n    }\n}\n```
['Array', 'Binary Search', 'Java']