Earliest Second to Mark Indices I Solution in C++/Java/Python/JS
Earliest Second-to-Mark Indices I Problem Description:
You are given two 1-indexed integer arrays, nums and, changeIndices, having lengths n and m, respectively.
Initially, all indices in nums are unmarked. Your task is to mark all indices in nums.
In each second, s, in order from 1 to m (inclusive), you can perform one of the following operations:
Choose an index i in the range [1, n] and decrement nums[i] by 1.
If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s].
Do nothing.
Return an integer denoting the earliest second in the range [1, m] when all indices in nums can be marked by choosing operations optimally, or -1 if it is impossible.
Examples:
Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
Output: 8
Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
- Second 1: Choose index 1 and decrement nums[1] by one. nums becomes [1,2,0].
- Second 2: Choose index 1 and decrement nums[1] by one. nums becomes [0,2,0].
- Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [0,1,0].
- Second 4: Choose index 2 and decrement nums[2] by one. nums becomes [0,0,0].
- Second 5: Mark the index changeIndices[5], which is marking index 3, since nums[3] is equal to 0.
- Second 6: Mark the index changeIndices[6], which is marking index 2, since nums[2] is equal to 0.
- Second 7: Do nothing.
- Second 8: Mark the index changeIndices[8], which is marking index 1, since nums[1] is equal to 0.
Now, all indices have been marked.
It can be shown that it is not possible to mark all indices earlier than the 8th second.
Hence, the answer is 8.
Input: nums = [1,3], changeIndices = [1,1,1,2,1,1,1]
Output: 6
Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
- Second 1: Choose index 2 and decrement nums[2] by one. nums becomes [1,2].
- Second 2: Choose index 2 and decrement nums[2] by one. nums becomes [1,1].
- Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [1,0].
- Second 4: Mark the index changeIndices[4], which is marking index 2, since nums[2] is equal to 0.
- Second 5: Choose index 1 and decrement nums[1] by one. nums becomes [0,0].
- Second 6: Mark the index changeIndices[6], which is marking index 1, since nums[1] is equal to 0.
Now all indices have been marked.
It can be shown that it is not possible to mark all indices earlier than the 6th second.
Hence, the answer is 6.
Input: nums = [0,1], changeIndices = [2,2,2]
Output: -1
Explanation: In this example, it is impossible to mark all indices because index 1 isn't in changeIndices.
Hence, the answer is -1.
Constraints:
1 <= n == nums.length <= 2000
0 <= nums[i] <= 10⁹
1 <= m == changeIndices.length <= 2000
1 <= changeIndices[i] <= n
Brute Force Approach
To approach the problem, we are given two 1-indexed integer arrays: nums and changeIndices, with lengths n and m, respectively. We need to determine the earliest second in the range [1, m] when all indices in nums can be marked by choosing the following operations:
- Choose an index i in the range [1, n] and decrement nums[i] by 1.
- If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s].
- Do nothing.
or return -1 if it is impossible.
What can be the minimum time required to mark all indices?
The minimum time required should be 1, as we can mark an index immediately if it is already 0 and appears in changeIndices in the first second. If an index is 0 at the beginning and is present in changeIndices, it can be marked without decrementing any element.
What would be the maximum time required to mark all indices?
The maximum possible time required is m, in the best-case scenario where all operations are optimally chosen such that the last markable index appears at second m.
If an index takes too long to reach 0, or if it does not appear in changeIndices, then marking all indices might be impossible, leading to an answer of -1.
Thus, our search space for the earliest second ranges from 1 to m. The problem then reduces to finding the earliest second when all indices in nums can be marked.
A naive approach is to iterate through all possible values from 1 to m and check whether it is possible to mark all indices. If so, then it is a valid solution.
Consider nums = [1,3] and changeIndices = [1,1,1,2,1,1,1].
We start by setting the smallest possible time as 1 and the largest possible time as m = 7 (since we have 7 seconds available). We then check whether it is possible to mark all indices in nums at different time limits.
- If the earliest second is 1, we cannot mark all indices because nums[2] = 3 requires multiple decrements before it can be marked.
- If the earliest second is 2, 3, 4, or 5, we still cannot mark all indices optimally in these constraints.
- If the earliest second is 6, 7 or 8, we check if marking is possible within this time.
If the earliest second is 6, we can perform the following operations:
- Second 1: Decrement nums[2], resulting in [1,2].
- Second 2: Decrement nums[2], resulting in [1,1].
- Second 3: Decrement nums[2], resulting in [1,0].
- Second 4: Mark index 2, as nums[2] is 0.
- Second 5: Decrement nums[1], resulting in [0,0].
- Second 6: Mark index 1, as nums[1] is 0.
Now, all indices are marked, making 6 the earliest possible second where we achieve the goal.
For any second less than 6, we cannot mark all indices within the given constraints. Thus, the answer is 6.
We can see that every second from 1 to 6 is necessary to mark all indices. However, if we try to complete this process in 5 or fewer seconds, it is impossible because at least one index will remain unmarked.
Let’s define minTime as the earliest second when all indices in nums can be marked. Any second greater than minTime would also allow marking all indices, but we seek the minimum. On the other hand, any second less than minTime will never satisfy the constraints, as some indices will remain unmarked.
Efficiently Marking Indices Within a Given Time Limit
Alright! Let’s break this down step by step in a way that makes complete sense.
We have an array of numbers nums, and we need to "mark" all indices while following a set of rules.
We are also given changeIndices, which tells us the indices that are available at different moments in time.
The main question is: Can we successfully mark all indices within the given time limit?
Think of it like a task scheduling problem.
- Each index i in nums represents a task that must be completed.
- However, we can only complete an index when it becomes available, which is determined by changeIndices.
- The time limit (let's say m) means we must finish marking all indices before this moment.
So, our goal is to see whether it is possible to complete all tasks within this given time.
Since changeIndices gives us a list of indices that become available at different time steps, the first thing we do is record the last time each index appears in changeIndices.
Why?
- If an index i never appears in changeIndices, it means we can never mark it. In that case, it’s impossible to complete the task.
- If an index appears multiple times, we only care about the last time it appears because that’s the final opportunity we get to complete it.
So, we go through changeIndices and store the latest occurrence of each index.
If any index in nums is missing in this list, we can immediately return false—there’s no way to mark it.
Now that we know when each index becomes available, we need to decide how to process them efficiently.
- We sort all indices based on their last available time.
- Why? Because if an index is available at time t, we should prioritize marking it before we run out of time.
So, we create a list of pairs (last_available_time, index) and sort them in increasing order of time.
Now comes the crucial part—actually marking the indices.
We go through each index one by one in the sorted order.
For each index i, we need to:
- Spend time marking it → This takes nums[i] + 1 time (because its the time required for decrementing nums[i] to 0 and +1 for marking it).
- Ensure we finish before its last available time → If the total time spent so far exceeds its availability, it’s impossible.
- Keep track of total time spent → Every time we mark an index, we update our time counter.
If we successfully process all indices without exceeding their availability, then it’s possible to complete the task within the given time.
If any index in nums is never available in changeIndices, we can immediately return false.
And that’s it! We’ve determined whether marking all indices is possible or not.
Let's understand with an example:
Earliest Second to Mark Indices I Example:
Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
Step-by-Step Execution:
We iterate over possible values of m from 1 to 8 to check when all indices can be marked.
- m = 1 → Can only decrement nums[2], but not enough to mark all indices. (Fail)
- m = 2 → Further decrement nums[2], but still incomplete. (Fail)
- m = 3 → nums[2] becomes 1, but marking all indices still not possible. (Fail)
- m = 4 → nums[2] becomes 0, but marking is incomplete. (Fail)
- m = 5 → Mark nums[3] since it’s 0. Still missing marks for nums[1] and nums[2]. (Fail)
- m = 6 → Mark nums[2] since it’s 0. nums[1] still unmarked. (Fail)
- m = 7 → No additional marks possible, as changeIndices[6] is 0. (Fail)
- m = 8 → Mark nums[1], all indices are marked. (Success)
Final Answer:
The earliest second when all indices are marked is 8.
Steps to Implement the Solution:
Define a Function to Check Feasibility (isPossible)
- Maintain a set to store the last occurrence of each index in changeIndices.
- Use an array (lastInd) to record the last second an index appears in changeIndices.
- If an index never appears in changeIndices, return false (marking is impossible).
- Process indices in the order of their last occurrence and check if marking is possible within m seconds.
- If marking all indices is feasible within m, return true.
Implement the earliestSecondToMarkIndices Function
- Initialize low = 1 and high = m to define the search range.
- Iterate from low to high, checking feasibility using isPossible().
- If a valid time is found, update ans and exit the loop early.
- Return ans, representing the earliest second when marking all indices is possible.
- If marking is impossible within m, return -1.
Earliest Second to Mark Indices I Leetcode Solution
Earliest Second-to-Mark Indices I / Code Implementation
1. Earliest Second-to-Mark Indices I solution in c++ Try on Compiler
class Solution {
// Function to check if it's possible to mark indices at time m
bool isPossible(vector<int> &nums, vector<int> &changeIndices, int m)
{
// Set to store pairs of last index and their respective values
set<pair<int, int>> st;
// Vector to track the last index where each value was changed
vector<int> lastInd(nums.size() + 1, -1);
// Populate the lastInd array with the changeIndices
for (int i = 0; i < m; i++)
{
int val = changeIndices[i];
lastInd[val] = i + 1;
}
// Loop through the nums array and check if each index has a valid change
for (int i = 1; i <= nums.size(); i++)
{
if (lastInd[i] == -1)
// If no change is found for any value, return false
return false;
// Insert the pair of last index and value into the set
st.insert({lastInd[i], i});
}
// Variable to track the total time for marking indices
int time = 0;
for (auto &pos : st)
{
// Time to mark the current index is its value + 1
int t = nums[pos.second - 1] + 1;
// If total time exceeds the last index, it's not possible
if (t + time > pos.first)
return false;
// Add time for the current position
time += t;
}
// If it's possible to mark all indices within time limit, return true
return true;
}
public:
// Function to find the earliest second to mark all indices
int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
// Size of the nums array
int n = nums.size();
// Size of the changeIndices array
int m = changeIndices.size();
// Initialize low and high bounds for the search
int low = 1, high = m;
int ans = -1;
// Loop through possible times from low to high to find the earliest valid time
for (int i = low; i <= high; i++)
{
if (isPossible(nums, changeIndices, i))
{
// Store the earliest valid time
ans = i;
// Exit once the earliest time is found
break;
}
}
// Return the earliest valid time
return ans;
}
};
2. Earliest Second-to-Mark Indices I solution in Java Try on Compiler
import java.util.*;
class Solution {
// Function to check if it's possible to mark indices at time m
public boolean isPossible(int[] nums, int[] changeIndices, int m) {
// Custom comparator for Pair
TreeSet<Pair<Integer, Integer>> st = new TreeSet<>((a, b) -> {
// Compare based on the first element of the pair
return a.getKey() - b.getKey();
});
// Array to track the last index where each value was changed
int[] lastInd = new int[nums.length + 1];
Arrays.fill(lastInd, -1);
// Populate the lastInd array with the changeIndices
for (int i = 0; i < m; i++) {
int val = changeIndices[i];
lastInd[val] = i + 1;
}
// Loop through the nums array and check if each index has a valid change
for (int i = 1; i <= nums.length; i++) {
if (lastInd[i] == -1)
// If no change is found for any value, return false
return false;
// Insert the pair of last index and value into the set
st.add(new Pair<>(lastInd[i], i));
}
// Variable to track the total time for marking indices
int time = 0;
for (Pair<Integer, Integer> pos : st) {
// Time to mark the current index is its value + 1
int t = nums[pos.getValue() - 1] + 1;
// If total time exceeds the last index, it's not possible
if (t + time > pos.getKey())
return false;
// Add time for the current position
time += t;
}
// If it's possible to mark all indices within time limit, return true
return true;
}
// Function to find the earliest second to mark all indices
public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
int n = nums.length; // Size of the nums array
int m = changeIndices.length; // Size of the changeIndices array
// Initialize low and high bounds for the search
int low = 1, high = m;
int ans = -1;
// Loop through possible times from low to high to find the earliest valid time
for (int i = low; i <= high; i++) {
if (isPossible(nums, changeIndices, i)) {
// Store the earliest valid time
ans = i;
// Exit once the earliest time is found
break;
}
}
// Return the earliest valid time
return ans;
}
}
3. Earliest Second-to-Mark Indices I solution in Python Try on Compiler
class Solution:
# Function to check if it's possible to mark indices at time m
def isPossible(self, nums, changeIndices, m):
# List to store pairs of last index and their respective values
st = []
# Array to track the last index where each value was changed
lastInd = [-1] * (len(nums) + 1)
# Populate the lastInd array with the changeIndices
for i in range(m):
val = changeIndices[i]
lastInd[val] = i + 1
# Loop through the nums array and check if each index has a valid change
for i in range(1, len(nums) + 1):
if lastInd[i] == -1:
# If no change is found for any value, return false
return False
# Insert the pair of last index and value into the list
st.append((lastInd[i], i))
# Sort the list based on the last index
st.sort()
# Variable to track the total time for marking indices
time = 0
for pos in st:
# Time to mark the current index is its value + 1
t = nums[pos[1] - 1] + 1
# If total time exceeds the last index, it's not possible
if t + time > pos[0]:
return False
# Add time for the current position
time += t
# If it's possible to mark all indices within time limit, return true
return True
# Function to find the earliest second to mark all indices
def earliestSecondToMarkIndices(self, nums, changeIndices):
# Size of the nums array
n = len(nums)
# Size of the changeIndices array
m = len(changeIndices)
# Initialize low and high bounds for the search
low, high = 1, m
ans = -1
# Loop through possible times from low to high to find the earliest valid time
for i in range(low, high + 1):
if self.isPossible(nums, changeIndices, i):
# Store the earliest valid time
ans = i
# Exit once the earliest time is found
break
# Return the earliest valid time
return ans
4. Earliest Second-to-Mark Indices I solution in Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number[]} changeIndices
* @return {number}
*/
var earliestSecondToMarkIndices = function(nums, changeIndices) {
// Function to check if it's possible to mark indices at time m
const isPossible = (nums, changeIndices, m) => {
// Map to store pairs of last index and their respective values
// Using Map instead of Set since JavaScript doesn't have a built-in ordered set
const map = new Map();
// Array to track the last index where each value was changed
const lastInd = new Array(nums.length + 1).fill(-1);
// Populate the lastInd array with the changeIndices
for (let i = 0; i < m; i++) {
const val = changeIndices[i];
lastInd[val] = i + 1;
}
// Loop through the nums array and check if each index has a valid change
for (let i = 1; i <= nums.length; i++) {
if (lastInd[i] === -1) {
// If no change is found for any value, return false
return false;
}
// Insert the pair of last index and value into the map
map.set(lastInd[i], i);
}
// Sort the map entries by key (last index)
const sortedEntries = Array.from(map.entries()).sort((a, b) => a[0] - b[0]);
// Variable to track the total time for marking indices
let time = 0;
// Check each position in sorted order
for (const [pos, val] of sortedEntries) {
// Time to mark the current index is its value + 1
const t = nums[val - 1] + 1;
// If total time exceeds the last index, it's not possible
if (t + time > pos) {
return false;
}
// Add time for the current position
time += t;
}
// If it's possible to mark all indices within time limit, return true
return true;
};
// Size of the changeIndices array
const m = changeIndices.length;
// Initialize low and high bounds for the search
let low = 1;
let high = m;
let ans = -1;
// Loop through possible times from low to high to find the earliest valid time
for (let i = low; i <= high; i++) {
if (isPossible(nums, changeIndices, i)) {
// Store the earliest valid time
ans = i;
// Exit once the earliest time is found
break;
}
}
// Return the earliest valid time
return ans;
};Complexity Analysis of Earliest Second-to-Mark Indices I (brute force):
Time Complexity: O(m * (m + n log n))
Let's analyze the time complexity of the solution in detail.
- isPossible(nums, changeIndices, m) Complexity
This function checks whether it is possible to mark all indices within m seconds.
- Building the lastInd array:
- We iterate over m elements in changeIndices → O(m)
- Processing nums to populate the set st:
- We iterate over n elements in nums → O(n)
- Processing the set st:
- We insert at most n elements into a set → O(n log n) (since insertion in a set takes O(log n) per element)
- We iterate over n elements to process them → O(n)
Total complexity of isPossible() = O(m + n log n)
2. earliestSecondToMarkIndices(nums, changeIndices) Complexity
- We iterate over m possible values (in worst case) and call isPossible() for each.
- Worst-case scenario: isPossible() is called O(m) times.
- Each call to isPossible() takes O(m + n log n).
Thus, the total complexity is: O(m * (m + n log n))
Space Complexity: O(n+m)
- Auxiliary Space Complexity: O(1)
The only additional space used is a few integer and long long variables (count, ans, i, and function parameters).
Since these variables take O(1) space, the auxiliary space complexity is: O(1). - Total Space Complexity: O(1)
Total space includes input storage: Input arrays nums and changeIndices → O(n + m) space.
Therefore, the total space complexity is O(n+m).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(m * (m + n log n)), where m is the length of the changeIndices array and n is the length of the nums array (with a maximum value of 2000). In the worst-case scenario, the algorithm iterates up to m times, and each iteration calls the isPossible() function, leading to a total complexity of O(m * (m + n log n)).
This time complexity can become inefficient when m is large, particularly when m is close to its upper bound (2000). In such cases, the algorithm may perform a large number of operations (nearly 4 × 10⁶ in the worst case).
This solution may not execute efficiently for all test cases, particularly when m is at its upper limit. While it may work for smaller values of m, it could exceed the time limits for large inputs where m approaches 2000.
In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Since O(m * (m + n log n)) can reach around 4 × 10⁶ operations in the worst case, the solution is close to the limit but may still be acceptable for the given constraints.
However, since the test cases on LeetCode are not extremely strict, the solution is able to pass within the given time limits.
How to optimize it?
In the previous approach, we checked every possible time m (from 1 to m) and verified if it was possible to mark all indices while maintaining the given constraints. This gave us an O(m * (m + n log n)) time complexity, which was too slow.
Now, let’s think about improving this.
The main issue was that we checked every possible value of m from 1 to m, which took a lot of time.
Can we make this part faster?
Yes! Here’s the hint:
We are searching for the earliest possible second when all indices can be marked. We know this valid second lies between 1 (earliest possible time) and m (upper bound on time).
Now that we know the two endpoints, 1 and m, let's make a few observations:
- The data structure is sorted:
The range of possible values for m is naturally sorted from 1 to m. - The search space is monotonic:
- If a certain value for m allows us to mark all indices, then any larger m will also work.
- If a certain value does not allow us to mark all indices, then any smaller m will also fail.
- For the example nums = [1,3], changeIndices = [1,1,1,2,1,1,1], the algorithm will fail for m = 5 because it is impossible to mark all indices within 5 seconds. However, starting from m = 6, it will succeed (F, F, F, ..., T, T, T), and the search will find that the earliest valid second is 6. This illustrates the monotonic property: once a value works, it will continue to work for larger m.
- The middle element helps minimize or maximize the search space:
If we take the middle value of the current range and check if it works (i.e., can we mark all indices within that time?), we can narrow the search space:
If it works, we move to the left half to find an earlier valid time.
If it doesn’t work, we move to the right half to find a later valid time.
If we plot a graph with the possible values of m on the x-axis and whether we can mark all indices on the y-axis, we observe the following pattern:
- Before reaching the earliest valid m, marking all indices is impossible.
- Once m reaches this valid time, it becomes possible.
- The transition follows a step-like pattern, confirming that binary search is a suitable approach.
Thus, m_min represents the earliest possible second when marking all indices becomes feasible. Once this number is found, marking all indices remains feasible for any m ≥ m_min.
With these points in mind, it's clear that instead of linearly checking all possible values from 1 to m, we can take the middle value and continually reduce the search space.
Does this approach remind you of something you've seen before?
Yes, we are applying binary search here. By leveraging the sorted and monotonic properties of the range of m, we efficiently narrow down the search space to find the earliest valid second, instead of checking each value linearly.
Earliest Second-to-Mark Indices I Algorithm
Binary search can help us quickly find the earliest second (m) when all indices in nums can be marked while satisfying all constraints.
- Start by taking the middle value between low (1) and high (m).
- If this mid value satisfies the condition that we can mark all indices within m seconds, we store it as a potential answer and move the search to the left half, looking for an earlier valid second.
- Otherwise, we move the search to the right half to check for a later valid second.
- We continue this process as long as low ≤ high.
Once the condition breaks, the stored answer is returned as the earliest second (m) when all indices in nums can be marked optimally
By using binary search, we can cut the search space in half at each step, which makes the solution much faster and avoids the TLE issue.
Let us understand this with a video.
earliest-second-to-mark-indices-i-optimal-approach-animation
Let's understand with an example:
Earliest Second to Mark Indices I Example:
Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
Binary Search Execution:
- Initial search range: low = 1, high = 8
- Mid = (1+8)/2 = 4 → Check if m = 4 is valid
- Not possible to mark all indices → Move right (low = 5)
- Mid = (5+8)/2 = 6 → Check if m = 6 is valid
- Not possible to mark all indices → Move right (low = 7)
- Mid = (7+8)/2 = 7 → Check if m = 7 is valid
- Not possible to mark all indices → Move right (low = 8)
- Mid = 8 → Check if m = 8 is valid
- Valid → Store answer = 8 and move left (high = 7)
- Exit loop (low > high), return ans = 8
Final Output: 8
How to code it up:
- Checking Feasibility (isPossible Function)
Track Last Occurrence: Maintain an array to store the last time each index is marked up to m seconds.
Validate Each Index: Ensure all indices in nums have at least one valid marking within the given time m.
Process Changes in Order: Store the last occurrence of each index in a set and iterate over them in order.
Check Time Constraint: Ensure that the accumulated marking time does not exceed the allowed time for any index. - Finding the Earliest Possible Time (earliestSecondToMarkIndices Function)
Initialize Binary Search: Set low = 1 and high = m to explore the search space.
Perform Binary Search:
- Calculate mid as the average of low and high.
- Check feasibility using isPossible.
- If possible, store the result and search for a smaller time (high = mid - 1).
- If not possible, look for a larger time (low = mid + 1).
- Return the Earliest Valid Time: Once the search concludes, return the smallest mid that satisfies the constraints.
Earliest Second to Mark Indices I Leetcode Solution
Earliest Second-to-Mark Indices I / Code Implementation
1. Earliest Second-to-Mark Indices I solution in c++ Try on Compiler
class Solution {
// Function to check if it is possible to mark all indices within 'm' seconds
bool isPossible(vector<int> &nums, vector<int> &ci, int m)
{
// Set to store pairs of last occurrence index and respective values
set<pair<int, int>> st;
// Vector to track the last index where each value was changed
vector<int> lastInd(nums.size()+1, -1);
// Populate the lastInd array with the changeIndices up to 'm' seconds
for(int i = 0; i < m; i++)
{
int val = ci[i];
lastInd[val] = i + 1;
}
// Loop through the nums array to check if each index has a valid change
for(int i = 1; i <= nums.size(); i++)
{
// If no change is found for any value, return false
if(lastInd[i] == -1)
return false;
// Insert the pair of last index and value into the set
st.insert({lastInd[i], i});
}
// Variable to track the total time for marking indices
int time = 0;
// Process each stored pair in the set
for(auto &pos: st)
{
// Time required to mark the current index
int t = nums[pos.second - 1] + 1;
// If total time exceeds the last occurrence index, it's not possible
if(t + time > pos.first)
return false;
// Add time for the current operation
time += t;
}
return true;
}
public:
// Function to find the earliest second to mark all indices
int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
// Get sizes of input arrays
int n = nums.size();
int m = changeIndices.size();
// Initialize binary search boundaries
int l = 1, r = m;
int ans = -1;
// Perform binary search to find the minimum valid time
while(l <= r)
{
// Find the middle value
int mid = (l + r) / 2;
// Check if marking indices is possible within 'mid' seconds
if(isPossible(nums, changeIndices, mid))
{
// Store the current answer and move left to find a smaller valid time
ans = mid;
r = mid - 1;
}
else
{
// Increase the lower bound to check for a larger valid time
l = mid + 1;
}
}
return ans;
}
};
2. Earliest Second-to-Mark Indices I solution in Java Try on Compiler
import java.util.*;
class Solution {
// Function to check if it is possible to mark all indices within 'm' seconds
private boolean isPossible(int[] nums, int[] ci, int m) {
// TreeSet to store pairs of last occurrence index and respective values
TreeSet<int[]> st = new TreeSet<>(Comparator.comparingInt(a -> a[0]));
// Array to track the last index where each value was changed
int[] lastInd = new int[nums.length + 1];
Arrays.fill(lastInd, -1);
// Populate the lastInd array with the changeIndices up to 'm' seconds
for (int i = 0; i < m; i++) {
int val = ci[i];
lastInd[val] = i + 1;
}
// Loop through the nums array to check if each index has a valid change
for (int i = 1; i <= nums.length; i++) {
// If no change is found for any value, return false
if (lastInd[i] == -1) {
return false;
}
// Insert the pair of last index and value into the TreeSet
st.add(new int[]{lastInd[i], i});
}
// Variable to track the total time for marking indices
int time = 0;
// Process each stored pair in the set
for (int[] pos : st) {
// Time required to mark the current index
int t = nums[pos[1] - 1] + 1;
// If total time exceeds the last occurrence index, it's not possible
if (t + time > pos[0]) {
return false;
}
// Add time for the current operation
time += t;
}
return true;
}
// Function to find the earliest second to mark all indices
public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
// Get sizes of input arrays
int n = nums.length;
int m = changeIndices.length;
// Initialize binary search boundaries
int l = 1, r = m;
int ans = -1;
// Perform binary search to find the minimum valid time
while (l <= r) {
// Find the middle value
int mid = (l + r) / 2;
// Check if marking indices is possible within 'mid' seconds
if (isPossible(nums, changeIndices, mid)) {
// Store the current answer and move left to find a smaller valid time
ans = mid;
r = mid - 1;
} else {
// Increase the lower bound to check for a larger valid time
l = mid + 1;
}
}
return ans;
}
}
3. Earliest Second-to-Mark Indices I solution in Python Try on Compiler
class Solution:
def isPossible(self, nums, ci, m):
# Set to store pairs of last occurrence index and respective values
st = set()
# Dictionary to track the last index where each value was changed
lastInd = {i: -1 for i in range(1, len(nums) + 1)}
# Populate lastInd array with the changeIndices up to 'm' seconds
for i in range(m):
lastInd[ci[i]] = i + 1
# Loop through the nums array to check if each index has a valid change
for i in range(1, len(nums) + 1):
if lastInd[i] == -1:
return False
st.add((lastInd[i], i))
# Variable to track the total time for marking indices
time = 0
# Process each stored pair in the set
for pos in sorted(st):
t = nums[pos[1] - 1] + 1
if t + time > pos[0]:
return False
time += t
return True
def earliestSecondToMarkIndices(self, nums, changeIndices):
l, r = 1, len(changeIndices)
ans = -1
while l <= r:
mid = (l + r) // 2
if self.isPossible(nums, changeIndices, mid):
ans = mid
r = mid - 1
else:
l = mid + 1
return ans
4. Earliest Second-to-Mark Indices I solution in Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number[]} changeIndices
* @return {number}
*/
var earliestSecondToMarkIndices = function (nums, changeIndices) {
// Function to check if it's possible to mark indices at time m
const isPossible = (nums, changeIndices, m) => {
// Map to store pairs of last index and their respective values
// Using Map instead of Set since JavaScript doesn't have a built-in ordered set
const map = new Map();
// Array to track the last index where each value was changed
const lastInd = new Array(nums.length + 1).fill(-1);
// Populate the lastInd array with the changeIndices
for (let i = 0; i < m; i++) {
const val = changeIndices[i];
lastInd[val] = i + 1;
}
// Loop through the nums array and check if each index has a valid change
for (let i = 1; i <= nums.length; i++) {
if (lastInd[i] === -1) {
// If no change is found for any value, return false
return false;
}
// Insert the pair of last index and value into the map
map.set(lastInd[i], i);
}
// Sort the map entries by key (last index)
const sortedEntries = Array.from(map.entries()).sort((a, b) => a[0] - b[0]);
// Variable to track the total time for marking indices
let time = 0;
// Check each position in sorted order
for (const [pos, val] of sortedEntries) {
// Time to mark the current index is its value + 1
const t = nums[val - 1] + 1;
// If total time exceeds the last index, it's not possible
if (t + time > pos) {
return false;
}
// Add time for the current position
time += t;
}
// If it's possible to mark all indices within time limit, return true
return true;
};
let l = 1, r = changeIndices.length, ans = -1;
while (l <= r) {
let mid = Math.floor((l + r) / 2);
if (isPossible(nums, changeIndices, mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
};Earliest Second-to-Mark Indices I Complexity Analysis(binary search):
Time Complexity : O(log m * (m + n log n))
We analyze the time complexity of the earliestSecondToMarkIndices function and the isPossible helper function.
Binary Search in earliestSecondToMarkIndices
- The function performs binary search on the range [1, m], where m is the size of changeIndices.
- Binary search takes O(log m) iterations.
Helper Function isPossible
- Inside each binary search iteration, we call isPossible(nums, changeIndices, mid).
- Let's analyze the steps inside isPossible:
- Building the lastInd array
- We iterate over m, updating last occurrence indices.
- Time complexity: O(m)
- Checking if all indices have valid changes
- We iterate over n (size of nums) to verify if every index has a change.
- Time complexity: O(n)
- Inserting elements into a set
- We insert up to n elements into a set.
- Since set operations (insert and lookup) take O(log n), this step takes O(n log n) in the worst case.
- Processing the set elements
- We iterate through at most n elements in the set.
- Time complexity: O(n)
Overall Complexity
- Binary search runs in O(log m).
- Each call to isPossible runs in O(m + n log n).
- The total complexity is O(log m * (m + n log n)).
Space Complexity : O(n+m)
- Auxiliary Space Complexity: O(1)
The only additional space used is a few integer and long long variables (count, ans, i, and function parameters).
Since these variables take O(1) space, the auxiliary space complexity is: O(1). - Total Space Complexity: O(n+m)
Total space includes input storage: Input arrays nums and changeIndices → O(n + m) space.
Therefore, the total space complexity is O(n+m).
Similar Problems
Many array problems on Leetcode can be efficiently tackled using Binary Search, especially when searching for specific thresholds or optimizing constraints. A fundamental example is the Ceiling of a Number, where we use Binary Search to find the smallest number in a sorted array that is greater than or equal to a target. Similarly, problems like Binary Search on Answer require applying Binary Search to optimize solutions for partitioning or minimizing/maximizing constraints. The Longest Sequence problem often involves techniques like Binary Search on sorted subsequences to maintain efficiency. Another interesting problem is Find Beautiful Indices in the Given Array I, which may require searching for indices that satisfy specific properties. Reading a Binary Search article on Leetcode can further deepen the understanding of these techniques and their wide range of applications.
Now we have successfully tackled this problem, let's try these similar problems.
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.Return the minimum integer k such that she can eat all the bananas within h hours.
Given an array, arr[] of non-negative integers. The task is to return the maximum of j - i (i<=j) subjected to the constraint of arr[i] <= arr[j].