2659. Make Array Empty

HardGreedyBinary Indexed TreeSegment TreeArrayBinary SearchOrdered SetSorting

Problem Description

Given an array of distinct integers called nums, the task is to find out how many operations it will take to make this array empty. The operations allowed are:

If the first element of nums is the smallest overall, you can remove it from the array.
If the first element is not the smallest, you can move it to the end of the array.

Intuition

To find the least number of operations to make the nums array empty, we need to identify an approach that can efficiently keep track of element positions after each removal or shift operation. One way to minimize the operation count is by always aiming to remove the smallest element when it reaches the beginning of the array. To achieve this, a sorted structure will be handy as it promptly identifies the smallest element.

Sorting the nums array could help, but only if we keep track of the original positions of the elements in a separate data structure (usually a hash table). This way, we can directly infer how many operations are needed to move an element to the beginning based on its original position.

The sorted nature of the array allows us to focus only on adjacent elements because after sorting, they will be the ones contending to move to the first position and get removed. Hence, we compare adjacent elements in the sorted array, check their initial positions in the original nums array, and calculate the required moves.

The overall goal lies in maintaining and updating the state of the array after each operation optimally, which would be an expensive task if we were to simulate the process directly. This is where a Fenwick Tree (Binary Indexed Tree) or a sorted list comes into the picture, as it allows us to quickly determine the number of elements that have been removed between two given indices over time. The sorted list is preferred when the implementation language provides it, due to its simplicity and readability.

Intuitively, we start with the number of operations as the position of the minimum element plus one, due to the initial sort. Then, we iterate through pairs of adjacent sorted elements, updating the operations count by considering the original positions and the elements removed in between.

Learn more about Greedy, Segment Tree, Binary Search and Sorting patterns.

Solution Approach

The solution follows these steps:

Creating a Position Map: The solution starts by creating a hash table to store the position of each element in the nums array before sorting. This map is represented as pos in the code. It is crucial because after sorting the nums array, we need a way to reference the original position of each element.
Sorting the Array: Next, the array is sorted to streamline the process of finding the smallest number and keeping track of the original positions to calculate the number of operations needed.
Calculating Initial Operations: The number of initial operations is determined by finding the position of the minimum element in the sorted array (nums[0] after sorting) and then adding one, which is calculated as ans = pos[nums[0]] + 1.
Using a Sorted List: The SortedList data structure is used to maintain the indices of the elements that have already been removed from the array. This is because as elements are removed from the array, it becomes challenging to determine the "real" position of elements within the non-removed subset of the original array.
Iterating Through Pairs of Elements: The code iterates through pairs of adjacent elements in the sorted array (using pairwise(nums)), which would be consecutive when considering removals. For each pair of adjacent elements a and b, their original positions i and j are looked up from the pos map.
Updating the Operation Count: For each pair (a, b) traversed, the operations required to bring b to the front and remove it is based on the number of elements between i and j that have already been removed. This is where the SortedList comes in handy, as it can quickly tell how many elements have been removed in the range (i, j) using binary search, which is done with sl.bisect(j) - sl.bisect(i).
Accounting for Wraps: If the original position of a is greater than b (i > j), this means we have a wrap-around situation since the sorted order reverses the original order for these two elements. Here, each wrap adds (n - k) to our operations count where k is the index of the current pair in the sorted array.
Handling Remaining Elements: The remaining elements (if any) are sorted smaller than the current element, and as such, they will be removed in the order they appear in the sorted array, hence no further operations need to be tracked.
Returning the Result: After traversing through all the pairs, the variable ans holds the total number of operations required to make the nums empty, which is returned as the result.

With this approach using a hash table, sorting, and a SortedList, we can efficiently calculate the operation count in O(n log n) time complexity due to the sorting and binary searches in the sorted list.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach with the following input array:

nums = [4, 3, 1, 2]

Step 1: Creating a Position Map

We create a position map that keeps track of the original positions of the elements:

pos = {4: 0, 3: 1, 1: 2, 2: 3}

