Minimum Number of Operations to Make Array Continuous solution and explanation
Google
9 more videos on this problem
Minimum Number of Operations to Make Array Continuous - Leetcode 2009 - PythonNeetCodeIO · 18:31 · 21K views
Minimum Number of Operations to Make Array Continuous | Brute Force | Optimal | Leetcode - 2009codestorywithMIK · 35:18 · 9K views
Minimum Number of Operations to Make Array Continuous | LeetCode 2009 | Fully Explained with CodeSuperCode · 16:24 · 5K views
LeetCode 2009. Minimum Number of Operations to Make Array ContinuousHappy Coding · 14:18 · 5K views
Minimum Number of Operations to Make Array Continuous | Leetcode 2009Ayushi Sharma · 31:11 · 2K views
LeetCode 2009 Minimum Number of Operations to Make Array ContinuousJeevan Kumar - Cracckify · 14:12 · 1K views
2009. Minimum Number of Operations to Make Array Continuous (Leetcode Hard)Programming Live with Larry · 15:32 · 1K views
Daily Leetcode #1288: Oct 10, 2023 - 2009. Minimum Number of Operations to Make Array ContinuousProgramming Live with Larry · 10:33 · 565 views
Minimum Number of Operations to Make Array Continuous - JAVA - 2009 Leetcode Hard in 7 minsLeet Logics · 5:01 · 414 views
LeetCode 2009:✅ Minimum Number of Operations to Make Array ContinuousThe algorithm Architect · 13:53 · 377 views
The problem
You are given an integer array nums. In one operation, you can replace any element in nums with any integer.
nums is considered continuous if both of the following conditions are fulfilled:
- All elements in
numsare unique. - The difference between the maximum element and the minimum element in
numsequalsnums.length - 1.
For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.
Return the minimum number of operations to make nums continuous.
Example 1:
Input: nums = [4,2,5,3] Output: 0 Explanation: nums is already continuous.
Example 2:
Input: nums = [1,2,3,5,6] Output: 1 Explanation: One possible solution is to change the last element to 4. The resulting array is [1,2,3,5,4], which is continuous.
Example 3:
Input: nums = [1,10,100,1000] Output: 3 Explanation: One possible solution is to: - Change the second element to 2. - Change the third element to 3. - Change the fourth element to 4. The resulting array is [1,2,3,4], which is continuous.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an integer array and can replace any element with any integer. The goal is to make the array continuous: all elements must be unique and the difference between the maximum and minimum values must be n - 1. The task is to compute the minimum number of replacements required.
Approach 1: Sort + Sliding Window (O(n log n) time, O(n) space)
The key observation: a valid continuous array of length n must fit inside a value range [x, x + n - 1]. First remove duplicates by converting the array into a sorted unique list. Then use a sliding window over this sorted list. For each left index l, expand the right pointer r while nums[r] - nums[l] <= n - 1. This window represents values that can already fit inside a valid continuous range without replacement. The number of elements you keep is the window size, so the number of operations needed is n - window_size. Track the maximum window size across the array. Sorting costs O(n log n), and the two-pointer scan is linear.
This approach works because the best strategy is always to preserve the largest set of numbers that already fit within a valid continuous interval. The array is sorted once, and the window ensures you never revisit elements.
Approach 2: Binary Search with a Set (O(n log n) time, O(n) space)
Another way to think about the problem is to treat each number as a possible start of a continuous range. Insert all values into a hash table or set to remove duplicates, then sort the unique values. For every index i, compute the maximum allowed value nums[i] + n - 1. Use binary search to find the rightmost index whose value fits within this limit. The count of valid elements is right - i + 1, and the required operations become n - count. Iterate over all starting points and keep the minimum.
This approach explicitly searches the farthest element that still fits inside the allowed range. The complexity stays O(n log n) due to sorting and repeated binary searches.
Recommended for interviews: The Sort + Sliding Window approach is the one most interviewers expect. It shows you recognize the continuous-range constraint and can convert the problem into a two-pointer window over sorted unique values. Mentioning the binary search variant demonstrates deeper understanding of range queries, but the sliding window solution is usually cleaner and easier to implement under time pressure.
Approach 1: Sort and Sliding Window
This approach involves sorting the array and then using a sliding window technique to identify the minimal range that can lead to a continuous array by transformation.
Steps:
- Sort the array to easily determine the valid range.
- Use a two-pointer sliding window approach to maintain unique elements within a feasible range of size
nums.length - 1. - The minimal number of elements to be replaced will be equal to the original array size minus the maximal length of this window.
def min_operations(nums):
nums = sorted(set(nums))
n = len(nums)
max_nums_len = len(nums)
i, j, max_valid_count = 0, 0, 0
while j < max_nums_len:
while j < max_nums_len and nums[j] - nums[i] < n:
j += 1
max_valid_count = max(max_valid_count, j - i)
i += 1
return n - max_valid_count
# Example usage:
print(min_operations([4, 2, 5, 3])) # Output: 0
print(min_operations([1, 2, 3, 5, 6])) # Output: 1
print(min_operations([1, 10, 100, 1000])) # Output: 3#include <bits/stdc++.h>
using namespace std;
int minOperations(vector<int>& nums) {
set<int> unique_nums(nums.begin(), nums.end());
vector<int> sorted_nums(unique_nums.begin(), unique_nums.end());
int n = nums.size();
int max_valid_count = 0;
for (int i = 0, j = 0; j < sorted_nums.size(); ++j) {
while (sorted_nums[j] - sorted_nums[i] >= n) {
++i;
}
max_valid_count = max(max_valid_count, j - i + 1);
}
return n - max_valid_count;
}
// Example usage
int main() {
vector<int> nums1 = {4, 2, 5, 3};
vector<int> nums2 = {1, 2, 3, 5, 6};
vector<int> nums3 = {1, 10, 100, 1000};
cout << minOperations(nums1) << endl; // Output: 0
cout << minOperations(nums2) << endl; // Output: 1
cout << minOperations(nums3) << endl; // Output: 3
return 0;
}This Python solution first creates a sorted and deduplicated list of nums. It uses two pointers to traverse the sorted list, maintaining the largest subarray where the elements fulfill the necessary range condition. The difference between the original size and this subarray's size gives the answer.
Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for the extra space used by the set and sorted list.
Approach 2: Binary Search with a Set
This approach optimally uses binary search for potentially faster window limits:
- Sort and deduplicate the array.
- Use binary search to maintain the longest subarray fulfilling the difference constraint.
- Calculate necessary operations from this subarray size.
import java.util.*;
public class ContinuousArray {
public static int minOperations(int[] nums) {
Set<Integer> uniqueNumsSet = new HashSet<>();
for (int num : nums) {
uniqueNumsSet.add(num);
}
List<Integer> uniqueNums = new ArrayList<>(uniqueNumsSet);
Collections.sort(uniqueNums);
int n = nums.length;
int maxValidCount = 0;
for (int i = 0; i < uniqueNums.size(); i++) {
int end = uniqueNums.get(i) + n - 1;
int j = Collections.binarySearch(uniqueNums, end);
if (j < 0) {
j = -j - 1;
} else {
j += 1;
}
maxValidCount = Math.max(maxValidCount, j - i);
}
return n - maxValidCount;
}
public static void main(String[] args) {
int[] nums1 = {4, 2, 5, 3};
int[] nums2 = {1, 2, 3, 5, 6};
int[] nums3 = {1, 10, 100, 1000};
System.out.println(minOperations(nums1)); // Output: 0
System.out.println(minOperations(nums2)); // Output: 1
System.out.println(minOperations(nums3)); // Output: 3
}
}function minOperations(nums) {
nums = Array.from(new Set(nums)).sort((a, b) => a - b);
const n = nums.length;
let maxValidCount = 0;
for (let i = 0; i < n; ++i) {
let j = i;
while (j < n && nums[j] - nums[i] <= n - 1) {
++j;
}
maxValidCount = Math.max(maxValidCount, j - i);
}
return nums.length - maxValidCount;
}
// Example usage
console.log(minOperations([4, 2, 5, 3])); // Output: 0
console.log(minOperations([1, 2, 3, 5, 6])); // Output: 1
console.log(minOperations([1, 10, 100, 1000])); // Output: 3This Java solution first constructs a deduplicated sorted list and utilizes binary search to determine the longest valid subarray within constraints, minimizing transformation operations needed.
Time Complexity: O(N log N) due to sorting and binary search. Space Complexity: O(N) for the intermediary data structure created.
Approach 3: Sorting + Deduplication + Binary Search
First, we sort the array and remove duplicates.
Then, we traverse the array, enumerating the current element nums[i] as the minimum value of the consecutive array. We use binary search to find the first position j that is greater than nums[i] + n - 1. Then, j-i is the length of the consecutive array when the current element is the minimum value. We update the answer, i.e., ans = min(ans, n - (j - i)).
Finally, we return ans.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.
function minOperations(nums: number[]): number {
const n = nums.length;
nums.sort((a, b) => a - b);
let m = 1;
for (let i = 1; i < n; ++i) {
if (nums[i] !== nums[i - 1]) {
nums[m++] = nums[i];
}
}
let ans = n;
for (let i = 0; i < m; ++i) {
const j = search(nums, nums[i] + n - 1, i, m);
ans = Math.min(ans, n - (j - i));
}
return ans;
}
function search(nums: number[], x: number, left: number, right: number): number {
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func minOperations(nums []int) int {
sort.Ints(nums)
n := len(nums)
m := 1
for i := 1; i < n; i++ {
if nums[i] != nums[i-1] {
nums[m] = nums[i]
m++
}
}
ans := n
for i := 0; i < m; i++ {
j := sort.Search(m, func(k int) bool { return nums[k] > nums[i]+n-1 })
ans = min(ans, n-(j-i))
}
return ans
}use std::collections::BTreeSet;
impl Solution {
#[allow(dead_code)]
pub fn min_operations(nums: Vec<i32>) -> i32 {
let n = nums.len();
let nums = nums.into_iter().collect::<BTreeSet<i32>>();
let m = nums.len();
let nums = nums.into_iter().collect::<Vec<i32>>();
let mut ans = n;
for i in 0..m {
let j = match nums.binary_search(&(nums[i] + (n as i32))) {
Ok(idx) => idx,
Err(idx) => idx,
};
ans = std::cmp::min(ans, n - (j - i));
}
ans as i32
}
}Approach 4: Sorting + Deduplication + Two Pointers
Similar to Solution 1, we first sort the array and remove duplicates.
Then, we traverse the array, enumerating the current element nums[i] as the minimum value of the consecutive array. We use two pointers to find the first position j that is greater than nums[i] + n - 1. Then, j-i is the length of the consecutive array when the current element is the minimum value. We update the answer, i.e., ans = min(ans, n - (j - i)).
Finally, we return ans.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.
function minOperations(nums: number[]): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let m = 1;
for (let i = 1; i < n; i++) {
if (nums[i] !== nums[i - 1]) {
nums[m] = nums[i];
m++;
}
}
let ans = n;
for (let i = 0, j = 0; i < m; i++) {
while (j < m && nums[j] - nums[i] <= n - 1) {
j++;
}
ans = Math.min(ans, n - (j - i));
}
return ans;
}func minOperations(nums []int) int {
sort.Ints(nums)
n := len(nums)
m := 1
for i := 1; i < n; i++ {
if nums[i] != nums[i-1] {
nums[m] = nums[i]
m++
}
}
ans := n
for i, j := 0, 0; i < m; i++ {
for j < m && nums[j]-nums[i] <= n-1 {
j++
}
ans = min(ans, n-(j-i))
}
return ans
}impl Solution {
pub fn min_operations(mut nums: Vec<i32>) -> i32 {
nums.sort();
let n = nums.len();
if n == 0 {
return 0;
}
let mut m = 1usize;
for i in 1..n {
if nums[i] != nums[i - 1] {
nums[m] = nums[i];
m += 1;
}
}
let mut ans = n as i32;
let mut j = 0usize;
for i in 0..m {
while j < m && nums[j] - nums[i] <= n as i32 - 1 {
j += 1;
}
ans = ans.min(n as i32 - (j as i32 - i as i32));
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort and Sliding Window | Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for the extra space used by the set and sorted list. |
| Binary Search with a Set | Time Complexity: O(N log N) due to sorting and binary search. Space Complexity: O(N) for the intermediary data structure created. |
| Sorting + Deduplication + Binary Search | – |
| Sorting + Deduplication + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Sliding Window | O(n log n) | O(n) | Best general solution; clean two-pointer logic after sorting unique values |
| Binary Search with Set | O(n log n) | O(n) | Useful when framing the problem as repeated range queries on a sorted array |
Frequently asked questions
Is Minimum Number of Operations to Make Array Continuous easy or hard?
The problem is classified as Hard on LeetCode because the key insight is not obvious. Recognizing that the array must fit within a value range of length n and converting the task into a sliding window over sorted unique values requires strong algorithmic intuition.
Minimum Number of Operations to Make Array Continuous Python/Java solution
Python and C++ implementations typically use the sorting plus sliding window technique. Java and JavaScript solutions often combine a set for deduplication with binary search on the sorted unique array. Both implementations achieve O(n log n) time complexity.
How to solve Minimum Number of Operations to Make Array Continuous in O(n)?
A strict O(n) solution is generally not achievable because the array must be sorted to reason about value ranges. The closest optimal approach is O(n log n) using sorting followed by a sliding window that checks which elements fit within a valid continuous interval of size n.
What is the best approach for Minimum Number of Operations to Make Array Continuous?
The best approach is sorting the array, removing duplicates, and using a sliding window to find the largest group of numbers that already fits inside a range of length n. The number of required operations becomes n minus the size of that window. This method runs in O(n log n) time due to sorting and O(n) space for storing unique elements.
Is Minimum Number of Operations to Make Array Continuous asked at Google/Amazon/Meta?
This style of problem appears frequently in interviews at companies like Google, Amazon, and Meta because it combines multiple concepts: sorting, sliding window, and reasoning about numeric ranges. Variants of range compression and minimal modification problems are common in high-level algorithm interviews.
What data structure is used in Minimum Number of Operations to Make Array Continuous?
The typical solution uses arrays with sorting, a hash set to remove duplicates, and a sliding window implemented with two pointers. Some variations also use binary search on the sorted array to locate the farthest value within the allowed range.
What is the time complexity of Minimum Number of Operations to Make Array Continuous?
The optimal solution runs in O(n log n) time. Sorting the array dominates the complexity, while the sliding window scan is linear O(n). Space complexity is O(n) because duplicates are removed using a set or a new list of unique values.