You may recall that an array arr
is a mountain array if and only if:
arr.length >= 3
i
(0-indexed) with 0 < i < arr.length - 1
such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given an integer array nums
, return the minimum number of elements to remove to make nums
a mountain array.
For example:
nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1]
.What is the most efficient solution, and what are the time and space complexities?
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:
The brute force method for finding the fewest removals to make a mountain involves trying all possible combinations of keeping some numbers and removing others. We check each of these combinations to see if it forms a valid mountain, and then keep track of the smallest number of removals required.
Here's how the algorithm would work step-by-step:
def minimum_mountain_removals_brute_force(numbers):
list_length = len(numbers)
minimum_removals = list_length
for i in range(1 << list_length):
selected_numbers = []
for j in range(list_length):
if (i >> j) & 1:
selected_numbers.append(numbers[j])
selected_length = len(selected_numbers)
if selected_length >= 3:
# Check if it forms a mountain
peak_found = False
peak_index = -1
for k in range(1, selected_length - 1):
if selected_numbers[k] > selected_numbers[k - 1] and \
selected_numbers[k] > selected_numbers[k + 1]:
peak_found = True
peak_index = k
break
if peak_found:
is_mountain = True
# Verify increasing sequence before peak
for k in range(1, peak_index + 1):
if selected_numbers[k] <= selected_numbers[k - 1]:
is_mountain = False
break
# Verify decreasing sequence after peak
if is_mountain:
for k in range(peak_index + 1, selected_length):
if selected_numbers[k] >= selected_numbers[k - 1]:
is_mountain = False
break
if is_mountain:
#Calculate the number of removals
removals = list_length - selected_length
minimum_removals = min(minimum_removals, removals)
return minimum_removals
To find the fewest removals to form a mountain, we'll find the longest mountain-shaped sequence that already exists within the given sequence. Then, we'll remove everything else. The trick is to efficiently find this longest mountain.
Here's how the algorithm would work step-by-step:
def minimum_number_of_removals_to_make_mountain_array(number_array):
array_length = len(number_array)
longest_increasing_sequence = [1] * array_length
longest_decreasing_sequence = [1] * array_length
for i in range(1, array_length):
for j in range(i):
if number_array[i] > number_array[j]:
longest_increasing_sequence[i] = max(longest_increasing_sequence[i], longest_increasing_sequence[j] + 1)
# Calculate decreasing sequences from right to left.
for i in range(array_length - 2, -1, -1):
for j in range(array_length - 1, i, -1):
if number_array[i] > number_array[j]:
longest_decreasing_sequence[i] = max(longest_decreasing_sequence[i], longest_decreasing_sequence[j] + 1)
maximum_mountain_length = 0
# Find the longest mountain.
for i in range(array_length):
if longest_increasing_sequence[i] > 1 and longest_decreasing_sequence[i] > 1:
maximum_mountain_length = max(maximum_mountain_length, longest_increasing_sequence[i] + longest_decreasing_sequence[i] - 1)
# The result is the difference between the array length and mountain length.
return array_length - maximum_mountain_length
Case | How to Handle |
---|---|
Empty or null input array | Return 0 since an empty array is trivially a mountain (or can be considered such after 0 removals). |
Array with size 1 or 2 | Return the size of the array, as a mountain array needs at least one increasing and one decreasing element to be valid. |
Array with all identical elements | Return array.length - 1 because you need to remove all but one element to make it technically a mountain, assuming a single element is considered a valid trivial mountain. |
Array already a valid mountain array | Return 0, because no removals are needed. |
Array sorted in strictly increasing order | Return array.length - 1, keep the last element as the 'peak'. |
Array sorted in strictly decreasing order | Return array.length - 1, keep the first element as the 'peak'. |
Array with a very large number of elements | The longest increasing subsequence algorithm must be efficient (O(n log n)) to avoid time limit exceeding errors; dynamic programming alone may be too slow. |
Integer overflow when calculating LIS lengths for very large input arrays | The LIS calculations themselves won't overflow given problem constraints, but be mindful of memory usage as LIS arrays may be large. |