Step 2: Sorting the Array

Next, we sort the array:

sorted_nums = [1, 2, 3, 4]

The position map now helps us remember the original positions of these sorted elements.

Step 3: Calculating Initial Operations

The first sorted element is 1, which was originally at position 2 in the nums array. The number of operations to remove it (as it is the smallest) is:

ans = pos[1] + 1 = 2 + 1 = 3

Step 4: Using a Sorted List

We use a SortedList to maintain the indices of elements:

sl = [0, 1, 2, 3]  // This corresponds to the original indices of the sorted array elements

Step 5: Iterating Through Pairs of Elements

We iterate through pairs of adjacent elements in sorted_nums. Let's visualize this process:

Pair (1, 2): original positions are i = 2, j = 3.
Pair (2, 3): original positions are i = 3, j = 1. (Wrap around as i > j)
Pair (3, 4): original positions are i = 1, j = 0.

Step 6: Updating the Operation Count

We update the operations count as we consider each pair:

Pair (1, 2): ans += (pos[2] - sl.bisect(pos[1])) = 3 + (3 - 1) = 5 Update sl to remove the index of 1: sl = [0, 1, 3]
Pair (2, 3): ans += (pos[3] + sl.size() - sl.bisect(pos[2])) = 5 + (1 + 3 - 2) = 7 Update sl to remove the index of 2: sl = [0, 1] The wrap is accounted for by adding the size of sl before 2, which is 2: ans += 2.
Pair (3, 4): Since 3 is before 4 in sorted_nums, and in this case, it also comes before in the original array, we have no more wraps, and ans is not updated here. Update sl to remove the index of 3: sl = [0]

Step 7: Accounting for Wraps

We've already accounted for the wrap in Step 6 during the pair (2, 3) step.

Step 8: Handling Remaining Elements

None remaining, as all elements in pairs have been considered and will be removed in the calculated number of operations.

Step 9: Returning the Result

The total number of operations required to make nums empty is stored in ans, which is 9 in this example.

The operation calculation considers moving the elements to the end of the array to eventually place the smallest elements at the start for removal. Through this process, we arrive at the efficient solution for the given problem without having to simulate each operation explicitly, all while maintaining a time complexity of O(n log n) due to the sorting and the binary searches within the sorted list.

Solution Implementation

1from sortedcontainers import SortedList
2from typing import List
3from itertools import pairwise  # pairwise available from Python 3.10
4
5class Solution:
6    def count_operations_to_empty_array(self, nums: List[int]) -> int:
7        # Create a dictionary to map each number to its initial position
8        position_map = {value: index for index, value in enumerate(nums)}
9        # Sort the list to facilitate pairwise operation
10        nums.sort()
11      
12        # Create a SortedList to keep track of positions considered
13        sorted_positions = SortedList()
14      
15        # Initialize count with the operations for first position
16        # Since list is sorted, minimum operations is the position (0-indexed) plus 1
17        operations_count = position_map[nums[0]] + 1
18      
19        # Get the total number of elements
20        total_elements = len(nums)
21      
22        # Iterate over each pair of adjacent elements
23        for k, (current, next) in enumerate(pairwise(nums)):
24            # Retrieve initial positions of the pair
25            current_position = position_map[current]
26            next_position = position_map[next]
27          
28            # Calculate the distance considering the elements between them which have been moved
29            distance = next_position - current_position - sorted_positions.bisect(next_position) + sorted_positions.bisect(current_position)
30          
31            # Increment operations count by the distance and adjustments for previous moves
32            operations_count += distance + (total_elements - k - 1) * int(current_position > next_position)
33          
34            # Add the current position to the sorted list as it has now been considered
35            sorted_positions.add(current_position)
36      
37        # Return the total operations count
38        return operations_count
39

