2009. Minimum Number of Operations to Make Array Continuous
Problem Description
The problem presents an integer array nums
. The goal is to make the given array nums
continuous by performing a certain operation. The operation consists of replacing any element in nums
with any integer. An array is defined as continuous if it satisfies the following two conditions:
- All elements in the array are unique.
- The difference between the maximum element and the minimum element in the array is equal to the length of the array minus one.
The requirement is to return the minimum number of operations needed to make the array nums
continuous.
Intuition
To find the minimum number of operations to make the nums
array continuous, we use a two-pointer approach. Here's the general intuition behind this approach:
-
Removing Duplicates: Since all numbers must be unique in a continuous array, we first remove duplicates by converting the array to a set and then back to a sorted list.
-
Finding Subarrays with Potential: We iterate through the sorted and deduplicated
nums
to look for subarrays that could potentially be continuous with minimal changes. Each subarray is characterized by a fixed starting point (i
) and a dynamically found endpoint (j
), where the difference between the maximum and minimum element (which is the first and last in the sorted subarray) is not greater than the length of the array minus one. -
Greedy Selection: For each starting point
i
, we increment the endpointj
until the next element would break the continuity criterion. The size of the subarray between pointsi
andj
represents a potential continuous subarray. -
Calculating Operations: For each of these subarrays, we calculate the number of operations needed by subtracting the number of elements in the subarray from the total number of elements in
nums
. The rationale is that elements not in the subarray would need to be replaced to make the entire array continuous. -
Finding the Minimum: As we want the minimum number of operations, we track the smallest number of operations needed throughout the iteration by using the
min()
function, updating theans
variable accordingly.
The loop efficiently finds the largest subarray that can be made continuous without adding any additional elements (since adding elements is not an option as per problem constraints). The remaining elementsāthose not included in this largest subarrayāare the ones that would need to be replaced. The count of these elements gives us the minimum operations required.
Learn more about Binary Search patterns.
Solution Approach
The solution uses a sorted array without duplicates and a sliding window to find the minimum number of operations. The steps involved in the implementation are as follows:
-
Sorting and Deduplication: The input array
nums
is first converted to a set to remove any duplicates since our final array needs to have all unique elements. This set is then converted back into a sorted list to allow for easy identification of subarrays with potential to be continuous. This is important for step 2, the sliding window approach.nums = sorted(set(nums))
-
Initial Variables: The variable
n
stores the length of the original array. The variableans
is initialized ton
, representing the worst-case scenario where all elements need to be replaced. We also initialize a variablej
to 0, which will serve as our sliding windowās endpoint. -
Sliding Window: We then use a sliding window to find the largest subarray where the elements can remain unchanged. To do this, we iterate over the sorted array with a variable
i
that represents the starting point of our subarray.for i, v in enumerate(nums):
Inside the loop,
j
is incremented until the conditionnums[j] - v <= n - 1
is no longer valid. This condition checks whether the subarray starting fromi
up toj
can remain continuous if we were to fill in the numbers betweennums[i]
andnums[j]
.while j < len(nums) and nums[j] - v <= n - 1: j += 1
-
Calculating the Minimum: For each valid subarray, we calculate the number of elements that need to be replaced:
ans = min(ans, n - (j - i))
This calculates how many elements are not included in the largest potential continuous subarray and takes the minimum of the current answer and the number of elements outside the subarray. The difference
n - (j - i)
gives us the number of operations needed to fill in the missing numbers, since we skipped overn - (j - i)
numbers to achieve the lengthn
.
By the end of the loop, ans
contains the minimum number of operations required to make the array continuous, which is then returned.
This implementation efficiently solves the problem using a sorted set for uniqueness and a sliding window to find the best subarray. The selected subarray has the most elements that are already part of a hypothetical continuous array, thus minimizing the required operations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take the array nums = [4, 2, 5, 3, 5, 7, 6]
as an example to illustrate the solution approach.
-
Sorting and Deduplication:
nums = sorted(set(nums)) // nums = [2, 3, 4, 5, 6, 7]
We first remove the duplicate number 5 and then sort the array. The array becomes
[2, 3, 4, 5, 6, 7]
. -
Initial Variables:
n = len(nums) // n = 7 (original array length) ans = n // ans = 7 j = 0
-
Sliding Window: We iterate through the sorted and deduplicated array using a sliding window technique. The sliding window starts at each element
i
innums
and we try to expand the window by increasingj
.a. When
i = 0
(nums[i] = 2
):nums[j] - nums[i] <= n - 1 nums[0] - 2 <= 6 // 0 - 2 <= 6, condition is true, try next nums[1] - 2 <= 6 // 3 - 2 <= 6, condition is true, try next nums[2] - 2 <= 6 // 4 - 2 <= 6, condition is true, try next nums[3] - 2 <= 6 // 5 - 2 <= 6, condition is true, try next nums[4] - 2 <= 6 // 6 - 2 <= 6, condition is true, try next nums[5] - 2 <= 6 // 7 - 2 <= 6, condition is true
At this point, the subarray
[2, 3, 4, 5, 6, 7]
is the largest we can get starting fromi = 0
, without needing addition.We calculate the operations needed for this subarray:
ans = min(ans, n - (j - i)) // ans = min(7, 7 - (5 - 0)) = 2
So, we need to replace 2 elements in the original array to make the subarray from
2 to 7
continuous.b. The loop continues for
i = 1
toi = 5
, with the window size becoming smaller each time because the maximum possible value a continuous array can have also decreases.
By the end of the loop, we find that the minimum number of operations required is 2, which is the case when we consider the subarray [2, 3, 4, 5, 6, 7]
. The two operations would involve replacing the two remaining numbers 4
and 5
(from the original nums
) to get a continuous range that includes the largest possible number of the original elements.
Therefore, the answer for the example array is 2
. This demonstrates how the approach uses a sliding window to minimize the number of operations needed to make the array continuous.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minOperations(self, nums: List[int]) -> int:
5 # Get the length of the original nums list
6 list_length = len(nums)
7
8 # Use a set to eliminate duplicates, then convert back to a sorted list
9 nums = sorted(set(nums))
10
11 # Initialize the minimum number of operations as the length of the list
12 min_ops = list_length
13
14 # Initialize a pointer for the sliding window
15 window_start = 0
16
17 # Iterate through the list using the enumerate function, which provides both index and value
18 for window_end, value in enumerate(nums):
19 # Expand the window while the difference between the current value and the window's start value
20 # is less than the length of the original list
21 while window_start < len(nums) and nums[window_start] - value <= list_length - 1:
22 window_start += 1
23
24 # Update the minimum number of operations required by finding the minimum between
25 # the current min_ops and the operations calculated using the size of the window.
26 # The size of the window is the total number of elements that can be made consecutive by some operations.
27 min_ops = min(min_ops, list_length - (window_start - window_end))
28
29 # Return the minimum number of operations needed to have all integers in nums consecutively
30 return min_ops
31
1import java.util.Arrays;
2
3class Solution {
4 public int minOperations(int[] nums) {
5 // Sort the array to bring duplicates together and ease the operation count process
6 Arrays.sort(nums);
7
8 // Start uniqueNumbers counter at 1 since the first number is always unique
9 int uniqueNumbers = 1;
10
11 // Step through the sorted array and remove duplicates
12 for (int i = 1; i < nums.length; ++i) {
13 if (nums[i] != nums[i - 1]) {
14 nums[uniqueNumbers++] = nums[i];
15 }
16 }
17
18 // Initialize variable to track the minimum number of operations
19 int minOperations = nums.length;
20
21 // Use a sliding window to count the number of operations
22 for (int i = 0, j = 0; i < uniqueNumbers; ++i) {
23 // Expand the window to the right as long as the condition is met
24 while (j < uniqueNumbers && nums[j] - nums[i] <= nums.length - 1) {
25 ++j;
26 }
27 // Calculate the minimum operations needed and store the result
28 minOperations = Math.min(minOperations, nums.length - (j - i));
29 }
30
31 // Return the minimum number of operations found
32 return minOperations;
33 }
34}
35
1#include <vector>
2#include <algorithm> // Required for std::sort and std::unique
3
4class Solution {
5public:
6 int minOperations(std::vector<int>& nums) {
7 // Sort the vector in non-decreasing order
8 std::sort(nums.begin(), nums.end());
9
10 // Remove duplicate elements from the vector
11 int uniqueCount = std::unique(nums.begin(), nums.end()) - nums.begin();
12
13 // Store the total number of elements in the vector
14 int totalCount = nums.size();
15
16 // Initialize the answer to the max possible value, i.e., the total number of elements
17 int minOperations = totalCount;
18
19 // Use two pointers to find the least number of operations needed
20 for (int left = 0, right = 0; left < uniqueCount; ++left) {
21 // Move the right pointer as long as the difference between nums[right] and nums[left]
22 // is less than or equal to the length of the array minus 1
23 while (right < uniqueCount && nums[right] - nums[left] <= totalCount - 1) {
24 ++right;
25 }
26
27 // Calculate the minimum operations needed by subtracting the length of the current
28 // consecutive sequence from the total number of elements
29 minOperations = std::min(minOperations, totalCount - (right - left));
30 }
31
32 // Return the minimum number of operations required
33 return minOperations;
34 }
35};
36
1function minOperations(nums: number[]): number {
2 // Sort the array in non-decreasing order
3 nums.sort((a, b) => a - b);
4
5 // Remove duplicate elements from the array and get the count of unique elements
6 const uniqueElements: number[] = Array.from(new Set(nums));
7 const uniqueCount: number = uniqueElements.length;
8
9 // Store the total number of elements in the array
10 const totalCount: number = nums.length;
11
12 // Initialize the answer to the max possible value, i.e., the total number of elements
13 let minOps: number = totalCount;
14
15 // Use two pointers to find the least number of operations needed
16 for (let left = 0, right = 0; left < uniqueCount; ++left) {
17
18 // Move the right pointer as long as the difference between the unique elements at 'right' and 'left'
19 // is less than or equal to the length of the array minus 1
20 while (right < uniqueCount && uniqueElements[right] - uniqueElements[left] <= totalCount - 1) {
21 ++right;
22 }
23
24 // Calculate the minimum operations needed by subtracting the length of the current
25 // consecutive sequence of unique elements from the total number of elements
26 minOps = Math.min(minOps, totalCount - (right - left));
27 }
28
29 // Return the minimum number of operations required
30 return minOps;
31}
32
Time and Space Complexity
Time Complexity
The time complexity of the given code snippet involves several operations:
-
Sorting the unique elements in the array: This operation has a time complexity of
O(k log k)
, wherek
is the number of unique elements in the array. -
The for-loop runs
k
times, wherek
is the number of unique elements after removing duplicates. -
Inside the for-loop, we have a while-loop; but notice that each element is visited at most once by the while-loop because
j
only increases. This implies the while-loop total times through all for-loop iterations isO(k)
.
Combining these complexities, we have a total time complexity of O(k log k + k)
, which simplifies to O(k log k)
because k log k
will dominate for larger k
.
Space Complexity
The space complexity is determined by:
-
Storing the sorted unique elements, which takes
O(k)
space. -
Miscellaneous variables (
ans
,j
,n
), which use constant spaceO(1)
.
Hence, the total space complexity is O(k)
for storing the unique elements set. Note that k
here represents the count of unique elements in the original nums
list.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!