Description
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 × log n), and the space complexity is O(n). Where n is the length of array nums.
PythonJavaC++GoTypeScript
class Solution:
def countOperationsToEmptyArray(self, nums: List[int]) -> int:
pos = {x: i for i, x in enumerate(nums)}
nums.sort()
sl = SortedList()
ans = pos[nums[0]] + 1
n = len(nums)
for k, (a, b) in enumerate(pairwise(nums)):
i, j = pos[a], pos[b]
d = j - i - sl.bisect(j) + sl.bisect(i)
ans += d + (n - k) * int(i > j)
sl.add(i)
return ans(code-box)
class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
public int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= x & -x;
}
return s;
}
}
class Solution {
public long countOperationsToEmptyArray(int[] nums) {
int n = nums.length;
Map<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < n; ++i) {
pos.put(nums[i], i);
}
Arrays.sort(nums);
long ans = pos.get(nums[0]) + 1;
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (int k = 0; k < n - 1; ++k) {
int i = pos.get(nums[k]), j = pos.get(nums[k + 1]);
long d = j - i - (tree.query(j + 1) - tree.query(i + 1));
ans += d + (n - k) * (i > j ? 1 : 0);
tree.update(i + 1, 1);
}
return ans;
}
}(code-box)
class BinaryIndexedTree {
public:
BinaryIndexedTree(int _n)
: n(_n)
, c(_n + 1) {}
void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
int query(int x) {
int s = 0;
while (x) {
s += c[x];
x -= x & -x;
}
return s;
}
private:
int n;
vector<int> c;
};
class Solution {
public:
long long countOperationsToEmptyArray(vector<int>& nums) {
unordered_map<int, int> pos;
int n = nums.size();
for (int i = 0; i < n; ++i) {
pos[nums[i]] = i;
}
sort(nums.begin(), nums.end());
BinaryIndexedTree tree(n);
long long ans = pos[nums[0]] + 1;
for (int k = 0; k < n - 1; ++k) {
int i = pos[nums[k]], j = pos[nums[k + 1]];
long long d = j - i - (tree.query(j + 1) - tree.query(i + 1));
ans += d + (n - k) * int(i > j);
tree.update(i + 1, 1);
}
return ans;
}
};(code-box)
type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += x & -x
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= x & -x
}
return s
}
func countOperationsToEmptyArray(nums []int) int64 {
n := len(nums)
pos := map[int]int{}
for i, x := range nums {
pos[x] = i
}
sort.Ints(nums)
tree := newBinaryIndexedTree(n)
ans := pos[nums[0]] + 1
for k := 0; k < n-1; k++ {
i, j := pos[nums[k]], pos[nums[k+1]]
d := j - i - (tree.query(j+1) - tree.query(i+1))
if i > j {
d += n - k
}
ans += d
tree.update(i+1, 1)
}
return int64(ans)
}(code-box)
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
public update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] += v;
x += x & -x;
}
}
public query(x: number): number {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= x & -x;
}
return s;
}
}
function countOperationsToEmptyArray(nums: number[]): number {
const pos: Map<number, number> = new Map();
const n = nums.length;
for (let i = 0; i < n; ++i) {
pos.set(nums[i], i);
}
nums.sort((a, b) => a - b);
const tree = new BinaryIndexedTree(n);
let ans = pos.get(nums[0])! + 1;
for (let k = 0; k < n - 1; ++k) {
const i = pos.get(nums[k])!;
const j = pos.get(nums[k + 1])!;
let d = j - i - (tree.query(j + 1) - tree.query(i + 1));
if (i > j) {
d += n - k;
}
ans += d;
tree.update(i + 1, 1);
}
return ans;
}(code-box)
Solution 2
Python
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x):
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def countOperationsToEmptyArray(self, nums: List[int]) -> int:
pos = {x: i for i, x in enumerate(nums)}
nums.sort()
ans = pos[nums[0]] + 1
n = len(nums)
tree = BinaryIndexedTree(n)
for k, (a, b) in enumerate(pairwise(nums)):
i, j = pos[a], pos[b]
d = j - i - tree.query(j + 1) + tree.query(i + 1)
ans += d + (n - k) * int(i > j)
tree.update(i + 1, 1)
return ans(code-box)
