Minimum Score by Changing Two Elements - Practice Coding Problems

Minimum Score by Changing Two Elements - Problem

You are given an integer array nums.

The low score of nums is the minimum absolute difference between any two integers.

The high score of nums is the maximum absolute difference between any two integers.

The score of nums is the sum of the high and low scores.

Return the minimum score after changing two elements of nums.

Input & Output

Example 1 — Basic Case

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

› Output: 0

💡 Note: Change nums to [4,4,4]. Low score = 0 (min difference), High score = 0 (max-min), Total = 0+0 = 0

Example 2 — Different Values

$ Input: nums = [1,4,7,8,5]

› Output: 3

💡 Note: Change to [4,4,5,5,5]. Low score = 1 (difference between 4 and 5), High score = 1 (5-4), Total = 1+1 = 2. Actually optimal is changing to get score 3.

Example 3 — Small Array

$ Input: nums = [10,20]

› Output: 0

💡 Note: Change both elements to same value, e.g., [20,20]. Low score = 0, High score = 0, Total = 0

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,4,3] with current low and high scores

Process

Change two elements to minimize total score

Output

Return minimum possible score after changes

Key Takeaway

🎯 Key Insight: Making elements equal or close to equal minimizes both the minimum difference and the range

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is that after sorting, we only need to consider three strategic patterns: removing the two smallest elements, removing the two largest elements, or removing one from each end. The optimal approach sorts first then tries these three cases. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Greedy	O(n log n)	O(1)	Sort array and systematically try optimal element removal patterns
Brute Force	O(n⁴)	O(1)	Try all possible pairs of elements to change
Sort and Strategic Removal	O(n² log n)	O(n)	Sort array first, then try removing extreme elements

Optimized Greedy — Algorithm Steps

Sort the array in ascending order
Try removing first two elements (replace with 3rd element)
Try removing last two elements (replace with 3rd from end)
Try removing first and last element
Return minimum score among all options

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Arrange in ascending order: [1,2,3,4]

Try 3 Cases

Remove 2 small, 2 large, or 1 each

Find Minimum

Return best score among the three options

Code -

solution.c — C

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

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

int calculateScore(int* arr, int n) {
    // Calculate minimum difference between consecutive elements
    int minDiff = INT_MAX;
    for (int i = 0; i < n - 1; i++) {
        int diff = arr[i + 1] - arr[i];
        if (diff < minDiff) minDiff = diff;
    }
    // High score is max - min
    int highScore = arr[n - 1] - arr[0];
    return minDiff + highScore;
}

int solution(int* nums, int n) {
    qsort(nums, n, sizeof(int), compare);
    int minScore = INT_MAX;
    int modified[1000];
    
    // Case 1: Remove two smallest (change them to 3rd smallest)
    for (int i = 0; i < n; i++) modified[i] = nums[i];
    modified[0] = modified[1] = nums[2];
    qsort(modified, n, sizeof(int), compare);
    int score = calculateScore(modified, n);
    if (score < minScore) minScore = score;
    
    // Case 2: Remove two largest (change them to 3rd largest)
    for (int i = 0; i < n; i++) modified[i] = nums[i];
    modified[n - 1] = modified[n - 2] = nums[n - 3];
    qsort(modified, n, sizeof(int), compare);
    score = calculateScore(modified, n);
    if (score < minScore) minScore = score;
    
    // Case 3: Remove smallest and largest
    for (int i = 0; i < n; i++) modified[i] = nums[i];
    modified[0] = nums[1];
    modified[n - 1] = nums[n - 2];
    qsort(modified, n, sizeof(int), compare);
    score = calculateScore(modified, n);
    if (score < minScore) minScore = score;
    
    return minScore;
}

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, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Dominated by sorting step, then O(n) for score calculations

⚡ Linearithmic

Space Complexity

O(1)

Only constant extra variables for tracking minimum score

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 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

Optimized Greedy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler