You are given a 0-indexed integer array nums
. In one step, remove all elements nums[i]
where nums[i - 1] > nums[i]
for all 0 < i < nums.length
.
Return the number of steps performed until nums
becomes a non-decreasing array.
For example:
nums = [5,3,4,4,7,3,6,11,8,5,11]
should return 3
.
Explanation:
[5,**3**,4,4,7,**3**,6,11,**8**,**5**,11]
becomes [5,4,4,7,6,11,11]
[5,**4**,4,7,**6**,11,11]
becomes [5,4,7,11,11]
[5,**4**,7,11,11]
becomes [5,7,11,11]
[5,7,11,11]
is a non-decreasing array. Therefore, we return 3.nums = [4,5,7,7,13]
should return 0
Explanation: nums
is already a non-decreasing array. Therefore, we return 0.
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
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:
Let's say we have a list of numbers and we want to make them go from smallest to largest, left to right. The brute force approach is to try every single possible thing we could change about the numbers until we find one that works. It's like trying every combination of locks on a safe until it opens.
Here's how the algorithm would work step-by-step:
def steps_to_make_array_non_decreasing_brute_force(numbers):
minimum_changes = float('inf')
def calculate_changes(current_numbers):
changes = 0
for index in range(len(current_numbers) - 1):
if current_numbers[index] > current_numbers[index + 1]:
#We need to consider two possibilities, increasing the right or decreasing the left.
increase_right = list(current_numbers)
increase_right[index + 1] = current_numbers[index]
changes_increase = abs(current_numbers[index + 1] - increase_right[index + 1])
decrease_left = list(current_numbers)
decrease_left[index] = current_numbers[index + 1]
changes_decrease = abs(current_numbers[index] - decrease_left[index])
if changes_increase <= changes_decrease:
current_numbers[index + 1] = current_numbers[index]
changes += changes_increase
else:
current_numbers[index] = current_numbers[index + 1]
changes += changes_decrease
return changes
import itertools
# Generate all possible permutations is not right. The brute force approach is to try increase or decrease.
# The core logic is to try increase or decrease only when current value > next value
number_of_elements = len(numbers)
# Create a list of possible changes to apply.
possible_modifications = []
def find_non_decreasing_count(index, current_numbers, changes_count):
nonlocal minimum_changes
if index == number_of_elements -1 :
minimum_changes = min(minimum_changes, changes_count)
return
if current_numbers[index] <= current_numbers[index+1]:
find_non_decreasing_count(index+1, current_numbers, changes_count)
return
# Two options, increase the right value or decrease the left
increase_right_numbers = list(current_numbers)
increase_right_numbers[index+1] = current_numbers[index]
increase_right_changes_count = changes_count + abs(current_numbers[index+1] - current_numbers[index])
find_non_decreasing_count(index+1, increase_right_numbers, increase_right_changes_count)
decrease_left_numbers = list(current_numbers)
decrease_left_numbers[index] = current_numbers[index+1]
# Decrement the left element
decrease_left_changes_count = changes_count + abs(current_numbers[index] - current_numbers[index+1])
find_non_decreasing_count(index+1, decrease_left_numbers, decrease_left_changes_count)
find_non_decreasing_count(0, numbers, 0)
return minimum_changes
We want to find the minimum number of steps to make an array non-decreasing. The key idea is to use a stack to keep track of potential elements that might need to be removed, and to understand when an element definitely needs to be removed to maintain the non-decreasing property.
Here's how the algorithm would work step-by-step:
def steps_to_make_array_non_decreasing(numbers):
stack = []
max_steps = 0
for number in numbers:
steps = 0
# Remove elements that violate non-decreasing order
while stack and stack[-1][0] > number:
steps = max(steps, stack[-1][1] + 1)
stack.pop()
stack.append((number, steps))
max_steps = max(max_steps, steps)
return max_steps
Case | How to Handle |
---|---|
Null or empty input array | Return 0 if the input array is null or empty as no operations are needed. |
Array with only one element | Return 0 since a single-element array is already non-decreasing. |
Array already sorted in non-decreasing order | Return 0 as no steps are required to make it non-decreasing. |
Array sorted in strictly decreasing order | Requires maximum number of steps, should still be handled efficiently by the algorithm. |
Array with all elements equal | Return 0 as it is already non-decreasing. |
Array containing very large numbers (potential for integer overflow) | Use appropriate data types (e.g., long) to prevent overflow during calculations when modifying elements, or modular arithmetic when the prompt specifies a module. |
Large input array (performance considerations) | Ensure the algorithm has optimal time complexity, such as O(n) or O(n log n), to handle large inputs efficiently; avoid O(n^2) or higher complexities. |
Array containing negative numbers and zeros | The algorithm should correctly handle negative numbers and zeros without any special modifications, assuming the comparison logic uses <=. |