3049. Earliest Second to Mark Indices II LeetCode Solution
In this guide, you will get 3049. Earliest Second to Mark Indices II LeetCode Solution with the best time and space complexity. The solution to Earliest Second to Mark Indices II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Earliest Second to Mark Indices II
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.
Set nums[changeIndices[s]] to any non-negative value.
Choose an index i in the range [1, n], where nums[i] is equal to 0, and mark index i.
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 = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
Output: 6
Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3].
Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0].
Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0].
Second 4: Mark index 1, since nums[1] is equal to 0.
Second 5: Mark index 2, since nums[2] is equal to 0.
Second 6: Mark index 3, since nums[3] 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 2:
Input: nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
Output: 7
Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
Second 1: Mark index 1, since nums[1] is equal to 0.
Second 2: Mark index 2, since nums[2] is equal to 0.
Second 3: Decrement index 4 by one. nums becomes [0,0,1,1].
Second 4: Decrement index 4 by one. nums becomes [0,0,1,0].
Second 5: Decrement index 3 by one. nums becomes [0,0,0,0].
Second 6: Mark index 3, since nums[3] is equal to 0.
Second 7: Mark index 4, since nums[4] 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 7th second.
Hence, the answer is 7.
Input: nums = [1,2,3], changeIndices = [1,2,3]
Output: -1
Explanation: In this example, it can be shown that it is impossible to mark all indices, as we don’t have enough seconds.
Hence, the answer is -1.
Constraints:
1 <= n == nums.length <= 5000
0 <= nums[i] <= 109
1 <= m == changeIndices.length <= 5000
1 <= changeIndices[i] <= n
Complexity Analysis
Time Complexity: O(m + n + m\log m)
Space Complexity: O(m)
3049. Earliest Second to Mark Indices II LeetCode Solution in C++
class Solution {
public:
int earliestSecondToMarkIndices(vector<int>& nums,
vector<int>& changeIndices) {
const long numsSum = accumulate(nums.begin(), nums.end(), 0L);
// {the second: the index of nums can be zeroed at the current second}
const unordered_map<int, int> secondToIndex =
getSecondToIndex(nums, changeIndices);
int l = 0;
int r = changeIndices.size() + 1;
while (l < r) {
const int m = (l + r) / 2;
if (canMark(nums, secondToIndex, m, numsSum))
r = m;
else
l = m + 1;
}
return l <= changeIndices.size() ? l : -1;
}
private:
// Returns true if all indices of `nums` can be marked within `maxSecond`.
bool canMark(const vector<int>& nums,
const unordered_map<int, int>& secondToIndex, int maxSecond,
const long numsSum) {
// Use a min-heap to greedily pop out the minimum number, which yields the
// least saving.
priority_queue<int, vector<int>, greater<int>> minHeap;
int marks = 0;
for (int second = maxSecond - 1; second >= 0; --second) {
if (const auto it = secondToIndex.find(second);
it != secondToIndex.end()) {
// The number mapped by the index is a candidate to be zeroed out.
const int index = it->second;
minHeap.push(nums[index]);
if (marks == 0) {
// Running out of marks, so need to pop out the minimum number.
// So, the current second will be used to mark an index.
minHeap.pop();
++marks;
} else {
// There're enough marks.
// So, the current second will be used to zero out a number.
--marks;
}
} else {
// There's no candidate to be zeroed out.
// So, the current second will be used to mark an index.
++marks;
}
}
const int heapSize = minHeap.size();
const long decrementAndMarkCost =
numsSum - getHeapSum(minHeap) + (nums.size() - heapSize);
const long zeroAndMarkCost = heapSize + heapSize;
return decrementAndMarkCost + zeroAndMarkCost <= maxSecond;
}
long getHeapSum(priority_queue<int, vector<int>, greater<int>>& heap) {
long heapSum = 0;
while (!heap.empty())
heapSum += heap.top(), heap.pop();
return heapSum;
}
unordered_map<int, int> getSecondToIndex(const vector<int>& nums,
const vector<int>& changeIndices) {
// {the `index` of nums: the earliest second to zero out nums[index]}
unordered_map<int, int> indexToFirstSecond;
unordered_map<int, int> secondToIndex;
for (int zeroIndexedSecond = 0; zeroIndexedSecond < changeIndices.size();
++zeroIndexedSecond) {
// Convert to 0-indexed.
const int index = changeIndices[zeroIndexedSecond] - 1;
if (nums[index] > 0 && !indexToFirstSecond.contains(index))
indexToFirstSecond[index] = zeroIndexedSecond;
}
for (const auto& [index, second] : indexToFirstSecond)
secondToIndex[second] = index;
return secondToIndex;
}
}; /* code provided by PROGIEZ */
3049. Earliest Second to Mark Indices II LeetCode Solution in Java
class Solution {
public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
final long numsSum = Arrays.stream(nums).asLongStream().sum();
// {the second: the index of nums can be zeroed at the current second}
Map<Integer, Integer> secondToIndex = getSecondToIndex(nums, changeIndices);
int l = 0;
int r = changeIndices.length + 1;
while (l < r) {
final int m = (l + r) / 2;
if (canMark(nums, secondToIndex, m))
r = m;
else
l = m + 1;
}
return l <= changeIndices.length ? l : -1;
}
// Returns true if all indices of `nums` can be marked within `maxSecond`.
private boolean canMark(int[] nums, Map<Integer, Integer> secondToIndex, int maxSecond,
final long numsSum) {
// Use a min-heap to greedily pop out the minimum number, which yields the
// least saving.
Queue<Integer> minHeap = new PriorityQueue<>();
int marks = 0;
for (int second = maxSecond - 1; second >= 0; --second) {
if (secondToIndex.containsKey(second)) {
// The number mapped by the index is a candidate to be zeroed out.
final int index = secondToIndex.get(second);
minHeap.offer(nums[index]);
if (marks == 0) {
// Running out of marks, so need to pop out the minimum number.
// So, the current second will be used to mark an index.
minHeap.poll();
++marks;
} else {
// There're enough marks.
// So, the current second will be used to zero out a number.
--marks;
}
} else {
// There's no candidate to be zeroed out.
// So, the current second will be used to mark an index.
++marks;
}
}
final int heapSize = minHeap.size();
final long decrementAndMarkCost = numsSum - getHeapSum(minHeap) + (nums.length - heapSize);
final long zeroAndMarkCost = heapSize + heapSize;
return decrementAndMarkCost + zeroAndMarkCost <= maxSecond;
}
private long getHeapSum(Queue<Integer> minHeap) {
long sum = 0;
while (!minHeap.isEmpty())
sum += minHeap.poll();
return sum;
}
private Map<Integer, Integer> getSecondToIndex(int[] nums, int[] changeIndices) {
// {the `index` of nums: the earliest second to zero out nums[index]}
Map<Integer, Integer> indexToFirstSecond = new HashMap<>();
Map<Integer, Integer> secondToIndex = new HashMap<>();
for (int zeroIndexedSecond = 0; zeroIndexedSecond < changeIndices.length; ++zeroIndexedSecond) {
// Convert to 0-indexed.
final int index = changeIndices[zeroIndexedSecond] - 1;
if (nums[index] > 0)
indexToFirstSecond.putIfAbsent(index, zeroIndexedSecond);
}
for (Map.Entry<Integer, Integer> entry : indexToFirstSecond.entrySet()) {
final int index = entry.getKey();
final int second = entry.getValue();
secondToIndex.put(second, index);
}
return secondToIndex;
}
} // code provided by PROGIEZ
3049. Earliest Second to Mark Indices II LeetCode Solution in Python
class Solution:
def earliestSecondToMarkIndices(
self,
nums: list[int],
changeIndices: list[int],
) -> int:
# {the second: the index of nums can be zeroed at the current second}
secondToIndex = self._getSecondToIndex(nums, changeIndices)
numsSum = sum(nums)
def canMark(maxSecond: int) -> bool:
"""
Returns True if all indices of `nums` can be marked within `maxSecond`.
"""
# Use a min-heap to greedily pop out the minimum number, which yields the
# least saving.
minHeap = []
marks = 0
for second in range(maxSecond - 1, -1, -1):
if second in secondToIndex:
# The number mapped by the index is a candidate to be zeroed out.
index = secondToIndex[second]
heapq.heappush(minHeap, nums[index])
if marks == 0:
# Running out of marks, so need to pop out the minimum number.
# So, the current second will be used to mark an index.
heapq.heappop(minHeap)
marks += 1
else:
# There're enough marks.
# So, the current second will be used to zero out a number.
marks -= 1
else:
# There's no candidate to be zeroed out.
# So, the current second will be used to mark an index.
marks += 1
decrementAndMarkCost = ((numsSum - sum(minHeap)) +
(len(nums) - len(minHeap)))
zeroAndMarkCost = len(minHeap) + len(minHeap)
return decrementAndMarkCost + zeroAndMarkCost <= maxSecond
l = 0
r = len(changeIndices) + 1
ans = bisect.bisect_left(range(l, r), True, key=canMark) + l
return ans if ans <= len(changeIndices) else -1
def _getSecondToIndex(
self,
nums: list[int],
changeIndices: list[int],
) -> dict[int, int]:
# {the `index` of nums: the earliest second to zero out nums[index]}
indexToFirstSecond = {}
for zeroIndexedSecond, oneIndexedIndex in enumerate(changeIndices):
index = oneIndexedIndex - 1 # Convert to 0-indexed.
if nums[index] > 0 and index not in indexToFirstSecond:
indexToFirstSecond[index] = zeroIndexedSecond
return {second: index for index, second in indexToFirstSecond.items()} # code by PROGIEZ
