In this guide, you will get 2659. Make Array Empty LeetCode Solution with the best time and space complexity. The solution to Make Array Empty 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.
You are given an integer array nums containing distinct numbers, and you can perform the following operations until the array is empty:
If the first element has the smallest value, remove it
Otherwise, put the first element at the end of the array.
Return an integer denoting the number of operations it takes to make nums empty.
Example 1:
Input: nums = [3,4,-1]
Output: 5
Operation
Array
1
[4, -1, 3]
2
[-1, 3, 4]
3
[3, 4]
4
[4]
5
[]
Example 2:
Input: nums = [1,2,4,3]
Output: 5
Operation
Array
1
[2, 4, 3]
2
[4, 3]
3
[3, 4]
4
[4]
5
[]
Example 3:
Input: nums = [1,2,3]
Output: 3
Operation
Array
1
[2, 3]
2
[3]
3
[]
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
All values in nums are distinct.
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
2659. Make Array Empty LeetCode Solution in C++
class Solution {
public:
long long countOperationsToEmptyArray(vector<int>& nums) {
const int n = nums.size();
long ans = n;
unordered_map<int, int> numToIndex;
for (int i = 0; i < n; ++i)
numToIndex[nums[i]] = i;
ranges::sort(nums);
for (int i = 1; i < n; ++i)
// On the i-th step we've already removed the i - 1 smallest numbers and
// can ignore them. If an element nums[i] has smaller index in origin
// array than nums[i - 1], we should rotate the whole left array n - i
// times to set nums[i] element on the first position.
if (numToIndex[nums[i]] < numToIndex[nums[i - 1]])
ans += n - i;
return ans;
}
}; /* code provided by PROGIEZ */
2659. Make Array Empty LeetCode Solution in Java
class Solution {
public long countOperationsToEmptyArray(int[] nums) {
final int n = nums.length;
long ans = n;
Map<Integer, Integer> 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 the i-th step we've already removed the i - 1 smallest numbers and
// can ignore them. If an element nums[i] has smaller index in origin
// array than nums[i - 1], we should rotate the whole left array n - i
// times to set nums[i] element on the first position.
if (numToIndex.get(nums[i]) < numToIndex.get(nums[i - 1]))
ans += n - i;
return ans;
}
} // code provided by PROGIEZ
2659. Make Array Empty LeetCode Solution in Python
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 the i-th step we've already removed the i - 1 smallest numbers and
# can ignore them. If an element nums[i] has smaller index in origin
# array than nums[i - 1], we should rotate the whole left array n - i
# times to set nums[i] element on the first position.
if numToIndex[nums[i]] < numToIndex[nums[i - 1]]:
ans += n - i
return ans # code by PROGIEZ
