Problem

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 makenums empty.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Input: nums = [1,2,3]
Output: 3


Operation | Array  
---|---  
1 | [2, 3]  
2 | [3]  
3 | []  
  

Constraints

  • 1 <= nums.length <= 10^5
  • -109 <= nums[i] <= 10^9
  • All values in nums are distinct.

Solution

Method 1 – Binary Indexed Tree (Fenwick Tree) + Sorting

Intuition

Since all numbers are distinct, the smallest element can be found and removed efficiently. To count the number of rotations (moves to the end) needed before each removal, we can use a Binary Indexed Tree (Fenwick Tree) to track which elements remain. We process the elements in increasing order, and for each, count how many elements are before it (i.e., how many rotations are needed).

Approach

  1. Map each value to its index in the original array.
  2. Sort the array to process removals in increasing order.
  3. Use a Binary Indexed Tree to track which indices are still present.
  4. For each value (in sorted order), count the number of elements before its index (using prefix sum in BIT), which gives the number of rotations needed.
  5. Add 1 for the removal operation itself.
  6. Update the BIT to remove the current index.
  7. Sum all operations and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class BIT {
    vector<int> tree;
public:
    BIT(int n) : tree(n+2) {}
    void add(int i, int v) { for (++i; i < tree.size(); i += i & -i) tree[i] += v; }
    int sum(int i) { int s = 0; for (++i; i > 0; i -= i & -i) s += tree[i]; return s; }
};
class Solution {
public:
    long long countOperationsToEmptyArray(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int,int>> arr;
        for (int i = 0; i < n; ++i) arr.push_back({nums[i], i});
        sort(arr.begin(), arr.end());
        BIT bit(n);
        for (int i = 0; i < n; ++i) bit.add(i, 1);
        long long ans = 0;
        for (auto& [val, idx] : arr) {
            ans += bit.sum(idx-1) + 1;
            bit.add(idx, -1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func countOperationsToEmptyArray(nums []int) int64 {
    n := len(nums)
    arr := make([][2]int, n)
    for i, v := range nums {
        arr[i] = [2]int{v, i}
    }
    sort.Slice(arr, func(i, j int) bool { return arr[i][0] < arr[j][0] })
    bit := make([]int, n+2)
    add := func(i, v int) { for i++; i < len(bit); i += i & -i { bit[i] += v } }
    sum := func(i int) int { s := 0; for i++; i > 0; i -= i & -i { s += bit[i] }; return s }
    for i := 0; i < n; i++ { add(i, 1) }
    var ans int64
    for _, p := range arr {
        idx := p[1]
        ans += int64(sum(idx-1) + 1)
        add(idx, -1)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
class BIT {
    int[] tree;
    BIT(int n) { tree = new int[n+2]; }
    void add(int i, int v) { for (++i; i < tree.length; i += i & -i) tree[i] += v; }
    int sum(int i) { int s = 0; for (++i; i > 0; i -= i & -i) s += tree[i]; return s; }
}
class Solution {
    public long countOperationsToEmptyArray(int[] nums) {
        int n = nums.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++i) arr[i] = new int[]{nums[i], i};
        Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));
        BIT bit = new BIT(n);
        for (int i = 0; i < n; ++i) bit.add(i, 1);
        long ans = 0;
        for (int[] p : arr) {
            int idx = p[1];
            ans += bit.sum(idx-1) + 1;
            bit.add(idx, -1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class BIT(n: Int) {
    val tree = IntArray(n+2)
    fun add(i: Int, v: Int) { var i = i+1; while (i < tree.size) { tree[i] += v; i += i and -i } }
    fun sum(i: Int): Int { var s = 0; var i = i+1; while (i > 0) { s += tree[i]; i -= i and -i }; return s }
}
class Solution {
    fun countOperationsToEmptyArray(nums: IntArray): Long {
        val n = nums.size
        val arr = nums.mapIndexed { i, v -> v to i }.sortedBy { it.first }
        val bit = BIT(n)
        for (i in 0 until n) bit.add(i, 1)
        var ans = 0L
        for ((_, idx) in arr) {
            ans += bit.sum(idx-1) + 1
            bit.add(idx, -1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class BIT:
    def __init__(self, n: int):
        self.tree = [0] * (n+2)
    def add(self, i: int, v: int):
        i += 1
        while i < len(self.tree):
            self.tree[i] += v
            i += i & -i
    def sum(self, i: int) -> int:
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
class Solution:
    def countOperationsToEmptyArray(self, nums: list[int]) -> int:
        n = len(nums)
        arr = sorted((v, i) for i, v in enumerate(nums))
        bit = BIT(n)
        for i in range(n):
            bit.add(i, 1)
        ans = 0
        for _, idx in arr:
            ans += bit.sum(idx-1) + 1
            bit.add(idx, -1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
struct BIT { tree: Vec<i32> }
impl BIT {
    fn new(n: usize) -> Self { Self { tree: vec![0; n+2] } }
    fn add(&mut self, mut i: usize, v: i32) { i += 1; while i < self.tree.len() { self.tree[i] += v; i += i & (!i + 1) } }
    fn sum(&self, mut i: usize) -> i32 { i += 1; let mut s = 0; while i > 0 { s += self.tree[i]; i -= i & (!i + 1) } s }
}
impl Solution {
    pub fn count_operations_to_empty_array(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut arr: Vec<_> = nums.iter().enumerate().map(|(i, &v)| (v, i)).collect();
        arr.sort();
        let mut bit = BIT::new(n);
        for i in 0..n { bit.add(i, 1); }
        let mut ans = 0i64;
        for &(_, idx) in &arr {
            ans += bit.sum(idx-1) as i64 + 1;
            bit.add(idx, -1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class BIT {
    tree: number[];
    constructor(n: number) { this.tree = new Array(n+2).fill(0); }
    add(i: number, v: number) { for (i++; i < this.tree.length; i += i & -i) this.tree[i] += v; }
    sum(i: number): number { let s = 0; for (i++; i > 0; i -= i & -i) s += this.tree[i]; return s; }
}
class Solution {
    countOperationsToEmptyArray(nums: number[]): number {
        const n = nums.length;
        const arr = nums.map((v, i) => [v, i]).sort((a, b) => a[0] - b[0]);
        const bit = new BIT(n);
        for (let i = 0; i < n; ++i) bit.add(i, 1);
        let ans = 0;
        for (const [_, idx] of arr) {
            ans += bit.sum(idx-1) + 1;
            bit.add(idx, -1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), as we sort and use BIT for each element.
  • 🧺 Space complexity: O(n), for the BIT and index mapping.