1class BinaryIndexedTree {
2    private final int size; // Size of the array represented by the Binary Indexed Tree.
3    private final int[] tree; // The Binary Indexed Tree data structure.
4
5    // Constructor to initialize the Binary Indexed Tree with a given size.
6    public BinaryIndexedTree(int size) {
7        this.size = size;
8        this.tree = new int[size + 1]; // Initialize the tree array with an extra element.
9    }
10
11    // Function to update the Binary Indexed Tree with a delta at a given index.
12    public void update(int index, int delta) {
13        while (index <= size) {
14            tree[index] += delta; // Increment the value at the current index by delta.
15            index += index & -index; // Move to the next index to update.
16        }
17    }
18
19    // Function to query the cumulative frequency up to a given index.
20    public int query(int index) {
21        int sum = 0; // Initialize sum to accumulate the frequencies.
22        while (index > 0) {
23            sum += tree[index]; // Add the value at the current index to sum.
24            index -= index & -index; // Move to the parent index.
25        }
26        return sum; // Return the cumulative frequency.
27    }
28}
29
30class Solution {
31    public long countOperationsToEmptyArray(int[] nums) {
32        int n = nums.length; // Length of the input array nums.
33        Map<Integer, Integer> positions = new HashMap<>(); // Map to store the original positions of array elements.
34
35        // Fill the positions map with each number's last occurrence's index.
36        for (int i = 0; i < n; ++i) {
37            positions.put(nums[i], i);
38        }
39
40        // Sort the nums array to process in non-decreasing order.
41        Arrays.sort(nums);
42      
43        // Calculate initial answer by adding the original position of the first element + 1.
44        long answer = positions.get(nums[0]) + 1;
45      
46        // Instantiate a Binary Indexed Tree.
47        BinaryIndexedTree bit = new BinaryIndexedTree(n);
48
49        // Process each element in the sorted nums array.
50        for (int k = 0; k < n - 1; ++k) {
51            int i = positions.get(nums[k]);     // Original index of the k-th element.
52            int j = positions.get(nums[k + 1]); // Original index of the (k+1)-th element.
53          
54            // Calculate the distance 'd' considering the elements already accounted for in the BIT.
55            long d = j - i - (bit.query(j + 1) - bit.query(i + 1));
56          
57            // Update the answer with the calculated distance 'd' and additional cost if 'i' is greater than 'j'.
58            answer += d + (n - k) * (i > j ? 1 : 0);
59          
60            // Update the BIT to account for the processed element at position 'i'.
61            bit.update(i + 1, 1);
62        }
63      
64        // Return the final answer.
65        return answer;
66    }
67}
68

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5using namespace std;
6
7// Class to represent a Binary Indexed Tree (also known as a Fenwick Tree)
8class BinaryIndexedTree {
9public:
10    // Constructor initializes the tree with size `size`
11    explicit BinaryIndexedTree(int size)
12        : n(size)
13        , tree(size + 1, 0) {}
14
15    // Updates the tree at position `index` with value `delta`
16    void update(int index, int delta) {
17        while (index <= n) {
18            tree[index] += delta;
19            index += index & -index;
20        }
21    }
22
23    // Queries the cumulative sum up to and including position `index`
24    int query(int index) {
25        int sum = 0;
26        while (index > 0) {
27            sum += tree[index];
28            index -= index & -index;
29        }
30        return sum;
31    }
32
33private:
34    int n;                 // size of the array represented by the tree
35    vector<int> tree;      // internal representation of the tree
36};
37
38// Solution class containing method to count operations to empty an array
39class Solution {
40public:
41    long long countOperationsToEmptyArray(vector<int>& nums) {
42        unordered_map<int, int> valueToIndex;
43        int size = nums.size();
44        // Store the original indices of array elements
45        for (int i = 0; i < size; ++i) {
46            valueToIndex[nums[i]] = i;
47        }
48        // Sort the array to operate in non-decreasing order
49        sort(nums.begin(), nums.end());
50      
51        BinaryIndexedTree bit(size);
52      
53        // Calculate number of operations for the first element
54        long long operationsCount = valueToIndex[nums[0]] + 1;
55        for (int k = 0; k < size - 1; ++k) {
56            int currentIndex = valueToIndex[nums[k]];
57            int nextIndex = valueToIndex[nums[k + 1]];
58            // Calculate distance between currentIndex and nextIndex, accounting for updates
59            long long dist = nextIndex - currentIndex - (bit.query(nextIndex + 1) - bit.query(currentIndex + 1));
60            operationsCount += dist + (size - k) * static_cast<int>(currentIndex > nextIndex);
61            // Update the tree at position currentIndex + 1
62            bit.update(currentIndex + 1, 1);
63        }
64        return operationsCount;
65    }
66};
67

