Grokking Google Coding Interview
Vote

0% completed

​

Solution: Minimum Difference Between Largest and Smallest Value in Three Moves

Problem Statement

You are given an integer array nums. You're allowed to change any of the numbers up to three times, turning them into any value you wish.

Return the minimum difference between the largest and smallest value of nums after updating the nums array.

Examples

  • Example 1:

    • Input: [1,5,6,14,15]
    • Expected Output: 1
    • Justification: Change the numbers 14 and 15 to 2 and 3, respectively (or similarly small numbers). Now, the array is [1,2,3,5,6] with a minimum difference of 5 - 1 = 4.

  • Example 2:

    • Input: [10,10,10,10,10]

.....

.....

.....

Like the course? Get enrolled and start learning!
senthil kumar

senthil kumar

· a year ago

Minimum Difference After 3 Operations - Detailed Analysis

This algorithm finds the minimum possible difference between the maximum and minimum values in an array after performing at most 3 operations (changing any element to any value).

Problem Understanding

Goal: Minimize max(array) - min(array) after changing at most 3 elements.

Key Insight: To minimize the difference, we should either:

  1. Remove the largest elements, or

  2. Remove the smallest elements, or

  3. Remove some combination of both

Since we can change 3 elements, we have 4 strategies:

  • Change 3 largest elements

  • Change 2 largest + 1 smallest

  • Change 1 largest + 2 smallest

  • Change 3 smallest elements

Algorithm Walkthrough


public int minDifference(int[] nums)
Aingkaran Jega

Aingkaran Jega

· 2 years ago

the answer should mention the first three elements were changes so the array becomes something like [14,14,14,14,15] which will give minimum difference of 1

Show 1 reply

Reading Progress

0%

Vote for new content