Taro Logo

Make Array Empty

#20 Most AskedHard
0 views
Topics:
ArraysGreedy Algorithms

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.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Does moving the front value to the back count as its own operation, separate from removing the front value?
  2. Are duplicate values allowed?
  3. Is a value removed only when it is the smallest remaining value and it sits at the front?
  4. Is the answer the number of operations, rather than the sequence of removed values?
  5. Should an empty input produce a count of zero?

Brute Force Solution

Approach

While values remain, one pass removes every copy of the current minimum and rebuilds the rest in circular order, starting just after the first occurrence of that minimum. Each pass counts as one operation. The returned number is how many passes were required.

Here's how the algorithm would work step-by-step:

  1. While any values remain, add one to the operation count.
  2. Find the smallest value still present.
  3. Find the first position where that smallest value occurs.
  4. Rebuild the sequence by walking forward from that position, wrapping around to the front, and skipping every copy of the minimum.
  5. Replace the current sequence with that rebuilt sequence.
  6. Return the operation count when the sequence is empty.

Code Implementation

def make_array_empty_brute_force(input_numbers):
    working_list_of_numbers = list(input_numbers)
    number_of_steps = 0

    # Continue the process until the list of numbers becomes empty.
    while working_list_of_numbers:
        number_of_steps += 1

        # Find the smallest number currently in the list to determine what to remove next.
        current_smallest_value = min(working_list_of_numbers)

        remaining_numbers_after_removal = []
        start_index_of_smallest_found = -1

        # First pass: find the first occurrence of the smallest value to establish the wrap-around point.
        for index, number in enumerate(working_list_of_numbers):
            if number == current_smallest_value:
                start_index_of_smallest_found = index
                break
        
        # Second pass: rebuild the list by skipping all copies of the smallest value.
        # This pass simulates the circular traversal and removal in one operation.
        for index in range(len(working_list_of_numbers)):
            current_index = (start_index_of_smallest_found + index) % len(working_list_of_numbers)
            if working_list_of_numbers[current_index] != current_smallest_value:
                remaining_numbers_after_removal.append(working_list_of_numbers[current_index])
        
        working_list_of_numbers = remaining_numbers_after_removal

    return number_of_steps

Big(O) Analysis

Time Complexity
O(n^2) – Let n be the number of values. Each pass scans the remaining values to find the minimum and then scans them again to rebuild the rest. A pass removes at least one value, so there are at most n passes. The scans over a shrinking sequence still add up to O(n^2). The total time is O(n^2).
Space Complexity
O(n) – Let n be the number of values. The rebuilt sequence holds the values that were not removed, which is at most n. The previous sequence is discarded after the replacement. No extra table grows with the number of passes. The extra space is O(n).

Optimal Solution

Approach

Each value keeps the position of its last occurrence, and the values are then sorted. A wrap is counted whenever the next value's position is not strictly after the previous position, starting from a position before the beginning. The result starts at the length, adds the length once for every wrap, and subtracts one for every neighboring pair of those positions that increases.

Here's how the algorithm would work step-by-step:

  1. If there are no values, return zero.
  2. Record the last position of each distinct value.
  3. Sort the distinct values from smallest to largest.
  4. Walk those values and count a wrap whenever the next position is less than or equal to the previous one, starting the previous position before the beginning.
  5. Start the result at the length and add the length once for every wrap.
  6. Sort the recorded positions and subtract one for each neighboring pair that strictly increases.
  7. Return that result.

Code Implementation

def make_array_empty(numbers):
    number_to_position_map = {value: index for index, value in enumerate(numbers)}

    sorted_unique_numbers = sorted(number_to_position_map.keys())

    # The total operations start with the initial size of the array, for the first pass.
    total_operations = len(numbers)
    wrap_around_count = 0
    previous_position = -1

    for current_number in sorted_unique_numbers:
        current_position = number_to_position_map[current_number]

        # A smaller position means we've passed it in the current pass and must 'wrap around'.
        if current_position < previous_position:
            wrap_around_count += 1
        
        previous_position = current_position
    
    # Each wrap-around corresponds to a full pass over the *remaining* elements at that time.
    total_operations += wrap_around_count * len(numbers)
    
    # The operations are simulated by sorting positions, so we subtract to find the true cost.
    sorted_positions = sorted(number_to_position_map.values())
    for index in range(1, len(sorted_positions)):
        if sorted_positions[index] > sorted_positions[index - 1]:
            total_operations -= 1

    return total_operations

Big(O) Analysis

Time Complexity
O(n log n) – Let n be the number of values. Recording the last position of each value is a single pass, which is O(n). Sorting the distinct values and sorting their positions are each O(n log n). The wrap walk and the increasing-pair walk are linear in the number of distinct values. The sorts dominate, so the total time is O(n log n).
Space Complexity
O(n) – Let n be the number of values. The position map stores one entry per distinct value, which is at most n. The sorted list of positions has that same length. The wrap count and the running total are single numbers. The extra space is O(n).

Edge Cases

The input has one value
How to Handle:
A single pass removes it, so the direct count is one, and the formula also returns one.
The values are already in increasing order and all distinct
How to Handle:
Each pass removes the front value, so the direct count equals the length.
The smallest value sits at the end
How to Handle:
The direct simulation still uses one pass for that removal, because a pass rebuilds the circle rather than counting each rotation.
The current minimum occurs more than once
How to Handle:
One pass drops every copy of that minimum and keeps the other values in circular order.
The next smallest value sits at an earlier position than the previous one
How to Handle:
The fast formula counts one wrap and adds the length once for that wrap.
0/28 completed