1// Declare global variables to replace class properties
2let treeSize: number;
3let treeArray: number[];
4
5// Initializes the data structures for a binary indexed tree.
6function initializeBinaryIndexedTree( n: number): void {
7    treeSize = n;
8    treeArray = Array( n + 1).fill(0);
9}
10
11// Updates the binary indexed tree with a value at a specific index.
12// x: the index to update
13// v: the value to add
14function update( x: number, v: number): void {
15    while ( x <= treeSize) {
16        treeArray[ x] += v;
17        x += x & -x; // Traverse upwards by the internal binary representation
18    }
19}
20
21// Queries the cumulative frequency up to a given index.
22// x: the index up to which the cumulative sum should be computed
23function query( x: number): number {
24    let sum = 0;
25    while ( x > 0) {
26        sum += treeArray[ x];
27        x -= x & -x; // Traverse downwards by the internal binary representation
28    }
29    return sum;
30}
31
32// Computes the number of operations required to make the array empty,
33// given that the ith operation will remove nums[ i] or its current value.
34// nums: Array of numbers
35function countOperationsToEmptyArray( nums: number[]): number {
36    const positions: Map<number, number> = new Map();
37    const n = nums.length;
38
39    // Store the original positions of the elements
40    for ( let i = 0; i < n; ++i) {
41        positions.set( nums[ i], i);
42    }
43
44    // Sort the array
45    nums.sort((a, b) => a - b);
46
47    // Initialize the binary indexed tree
48    initializeBinaryIndexedTree( n);
49
50    // Start the operations count with the distance of the first element
51    let operationsCount = positions.get(nums[0])! + 1;
52
53    // Compute the number of operations required
54    for ( let k = 0; k < n - 1; ++k) {
55        const currentPosition = positions.get( nums[ k])!;
56        const nextPosition = positions.get( nums[ k + 1])!;
57
58        // Calculate the distance adjusted for the updates made in the tree
59        let distance = nextPosition - currentPosition - ( query( nextPosition + 1) - query( currentPosition + 1));
60      
61        // If the next position is before the current one, loop around the array
62        if ( currentPosition > nextPosition) {
63            distance += n - k;
64        }
65
66        // Increment the operation count by the corrected distance
67        operationsCount += distance;
68      
69        // Update the tree with the current position processed
70        update( currentPosition + 1, 1);
71    }
72    return operationsCount;
73}
74

Time and Space Complexity

The time complexity of the code is primarily governed by three factors: the sorting of the nums array, the operations in the SortedList, and the loop that iterates over pairwise(nums).

The sorting of the nums array at the beginning takes O(n log n) time, where n is the number of elements in the nums.
The SortedList operations including sl.bisect() and sl.add() inside the loop each have O(log n) complexity, as SortedList maintains a sorted list efficiently. In the worst case, sl.bisect() is called twice for each of the n-1 iterations of the loop (since pairwise() would yield n-1 pairs given n elements), and sl.add() is called once per iteration. This contributes (2 * (n - 1) + (n - 1)) * O(log n), which simplifies to O(n log n).
The loop over pairwise(nums) executes n-1 times because pairwise will generate a pair for each adjacent elements, leading to n-1 pairs. The remaining operations inside the loop have a constant time complexity.

Thus, combining these factors, we derive the total time complexity to be O(n log n).

The space complexity is influenced by the additional data structures used which are pos, the SortedList sl, and the sorted nums. Each of these data structures holds ‘n’ elements at most. Hence the overall space complexity is O(n) because the space used grows linearly with the size of nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know