You are given an integer array nums containing distinct numbers, and you can perform the following operations until the array is empty:
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] <= 109nums are distinct.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:
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:
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_stepsEach 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:
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| Case | How to Handle |
|---|---|
| The input has one value | 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 | Each pass removes the front value, so the direct count equals the length. |
| The smallest value sits at the end | 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 | 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 | The fast formula counts one wrap and adds the length once for that wrap. |