2659. Make Array Empty

• Time: $O(\texttt{sort})$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: long long countOperationsToEmptyArray(vector& nums) { const int n = nums.size(); long long ans = n; unordered_map numToIndex; for (int i = 0; i < n; ++i) numToIndex[nums[i]] = i; sort(nums.begin(), nums.end()); for (int i = 1; i < n; ++i) // On i-th step we've already removed i - 1 smallest nums and can ignore // them. If an element nums[i] has smaller index in origin array than // nums[i - 1], we should rotate whole left array n - i times to set // nums[i] element on the 1st position. if (numToIndex[nums[i]] < numToIndex[nums[i - 1]]) ans += n - i; return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public long countOperationsToEmptyArray(int[] nums) { final int n = nums.length; long ans = n; Map numToIndex = new HashMap<>(); for (int i = 0; i < n; ++i) numToIndex.put(nums[i], i); Arrays.sort(nums); for (int i = 1; i < n; ++i) // On i-th step we've already removed i - 1 smallest nums and can ignore // them. If an element nums[i] has smaller index in origin array than // nums[i - 1], we should rotate whole left array n - i times to set // nums[i] element on the 1st position. if (numToIndex.get(nums[i]) < numToIndex.get(nums[i - 1])) ans += n - i; return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution: def countOperationsToEmptyArray(self, nums: List[int]) -> int: n = len(nums) ans = n numToIndex = {} for i, num in enumerate(nums): numToIndex[num] = i nums.sort() for i in range(1, n): # On i-th step we've already removed i - 1 smallest nums and can ignore # them. If an element nums[i] has smaller index in origin array than # nums[i - 1], we should rotate whole left array n - i times to set # nums[i] element on the 1st position. if numToIndex[nums[i]] < numToIndex[nums[i - 1]]: ans += n - i return ans