Skip to content

3049. Earliest Second to Mark Indices II 👍

  • Time: $O(m + n + m\log m)$
  • Space: $O(m)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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()}