C++ || Greedy || Array || Binary Search || O(n log n log m) Time || O(n) Space
Intuition & Approach:We need to determine the earliest second at which we can mark all indices in the given array nums while following the changeIndices order.
# Intuition & Approach:
<!-- Describe your first thoughts on how to solve this problem. -->
We need to determine the earliest second at which we can mark all indices in the given array nums while following the changeIndices order. The problem can be broken down into:

1. Understanding the marking process:

    - The array changeIndices tells us at which time a specific index is available to be marked.

    - The array nums specifies the number of operations required to fully mark an index.

    - Each marking process takes 1 + nums[i] operations (1 operation to select and nums[i] operations to mark).

2. Binary Search on Time:

    - Since we need the earliest second where all indices are marked, we can binary search over the possible seconds (0 to m-1).

    - For a given second sec, we check if it is possible to mark all indices using a helper function isValid(sec).

    - If isValid(sec) == true, try earlier seconds (r = mid - 1). Otherwise, try later (l = mid + 1).

3. Checking Validity (isValid function):

    - Keep track of the last occurrence of each index in the changeIndices array until second sec.

    - Ensure all indices appear within this time; otherwise, return false.

    - Process indices in increasing order of their last appearance and check if we can mark them in the available time.

---


# Complexity
**Time complexity:**
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Binary Search on Time: O(log m)

- Checking Validity (isValid function):

    - Creating lastpos array: O(m)

    - Checking all indices: O(n)

    - Using map<int, int> for sorting: O(n log n)

    - Iterating through sorted indices: O(n)

- Total complexity: O(logm)×O(nlogn)=O(nlognlogm)

- For worst-case values of n ≈ 10^5 and m ≈ 10^5, this approach is efficient.


**Space complexity:O(n)**
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
- lastpos array: O(n)

- map<int, int>: O(n) (storing at most n indices)

- Other variables: O(1)

- Total space complexity: O(n)

---

# Code
```cpp []
class Solution {
public:
    int n,m;
    bool func(int sec,vector<int>& nums, vector<int>& changeIndices){
        vector<int> lastpos(n+1,-1);
        for(int i=0;i<=sec;i++){
            int ind=changeIndices[i];
            lastpos[ind]=i+1;
        }
        for(int i=1;i<=n;i++){
            if(lastpos[i]==-1){
                return false;
            }
        }
        map<int,int> mp;
        for(int i=1;i<=n;i++){
            int pos=lastpos[i];
            mp[pos]=i;
        }
        int ans=0;
        for(auto& [pos,ind]:mp){
            int val=1+nums[ind-1];
            if(ans+val>pos){
                return false;
            }
            ans+=val;
        }
        return true;
    }
    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
        n=nums.size();
        m=changeIndices.size();
        int l=0;
        int r=m-1;
        int result=-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(func(mid,nums,changeIndices)){
                result=mid+1;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return result;
    }
};
```
['Array', 'Binary Search', 'C++']