Earliest Second to Mark Indices I solution and explanation
6 more videos on this problem
3048. Earliest Second to Mark Indices I | Binary Search | Greedy | Weekly Contest 386Aryan Mittal · 38:32 · 4K views
Earliest Second to Mark Indices I | Detailed Intuition | Leetcode Weekly Contest 386 | Leetcode 3048codestorywithMIK · 1:00:10 · 4K views
3048. Earliest Second to Mark Indices I | Weekly Leetcode 386codingMohan · 28:45 · 1K views
3048. Earliest Second to Mark Indices I (Leetcode Medium)Programming Live with Larry · 24:58 · 557 views
Leetcode 3048. Earliest Second to Mark Indices I in Hindi ||Leetcode Weekly Contest 386||GeekstocodeGeekstocode · 25:20 · 216 views
3048-Earliest Second to Mark Indices I || Leetcode weekly contest-386 ||Java Solution #leetcode #dsaMahesh Ahirwar · 20:07 · 138 views
LeetCode 3048 - Earliest Second to Mark Indices I - PythonAlpha-Code · 25:19 · 77 views
The problem
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
iin the range[1, n]and decrementnums[i]by1. - If
nums[changeIndices[s]]is equal to0, mark the indexchangeIndices[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.
Example 1:
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.
Example 2:
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.
Example 3:
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 <= 20000 <= nums[i] <= 1091 <= m == changeIndices.length <= 20001 <= changeIndices[i] <= n
Approach overview
Problem Overview: You are given an array representing required decrements for each index and a sequence describing which index can be marked at each second. The goal is to determine the earliest second when all indices can be marked after performing enough decrement operations beforehand.
Approach 1: Recursive Backtracking (Exponential Time, Exponential Space)
The brute force idea is to simulate every possible sequence of actions. At each second you either decrement a value or mark the index if its value is already zero. Recursively explore all valid choices and track whether every index can eventually be marked within the allowed time. This approach directly models the rules of the problem but the branching factor grows quickly because every second may allow multiple operations. Time complexity becomes exponential in the number of seconds, and recursion stack usage leads to exponential space in the worst case. This version mainly helps you understand the constraints before optimizing.
Approach 2: Greedy Decrement Strategy (O(n + m) Time, O(n) Space)
A better approach treats the process greedily. When you know a specific second is used to mark an index, all required decrements for that index must occur before that moment. Track remaining decrements for each index and process the timeline from left to right. When a mark event appears, check whether enough earlier seconds exist to finish its decrements; otherwise the schedule is impossible. This strategy uses simple counters and iteration over the array of operations. Space complexity stays linear because you only maintain decrement counts and bookkeeping for which indices are completed.
Approach 3: Binary Search on Time + Greedy Check (O((n + m) log m) Time, O(n) Space)
The optimal strategy recognizes that the answer is the earliest feasible second. That makes the problem ideal for binary search over the time range. For a candidate second t, simulate whether it is possible to complete all decrements and marks using only the first t operations. The validation step uses the greedy decrement logic: traverse the operations, schedule marks when allowed, and ensure each index had enough earlier time to reduce its value to zero. If marking all indices is feasible within t, search the left half; otherwise search the right half. This converts the scheduling challenge into repeated feasibility checks and keeps each check linear.
Recommended for interviews: The binary search plus greedy validation is the solution interviewers expect. It shows you recognize the monotonic property of the answer and can combine binary search with a greedy feasibility check. Mentioning the brute-force backtracking approach first demonstrates understanding of the state space, but the optimized search-based solution shows stronger algorithmic thinking.
Approach 1: Greedy Decrement Strategy
This approach focuses on decrementing the numbers in the nums array until they reach zero. Once at zero, we mark the index using the changeIndices only if the condition is satisfied. The task is, therefore, to strategically decrement indices in nums to eventually allow marking. The main idea is to iterate through changeIndices, adjusting and marking off nums as efficiently as possible.
def earliest_second(nums, change_indices):
marked = [False] * len(nums)
remaining = len(nums)
for s in range(len(change_indices)):
index = change_indices[s] - 1
if nums[index] > 0:
nums[index] -= 1
if nums[index] == 0 and not marked[index]:
marked[index] = True
remaining -= 1
if remaining == 0:
return s + 1
return -1
# Example execution
print(earliest_second([2, 2, 0], [2, 2, 2, 2, 3, 2, 2, 1]))import java.util.*;
public class Solution {
public static int earliestSecond(int[] nums, int[] changeIndices) {
boolean[] marked = new boolean[nums.length];
int remaining = nums.length;
for (int s = 0; s < changeIndices.length; s++) {
int index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
remaining--;
}
if (remaining == 0) return s + 1;
}
return -1;
}
public static void main(String[] args) {
int[] nums = {2, 2, 0};
int[] changeIndices = {2, 2, 2, 2, 3, 2, 2, 1};
System.out.println(earliestSecond(nums, changeIndices));
}
}#include <vector>
using namespace std;
int earliestSecond(vector<int>& nums, vector<int>& changeIndices) {
vector<bool> marked(nums.size(), false);
int remaining = nums.size();
for (int s = 0; s < changeIndices.size(); ++s) {
int idx = changeIndices[s] - 1;
if (nums[idx] > 0) {
nums[idx]--;
}
if (nums[idx] == 0 && !marked[idx]) {
marked[idx] = true;
--remaining;
}
if (remaining == 0) return s + 1;
}
return -1;
}
int main() {
vector<int> nums = {2, 2, 0};
vector<int> changeIndices = {2, 2, 2, 2, 3, 2, 2, 1};
return earliestSecond(nums, changeIndices);
}function earliestSecond(nums, changeIndices) {
let marked = new Array(nums.length).fill(false);
let remaining = nums.length;
for (let s = 0; s < changeIndices.length; s++) {
let index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] === 0 && !marked[index]) {
marked[index] = true;
remaining--;
}
if (remaining === 0) return s + 1;
}
return -1;
}
// Example execution
console.log(earliestSecond([2, 2, 0], [2, 2, 2, 2, 3, 2, 2, 1]));#include <stdio.h>
#include <stdbool.h>
int earliestSecond(int* nums, int numsSize, int* changeIndices, int changeIndicesSize) {
int marked[numsSize];
for (int i = 0; i < numsSize; ++i) marked[i] = 0;
int remaining = numsSize;
for (int s = 0; s < changeIndicesSize; ++s) {
int index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = 1;
remaining--;
}
if (remaining == 0) return s + 1;
}
return -1;
}
int main() {
int nums[] = {2, 2, 0};
int changeIndices[] = {2, 2, 2, 2, 3, 2, 2, 1};
int n = sizeof(nums) / sizeof(nums[0]);
int m = sizeof(changeIndices) / sizeof(changeIndices[0]);
printf("%d\n", earliestSecond(nums, n, changeIndices, m));
return 0;
}using System;
public class Solution {
public static int EarliestSecond(int[] nums, int[] changeIndices) {
bool[] marked = new bool[nums.Length];
int remaining = nums.Length;
for (int s = 0; s < changeIndices.Length; s++) {
int index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
remaining--;
}
if (remaining == 0) return s + 1;
}
return -1;
}
public static void Main() {
int[] nums = {2, 2, 0};
int[] changeIndices = {2, 2, 2, 2, 3, 2, 2, 1};
Console.WriteLine(EarliestSecond(nums, changeIndices));
}
}The Python implementation mirrors the logical flow of the earlier solutions, using list operations for decrement and marking to determine the earliest second when all indices can be marked.
Time Complexity: O(m), Space Complexity: O(n).
Approach 2: Recursive Backtracking
This approach views the problem as a combination of dynamic and recursive decision-making. At each possible second, decide whether to decrement a number in nums, and carry out a backtracking recursive call exploring decision paths. If a state of zero unmarked nums is reached, return. This method, while slower, explores all potential efficient ways to mark the indices.
def backtrack(nums, change_indices, idx, marked, remaining):
if remaining == 0:
return True
if idx == len(change_indices):
return False
index = change_indices[idx] - 1
if nums[index] > 0:
nums[index] -= 1
if backtrack(nums, change_indices, idx + 1, marked, remaining):
return True
nums[index] += 1
if nums[index] == 0 and not marked[index]:
marked[index] = True
if backtrack(nums, change_indices, idx + 1, marked, remaining - 1):
return True
marked[index] = False
return backtrack(nums, change_indices, idx + 1, marked, remaining)
def earliest_second(nums, change_indices):
marked = [False] * len(nums)
return len(change_indices) if backtrack(nums, change_indices, 0, marked, len(nums)) else -1
# Example execution
print(earliest_second([2, 2, 0], [2, 2, 2, 2, 3, 2, 2, 1]))public class Solution {
public static boolean backtrack(int[] nums, int[] changeIndices, int idx, boolean[] marked, int remaining) {
if (remaining == 0) return true;
if (idx == changeIndices.length) return false;
int index = changeIndices[idx] - 1;
if (nums[index] > 0) {
nums[index]--;
if (backtrack(nums, changeIndices, idx + 1, marked, remaining)) return true;
nums[index]++;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
if (backtrack(nums, changeIndices, idx + 1, marked, remaining - 1)) return true;
marked[index] = false;
}
return backtrack(nums, changeIndices, idx + 1, marked, remaining);
}
public static int earliestSecond(int[] nums, int[] changeIndices) {
boolean[] marked = new boolean[nums.length];
int result = backtrack(nums, changeIndices, 0, marked, nums.length) ? changeIndices.length : -1;
return result;
}
public static void main(String[] args) {
int[] nums = {2, 2, 0};
int[] changeIndices = {2, 2, 2, 2, 3, 2, 2, 1};
System.out.println(earliestSecond(nums, changeIndices));
}
}#include <vector>
using namespace std;
bool backtrack(vector<int>& nums, vector<int>& changeIndices, int idx, vector<bool>& marked, int& remaining) {
if (remaining == 0) return true;
if (idx == changeIndices.size()) return false;
int index = changeIndices[idx] - 1;
if (nums[index] > 0) {
nums[index]--;
if (backtrack(nums, changeIndices, idx + 1, marked, remaining))
return true;
nums[index]++;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
if (backtrack(nums, changeIndices, idx + 1, marked, remaining--))
return true;
marked[index] = false;
}
return backtrack(nums, changeIndices, idx + 1, marked, remaining);
}
int earliestSecond(vector<int>& nums, vector<int>& changeIndices) {
vector<bool> marked(nums.size(), false);
int remaining = nums.size();
return backtrack(nums, changeIndices, 0, marked, remaining) ? changeIndices.size() : -1;
}
int main() {
vector<int> nums = {2, 2, 0};
vector<int> changeIndices = {2, 2, 2, 2, 3, 2, 2, 1};
return earliestSecond(nums, changeIndices);
}function backtrack(nums, changeIndices, idx, marked, remaining) {
if (remaining === 0) return true;
if (idx === changeIndices.length) return false;
let index = changeIndices[idx] - 1;
if (nums[index] > 0) {
nums[index]--;
if (backtrack(nums, changeIndices, idx + 1, marked, remaining)) return true;
nums[index]++;
}
if (nums[index] === 0 && !marked[index]) {
marked[index] = true;
if (backtrack(nums, changeIndices, idx + 1, marked, remaining - 1)) return true;
marked[index] = false;
}
return backtrack(nums, changeIndices, idx + 1, marked, remaining);
}
function earliestSecond(nums, changeIndices) {
let marked = new Array(nums.length).fill(false);
return backtrack(nums, changeIndices, 0, marked, nums.length) ? changeIndices.length : -1;
}
// Example execution
console.log(earliestSecond([2, 2, 0], [2, 2, 2, 2, 3, 2, 2, 1]));#include <stdio.h>
#include <stdbool.h>
bool backtrack(int* nums, int* changeIndices, int idx, int numsSize, int changeIndicesSize, bool* marked, int remaining) {
if (remaining == 0) return true;
if (idx == changeIndicesSize) return false;
int index = changeIndices[idx] - 1;
if (nums[index] > 0) {
nums[index]--;
if (backtrack(nums, changeIndices, idx+1, numsSize, changeIndicesSize, marked, remaining))
return true;
nums[index]++;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
if (backtrack(nums, changeIndices, idx+1, numsSize, changeIndicesSize, marked, remaining-1))
return true;
marked[index] = false;
}
return backtrack(nums, changeIndices, idx+1, numsSize, changeIndicesSize, marked, remaining);
}
int earliestSecond(int* nums, int numsSize, int* changeIndices, int changeIndicesSize) {
bool marked[numsSize];
for (int i = 0; i < numsSize; ++i) marked[i] = false;
return backtrack(nums, changeIndices, 0, numsSize, changeIndicesSize, marked, numsSize) ? changeIndicesSize : -1;
}
int main() {
int nums[] = {2, 2, 0};
int changeIndices[] = {2, 2, 2, 2, 3, 2, 2, 1};
int n = sizeof(nums) / sizeof(nums[0]);
int m = sizeof(changeIndices) / sizeof(changeIndices[0]);
printf("%d\n", earliestSecond(nums, n, changeIndices, m));
return 0;
}using System;
public class Solution {
public static bool Backtrack(int[] nums, int[] changeIndices, int idx, bool[] marked, int remaining) {
if (remaining == 0) return true;
if (idx == changeIndices.Length) return false;
int index = changeIndices[idx] - 1;
if (nums[index] > 0) {
nums[index]--;
if (Backtrack(nums, changeIndices, idx + 1, marked, remaining))
return true;
nums[index]++;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
if (Backtrack(nums, changeIndices, idx + 1, marked, remaining - 1))
return true;
marked[index] = false;
}
return Backtrack(nums, changeIndices, idx + 1, marked, remaining);
}
public static int EarliestSecond(int[] nums, int[] changeIndices) {
bool[] marked = new bool[nums.Length];
return Backtrack(nums, changeIndices, 0, marked, nums.Length) ? changeIndices.Length : -1;
}
public static void Main(string[] args) {
int[] nums = {2, 2, 0};
int[] changeIndices = {2, 2, 2, 2, 3, 2, 2, 1};
Console.WriteLine(EarliestSecond(nums, changeIndices));
}
}The Python recursive solution makes use of the backtrack function to evaluate possible decrements and markings, providing a depth-first search approach to solve the problem space through exhaustive exploration.
Time Complexity: Exponential; Space Complexity: O(m) owing to call stack depth.
Approach 3: Greedy Decrement and Marking
This approach involves greedily decrementing the specified elements in nums to zero at each second if possible, and marking indices when they reach zero based on changeIndices array. The goal is to mark all indices as early as possible by using the operations optimally within each second.
def earliest_seconds(nums, change_indices):
marked = [False] * len(nums)
marked_count = 0
for s, index in enumerate(change_indices):
index -= 1 # 1-based to 0-based index
if nums[index] > 0:
nums[index] -= 1
if nums[index] == 0 and not marked[index]:
marked[index] = True
marked_count += 1
if marked_count == len(nums):
return s + 1
return -1
# Example usage
print(earliest_seconds([1, 3], [1, 1, 1, 2, 1, 1, 1]))public class Solution {
public int earliestSeconds(int[] nums, int[] changeIndices) {
boolean[] marked = new boolean[nums.length];
int markedCount = 0;
for (int s = 0; s < changeIndices.length; s++) {
int index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
markedCount++;
}
if (markedCount == nums.length) return s + 1;
}
return -1;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 3};
int[] changeIndices = {1, 1, 1, 2, 1, 1, 1};
System.out.println(sol.earliestSeconds(nums, changeIndices));
}
}#include <vector>
#include <iostream>
using namespace std;
int earliestSeconds(vector<int>& nums, vector<int>& changeIndices) {
int n = nums.size();
vector<bool> marked(n, false);
int markedCount = 0;
for (int s = 0; s < changeIndices.size(); s++) {
int index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
markedCount++;
}
if (markedCount == n) return s + 1;
}
return -1;
}
// Example usage
int main() {
vector<int> nums = {1, 3};
vector<int> changeIndices = {1, 1, 1, 2, 1, 1, 1};
cout << earliestSeconds(nums, changeIndices) << endl;
return 0;
}function earliestSeconds(nums, changeIndices) {
const marked = new Array(nums.length).fill(false);
let markedCount = 0;
for (let s = 0; s < changeIndices.length; s++) {
const index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] === 0 && !marked[index]) {
marked[index] = true;
markedCount++;
}
if (markedCount === nums.length) {
return s + 1;
}
}
return -1;
}
// Example usage
console.log(earliestSeconds([1, 3], [1, 1, 1, 2, 1, 1, 1]));#include <stdio.h>
#include <stdbool.h>
int earliestSeconds(int* nums, int n, int* changeIndices, int m) {
bool marked[n];
for (int i = 0; i < n; i++) marked[i] = false;
int markedCount = 0;
for (int s = 0; s < m; s++) {
int index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
markedCount++;
}
if (markedCount == n) return s + 1;
}
return -1;
}
// Example usage
int main() {
int nums[] = {1, 3};
int changeIndices[] = {1, 1, 1, 2, 1, 1, 1};
printf("%d\n", earliestSeconds(nums, 2, changeIndices, 7));
return 0;
}using System;
public class Solution {
public int EarliestSeconds(int[] nums, int[] changeIndices) {
bool[] marked = new bool[nums.Length];
int markedCount = 0;
for (int s = 0; s < changeIndices.Length; s++) {
int index = changeIndices[s] - 1;
if (nums[index] > 0) {
nums[index]--;
}
if (nums[index] == 0 && !marked[index]) {
marked[index] = true;
markedCount++;
}
if (markedCount == nums.Length) return s + 1;
}
return -1;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 3};
int[] changeIndices = {1, 1, 1, 2, 1, 1, 1};
Console.WriteLine(sol.EarliestSeconds(nums, changeIndices));
}
}Python uses a similar strategy by maintaining a boolean list for marked indices. It decrements values and marks indices whenever zeros are reached, checking all indices by the iteration end.
With O(n + m) time complexity due to single loops, and O(n) space usage for marking statuses.
Approach 4: Binary Search on Time
This approach uses binary search to find the earliest second when all indices in nums can be marked. The idea is to test different times by decrementing numbers optimally and marking whenever possible, to see if all numbers can be marked.
def can_mark_all(nums, change_indices, limit):
temp = nums[:]
marked = [False] * len(nums)
for s in range(limit):
idx = change_indices[s] - 1
if temp[idx] > 0:
temp[idx] -= 1
if temp[idx] == 0 and not marked[idx]:
marked[idx] = True
return all(marked)
def earliest_seconds(nums, change_indices):
left, right = 1, len(change_indices)
result = -1
while left <= right:
mid = (left + right) // 2
if can_mark_all(nums, change_indices, mid):
result = mid
right = mid - 1
else:
left = mid + 1
return result
# Example usage
print(earliest_seconds([1, 3], [1, 1, 1, 2, 1, 1, 1]))public class Solution {
public boolean canMarkAll(int[] nums, int[] changeIndices, int limit) {
int[] temp = nums.clone();
boolean[] marked = new boolean[nums.length];
for (int s = 0; s < limit; s++) {
int idx = changeIndices[s] - 1;
if (temp[idx] > 0) {
temp[idx]--;
}
if (temp[idx] == 0 && !marked[idx]) {
marked[idx] = true;
}
}
for (boolean m : marked) {
if (!m) return false;
}
return true;
}
public int earliestSeconds(int[] nums, int[] changeIndices) {
int left = 1, right = changeIndices.length, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canMarkAll(nums, changeIndices, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 3};
int[] changeIndices = {1, 1, 1, 2, 1, 1, 1};
System.out.println(sol.earliestSeconds(nums, changeIndices));
}
}#include <vector>
#include <iostream>
using namespace std;
bool can_mark_all(vector<int>& nums, vector<int>& changeIndices, int limit) {
int n = nums.size();
vector<bool> marked(n, false);
vector<int> temp(nums);
for (int s = 0; s < limit; s++) {
int idx = changeIndices[s] - 1;
if (temp[idx] > 0) {
temp[idx]--;
}
if (temp[idx] == 0 && !marked[idx]) {
marked[idx] = true;
}
}
for (bool m : marked) {
if (!m) return false;
}
return true;
}
int earliestSeconds(vector<int>& nums, vector<int>& changeIndices) {
int left = 1, right = changeIndices.size(), result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (can_mark_all(nums, changeIndices, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
// Example usage
int main() {
vector<int> nums = {1, 3};
vector<int> changeIndices = {1, 1, 1, 2, 1, 1, 1};
cout << earliestSeconds(nums, changeIndices) << endl;
return 0;
}function canMarkAll(nums, changeIndices, limit) {
const temp = nums.slice();
const marked = new Array(nums.length).fill(false);
for (let s = 0; s < limit; s++) {
const idx = changeIndices[s] - 1;
if (temp[idx] > 0) {
temp[idx]--;
}
if (temp[idx] === 0 && !marked[idx]) {
marked[idx] = true;
}
}
return marked.every(x => x);
}
function earliestSeconds(nums, changeIndices) {
let left = 1, right = changeIndices.length, result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (canMarkAll(nums, changeIndices, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
// Example usage
console.log(earliestSeconds([1, 3], [1, 1, 1, 2, 1, 1, 1]));#include <stdio.h>
#include <stdbool.h>
bool can_mark_all(int* nums, int n, int* changeIndices, int m, int limit) {
bool marked[n];
int temp[n];
for (int i = 0; i < n; i++) {
marked[i] = false;
temp[i] = nums[i];
}
for (int s = 0; s < limit; s++) {
int idx = changeIndices[s] - 1;
if (temp[idx] > 0) {
temp[idx]--;
}
if (temp[idx] == 0 && !marked[idx]) {
marked[idx] = true;
}
}
for (int i = 0; i < n; i++) {
if (!marked[i]) return false;
}
return true;
}
int earliestSeconds(int* nums, int n, int* changeIndices, int m) {
int left = 1, right = m, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (can_mark_all(nums, n, changeIndices, m, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
// Example usage
int main() {
int nums[] = {1, 3};
int changeIndices[] = {1, 1, 1, 2, 1, 1, 1};
printf("%d\n", earliestSeconds(nums, 2, changeIndices, 7));
return 0;
}using System;
public class Solution {
public bool CanMarkAll(int[] nums, int[] changeIndices, int limit) {
int[] temp = (int[])nums.Clone();
bool[] marked = new bool[nums.Length];
for (int s = 0; s < limit; s++) {
int idx = changeIndices[s] - 1;
if (temp[idx] > 0) {
temp[idx]--;
}
if (temp[idx] == 0 && !marked[idx]) {
marked[idx] = true;
}
}
foreach (bool m in marked) {
if (!m) return false;
}
return true;
}
public int EarliestSeconds(int[] nums, int[] changeIndices) {
int left = 1, right = changeIndices.Length, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (CanMarkAll(nums, changeIndices, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 3};
int[] changeIndices = {1, 1, 1, 2, 1, 1, 1};
Console.WriteLine(sol.EarliestSeconds(nums, changeIndices));
}
}This Python code utilizes binary exploration over feasible seconds using can_mark_all function to assess the full marking capability by mid-second stages, relocating bounds iteratively until the minimal true path emerges, securing the smallest effective working second.
Time usability at O(log(m) * m) due to efficient binary checks; O(n) space impacts, standing from the marking assessment need.
Approach 5: Binary Search
We notice that if we can mark all indices within t seconds, then we can also mark all indices within t' geq t seconds. Therefore, we can use binary search to find the earliest seconds.
We define the left and right boundaries of binary search as l = 1 and r = m + 1, where m is the length of the array changeIndices. For each t = \frac{l + r}{2}, we check whether we can mark all indices within t seconds. If we can, we move the right boundary to t, otherwise we move the left boundary to t + 1. Finally, we judge whether the left boundary is greater than m, if it is, return -1, otherwise return the left boundary.
The key to the problem is how to judge whether we can mark all indices within t seconds. We can use an array last to record the latest time each index needs to be marked, use a variable decrement to record the current number of times that can be reduced, and use a variable marked to record the number of indices that have been marked.
We traverse the first t elements of the array changeIndices, for each element i, if last[i] = s, then we need to check whether decrement is greater than or equal to nums[i - 1], if it is, we subtract nums[i - 1] from decrement, and add one to marked; otherwise, we return False. If last[i] neq s, then we can temporarily not mark the index, so we add one to decrement. Finally, we check whether marked is equal to n, if it is, we return True, otherwise return False.
The time complexity is O(m times log m), and the space complexity is O(n). Where n and m are the lengths of nums and changeIndices respectively.
function earliestSecondToMarkIndices(nums: number[], changeIndices: number[]): number {
const [n, m] = [nums.length, changeIndices.length];
let [l, r] = [1, m + 1];
const check = (t: number): boolean => {
const last: number[] = Array(n + 1).fill(0);
for (let s = 0; s < t; ++s) {
last[changeIndices[s]] = s;
}
let [decrement, marked] = [0, 0];
for (let s = 0; s < t; ++s) {
const i = changeIndices[s];
if (last[i] === s) {
if (decrement < nums[i - 1]) {
return false;
}
decrement -= nums[i - 1];
++marked;
} else {
++decrement;
}
}
return marked === n;
};
while (l < r) {
const mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l > m ? -1 : l;
}func earliestSecondToMarkIndices(nums []int, changeIndices []int) int {
n, m := len(nums), len(changeIndices)
l := sort.Search(m+1, func(t int) bool {
last := make([]int, n+1)
for s, i := range changeIndices[:t] {
last[i] = s
}
decrement, marked := 0, 0
for s, i := range changeIndices[:t] {
if last[i] == s {
if decrement < nums[i-1] {
return false
}
decrement -= nums[i-1]
marked++
} else {
decrement++
}
}
return marked == n
})
if l > m {
return -1
}
return l
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Decrement Strategy | Time Complexity: O(m), Space Complexity: O(n). |
| Recursive Backtracking | Time Complexity: Exponential; Space Complexity: O(m) owing to call stack depth. |
| Greedy Decrement and Marking | With O(n + m) time complexity due to single loops, and O(n) space usage for marking statuses. |
| Binary Search on Time | Time usability at O(log(m) * m) due to efficient binary checks; O(n) space impacts, standing from the marking assessment need. |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | Exponential | Exponential | Conceptual understanding or very small inputs |
| Greedy Decrement Simulation | O(n + m) | O(n) | Checking feasibility when time limit is already fixed |
| Binary Search + Greedy Validation | O((n + m) log m) | O(n) | Finding the earliest valid second in the general case |
Frequently asked questions
Is Earliest Second to Mark Indices I easy or hard?
Earliest Second to Mark Indices I is classified as a Medium difficulty problem on LeetCode with an acceptance rate around 36%. The challenge comes from recognizing the monotonic property that allows binary search and designing a correct greedy feasibility check.
Earliest Second to Mark Indices I Python or Java solution?
The algorithm can be implemented in Python, Java, C++, JavaScript, and other languages using the same structure: a binary search loop with a helper function that validates whether marking is possible within a given number of seconds. The helper typically uses arrays and simple iteration.
What is the best approach for Earliest Second to Mark Indices I?
The most efficient solution uses binary search on the answer combined with a greedy feasibility check. You search for the earliest second t where marking all indices becomes possible. For each candidate t, simulate whether all required decrements can occur before their mark operations. This approach runs in O((n + m) log m) time with O(n) extra space.
How to solve Earliest Second to Mark Indices I in O((n+m) log m)?
Use binary search over the possible seconds from 1 to m. For each candidate second, run a greedy simulation that verifies whether every index can finish its decrements before being marked. If the check succeeds, search the earlier half; otherwise search later seconds. This approach relies on the monotonic property that if time t works, any larger time will also work.
What data structure is used in Earliest Second to Mark Indices I?
The solution primarily uses arrays to track remaining decrement counts and processed operations. During the feasibility check, you iterate through the operations and maintain counters to ensure each index has enough time to reach zero before marking.
What is the time complexity of Earliest Second to Mark Indices I?
The optimal solution runs in O((n + m) log m) time. Binary search is performed over the number of seconds m, and each feasibility check scans the arrays once. Space complexity is O(n) for tracking remaining decrements and marked indices.
Is Earliest Second to Mark Indices I asked at Google, Amazon, or Meta?
Problems involving scheduling with binary search and greedy validation frequently appear in interviews at large tech companies like Google, Amazon, and Meta. While the exact problem may vary, the pattern of binary searching an answer combined with a feasibility check is a common interview topic.