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.
Solutions
Solution 1: Hash Table + Sorting + Fenwick Tree
First, we use a hash table $pos$ to record the position of each element in array $nums$. Then, we sort array $nums$. The initial answer is the position of the minimum element in array $nums$ plus 1, which is $ans = pos[nums[0]] + 1$.
Next, we traverse the sorted array $nums$, the indexes of the two adjacent elements $a$ and $b$ are $i = pos[a]$, $j = pos[b]$. The number of operations needed to move the second element $b$ to the first position of the array and delete it is equal to the interval between the two indexes, minus the number of indexes deleted between the two indexes, and add the number of operations to the answer. We can use a Fenwick tree or an ordered list to maintain the deleted indexes between two indexes, so that we can find the number of deleted indexes between two indexes in $O(\log n)$ time. Note that if $i \gt j$, then we need to increase $n - k$ operations, where $k$ is the current position.
After the traversal is over, return the number of operations $ans$.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of array $nums$.