Leetcode # 2869. Minimum Operations to Collect Elements

Problem

https://leetcode.com/contest/biweekly-contest-114/problems/minimum-operations-to-collect-elements/

• The input is generated such that you can collect elements 1, 2, …, k.
  ⇒ find len(nums) – min(indices(num)[-1] for num in range(1, k + 1))

Solution

First Ver.

Time Complexity: O(2 * n) ≡ O(n)
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minOperations(self, nums: List[int], k: int) -> int:
    final_index = {}
    for i, num in enumerate(nums):
      final_index[num] = i
    return len(nums) - min(final_index[num] for num in range(1, k + 1))

Refined Ver.

Time Complexity: O(n)
Space Complexity: O(k)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minOperations(self, nums: List[int], k: int) -> int:
    final_index = {}
    min_final_index = len(nums)
    for i, num in enumerate(nums[::-1]):
      if num <= k and num not in final_index:
        final_index[num] = len(nums) - i - 1
        if final_index[num] < min_final_index:
          min_final_index = final_index[num]
    return len(nums) - min_final_index

Last Updated on 2023/10/01 by A1go