Minimum Number of Operations to Make Array Continuous

Minimum Number of Operations to Make Array Continuous - 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 nums are unique.
The difference between the maximum element and the minimum element in nums equals nums.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.

Input & Output

Example 1 — Already Continuous

$ Input: nums = [4,2,5,3]

› Output: 0

💡 Note: The array contains unique elements [2,3,4,5] and max-min = 5-2 = 3 = length-1. Already continuous, so 0 operations needed.

Example 2 — Need Replacements

$ Input: nums = [1,2,3,5,6]

› Output: 1

💡 Note: We can keep 4 elements in range [2,5]: [2,3,5] plus one replacement. Or keep [1,2,3] plus two replacements. Best is 1 replacement.

Example 3 — Many Duplicates

$ Input: nums = [1,10,100,1000]

› Output: 3

💡 Note: Only 1 element can be kept in any continuous range of length 4. Need to replace 3 elements.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [4,2,5,3] with length 4, need max-min = 3

Check Conditions

All unique? Yes. Range = 5-2 = 3 = length-1? Yes

Result

Already continuous, 0 operations needed

Key Takeaway

🎯 Key Insight: Keep maximum existing unique elements within any valid continuous range of length n

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to find the maximum number of unique elements that can fit within any continuous range of length n. We sort unique elements and use a sliding window to efficiently find the optimal range. Best approach is sliding window with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Starting Points	O(n²)	O(n)	Try every possible starting value and count operations needed for each continuous sequence
Sliding Window - Optimal Range Finding	O(n log n)	O(n)	Sort unique elements and use sliding window to find the maximum number of elements that fit in any valid range

Brute Force - Try All Starting Points — Algorithm Steps

Remove duplicates from original array
Try each unique element as potential starting point
For each start, count how many original elements fall in range [start, start + n - 1]
Return n minus the maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Remove Duplicates

Get unique elements from original array

Try Each Start

For each unique element, count how many fit in range [start, start+n-1]

Find Maximum

Keep track of maximum elements that can be preserved

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    // Create array of unique numbers
    int* unique = (int*)malloc(n * sizeof(int));
    int uniqueCount = 0;
    
    // Find unique elements
    for (int i = 0; i < n; i++) {
        int isUnique = 1;
        for (int j = 0; j < uniqueCount; j++) {
            if (unique[j] == nums[i]) {
                isUnique = 0;
                break;
            }
        }
        if (isUnique) {
            unique[uniqueCount++] = nums[i];
        }
    }
    
    int maxKeep = 0;
    for (int i = 0; i < uniqueCount; i++) {
        int start = unique[i];
        int count = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (unique[j] >= start && unique[j] <= start + n - 1) {
                count++;
            }
        }
        if (count > maxKeep) {
            maxKeep = count;
        }
    }
    
    free(unique);
    return n - maxKeep;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of the n unique elements, we iterate through all elements to count how many fit in the range

⚠ Quadratic Growth

Space Complexity

O(n)

Hash set to store unique elements and array to store them

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Starting Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler