Minimum Operations to Make the Array Alternating

Minimum Operations to Make the Array Alternating - Problem

You are given a 0-indexed array nums consisting of n positive integers. The array nums is called alternating if: nums[i - 2] == nums[i] where 2 <= i <= n - 1. nums[i - 1] != nums[i] where 1 <= i <= n - 1. In one operation you can choose an index i and change nums[i] into any positive integer. Return the minimum number of operations required to make the array alternating. Medium

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

nums[i - 2] == nums[i], where 2 <= i <= n - 1.
nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return the minimum number of operations required to make the array alternating.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Need to make alternating pattern. Even positions (0,2,4) should have same value, odd positions (1,3,5) should have same value, and they must be different. Optimal: change indices 1,3,4 to get [3,2,3,2,3,2]

Example 2 — Already Alternating

$ Input: nums = [1,2,2,2,2]

› Output: 2

💡 Note: Even positions (0,2,4): values [1,2,2]. Odd positions (1,3): values [2,2]. Best choice: Even=2, Odd=1. Change indices 0,1 to get [2,1,2,1,2]

Example 3 — Small Array

$ Input: nums = [1,2]

› Output: 0

💡 Note: Already alternating since nums[0] ≠ nums[1]. No operations needed

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,1,3,2,4,3] - not alternating

Pattern

Even positions must have same value, odd positions must have different value

Output

Minimum operations needed: 3

Key Takeaway

🎯 Key Insight: Split array into even/odd positions, find most frequent values for each group ensuring they differ

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is that an alternating array has two independent groups: even positions and odd positions. Each group must have the same value, and the two groups must have different values. The optimal approach uses frequency counting to find the most frequent values for each group. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Optimization	O(n)	O(n)	Count frequencies of values at even and odd positions, then pick optimal combination
Brute Force	O(n³)	O(n)	Try all possible value combinations for even and odd positions

Frequency Count Optimization — Algorithm Steps

Step 1: Count frequencies for even and odd positions separately
Step 2: Sort values by frequency for each group
Step 3: Pick best combination ensuring even and odd values are different

Visualization

Tap to expand

Step-by-Step Walkthrough

Separate Positions

Count frequencies for even and odd positions

Find Top Values

Get most frequent values for each group

Optimal Choice

Pick best combination with different values

Code -

solution.c — C

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

typedef struct {
    int val;
    int freq;
} pair;

int compare(const void* a, const void* b) {
    return ((pair*)b)->freq - ((pair*)a)->freq;
}

int solution(int* nums, int numsSize) {
    if (numsSize == 1) return 0;
    if (numsSize == 2) return nums[0] != nums[1] ? 0 : 1;
    
    // Count frequencies using simple arrays (assuming values <= 100000)
    int evenCount[100001] = {0};
    int oddCount[100001] = {0};
    int maxVal = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > maxVal) maxVal = nums[i];
        if (i % 2 == 0) {
            evenCount[nums[i]]++;
        } else {
            oddCount[nums[i]]++;
        }
    }
    
    // Convert to arrays of pairs and sort
    pair evenItems[1000], oddItems[1000];
    int evenSize = 0, oddSize = 0;
    
    for (int i = 1; i <= maxVal; i++) {
        if (evenCount[i] > 0) {
            evenItems[evenSize++] = (pair){i, evenCount[i]};
        }
        if (oddCount[i] > 0) {
            oddItems[oddSize++] = (pair){i, oddCount[i]};
        }
    }
    
    qsort(evenItems, evenSize, sizeof(pair), compare);
    qsort(oddItems, oddSize, sizeof(pair), compare);
    
    int evenTotal = 0, oddTotal = 0;
    for (int i = 0; i < evenSize; i++) evenTotal += evenItems[i].freq;
    for (int i = 0; i < oddSize; i++) oddTotal += oddItems[i].freq;
    
    int minOps = INT_MAX;
    
    for (int i = 0; i < evenSize && i < 2; i++) {
        for (int j = 0; j < oddSize && j < 2; j++) {
            if (evenItems[i].val != oddItems[j].val) {
                int ops = (evenTotal - evenItems[i].freq) + (oddTotal - oddItems[j].freq);
                if (ops < minOps) {
                    minOps = ops;
                }
            }
        }
    }
    
    return minOps;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies, then process unique values which is at most O(n)

✓ Linear Growth

Space Complexity

O(n)

Hash maps to store frequency counts for even and odd positions

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 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

Frequency Count Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler