[3 Solutions Tutorial O(n) Included] Minimum Difference Between Largest and Smallest Value
Topic :  Greedy, Sort\n\nI remember solving this Google OA problem three years ago.\n___\n\n## Solution 1\nIf the length of the input array is 4 or fewer, the a
**Topic** :  Greedy, Sort\n\n**I remember solving this Google OA problem three years ago.**\n___\n\n## Solution 1\nIf the length of the input array is 4 or fewer, the answer is 0 because we can make all numbers equal with up to 3 moves.\n\nThree moves means that **we can remove 3 numbers from the input array to make the remaining numbers equal to any number in the array**.\n\nIf we have more than 4 numbers, the **greedy intuition** suggests that excluding a total of 3 elements from both the leftmost and rightmost ends of the sorted array minimizes the difference between the maximum and minimum values remaining in the array. \n\nThis can simply be proven by contradiction. If we do not remove such numbers (three from both the leftmost and rightmost sides), then either the maximum or minimum of the array might be among the first three or last three numbers after sorting, potentially increasing the difference between them.\n\nThe solution involves iterating through the number of elements removed from the leftmost side. If we choose `i` elements from the leftmost side, then we must choose `3 - i` elements from the right side to remove.\n\n\n```c++ []\nclass Solution {\npublic:\n    int minDifference(vector<int>& nums) {\n        if(nums.size() <= 4) {\n            return 0;\n        }\n        sort(nums.begin(), nums.end());\n        int ans = nums.back() - nums[0];\n        for(int i = 0; i <= 3; i++) {\n            ans = min(ans, nums[nums.size() - (3 - i) - 1] - nums[i]);\n        }\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public int minDifference(int[] nums) {\n        if(nums.length <= 4) {\n            return 0;\n        }\n        Arrays.sort(nums);\n        int ans = nums[nums.length - 1] - nums[0];\n        for(int i = 0; i <= 3; i++) {\n            ans = Math.min(ans, nums[nums.length - (3 - i) - 1] - nums[i]);\n        }\n        return ans;\n    }\n}\n```\n```python []\nclass Solution:\n    def minDifference(self, nums: List[int]) -> int:\n        if len(nums) <= 4:\n            return 0\n        nums.sort()\n        ans = nums[-1] - nums[0]\n        for i in range(4):\n            ans = min(ans, nums[-(4 - i)] - nums[i])\n        return ans\n```\n```Go []\nfunc minDifference(nums []int) int {\n    if len(nums) <= 4 {\n        return 0\n    }\n    sort.Ints(nums)\n    ans := nums[len(nums)-1] - nums[0]\n    for i := 0; i <= 3; i++ {\n        ans = min(ans, nums[len(nums) - (3 - i) - 1] - nums[i])\n    }\n    return ans\n}\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param Integer[] $nums\n     * @return Integer\n     */\n    function minDifference($nums) {\n        if (count($nums) <= 4) {\n            return 0;\n        }\n        sort($nums);\n        $ans = $nums[count($nums) - 1] - $nums[0];\n        for ($i = 0; $i <= 3; $i++) {\n            $ans = min($ans, $nums[count($nums) - (3 - $i) - 1] - $nums[$i]);\n        }\n        return $ans;\n    }\n}\n```\n```javascript []\n/**\n * @param {number[]} nums\n * @return {number}\n */\nvar minDifference = function(nums) {\n    if (nums.length <= 4) {\n        return 0;\n    }\n    nums.sort((a, b) => a - b);\n    let ans = nums[nums.length - 1] - nums[0];\n    for (let i = 0; i <= 3; i++) {\n        ans = Math.min(ans, nums[nums.length - (3 - i) - 1] - nums[i]);\n    }\n    return ans;\n};\n```\n\n**Complexity**:\n* Time Complexity : `O(n log n)`\n* Space Complexity : `O(1)`\n\n<br/><br/>\n## Solution 2\nAnother approach involves computing the difference between the maximum and minimum values within each sliding window of size `len(nums) - 3`. This approach simplifies the implementation and enhances readability compared to the previous method.\n\n```c++ []\nclass Solution {\npublic:\n    int minDifference(vector<int>& nums) {\n        if(nums.size() <= 4) {\n            return 0;\n        }\n        sort(nums.begin(), nums.end());\n        int k = nums.size() - 3;\n        int ans = nums.back() - nums[0];\n        for(int i = k - 1; i < nums.size(); i++) {\n            ans = min(ans, nums[i] - nums[i - k + 1]);\n        }\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public int minDifference(int[] nums) {\n        if (nums.length <= 4) {\n            return 0;\n        }\n        Arrays.sort(nums);\n        int k = nums.length - 3;\n        int ans = nums[nums.length - 1] - nums[0];\n        for (int i = k - 1; i < nums.length; i++) {\n            ans = Math.min(ans, nums[i] - nums[i - k + 1]);\n        }\n        return ans;\n    }\n}\n```\n```python []\nclass Solution:\n    def minDifference(self, nums: List[int]) -> int:\n        if len(nums) <= 4:\n            return 0\n        nums.sort()\n        k = len(nums) - 3\n        ans = nums[-1] - nums[0]\n        for i in range(k - 1, len(nums)):\n            ans = min(ans, nums[i] - nums[i - k + 1])\n        return ans\n```\n```Go []\nfunc minDifference(nums []int) int {\n    if len(nums) <= 4 {\n        return 0\n    }\n    sort.Ints(nums)\n    k := len(nums) - 3\n    ans := nums[len(nums)-1] - nums[0]\n    for i := k - 1; i < len(nums); i++ {\n        ans = min(ans, nums[i] - nums[i - k + 1])\n    }\n    return ans\n}\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param Integer[] $nums\n     * @return Integer\n     */\n    function minDifference($nums) {\n        if (count($nums) <= 4) {\n            return 0;\n        }\n        sort($nums);\n        $k = count($nums) - 3;\n        $ans = $nums[count($nums) - 1] - $nums[0];\n        for ($i = $k - 1; $i < count($nums); $i++) {\n            $ans = min($ans, $nums[$i] - $nums[$i - $k + 1]);\n        }\n        return $ans;\n    }\n}\n```\n```javascript []\n/**\n * @param {number[]} nums\n * @return {number}\n */\nvar minDifference = function(nums) {\n    if (nums.length <= 4) {\n        return 0;\n    }\n    nums.sort((a, b) => a - b);\n    let k = nums.length - 3;\n    let ans = nums[nums.length - 1] - nums[0];\n    for (let i = k - 1; i < nums.length; i++) {\n        ans = Math.min(ans, nums[i] - nums[i - k + 1]);\n    }\n    return ans;\n};\n```\n\n**Complexity**:\n* Time Complexity : `O(n log n)`\n* Space Complexity : `O(1)`\n\n<br/>\n\n## Bonus\nWe only need the first four numbers and the last four numbers, so there\'s no need to sort the entire array. We can use an array of size 4 to keep track of both the top 4 largest and the top 4 smallest elements.\n\nHere is the simple and clean implementation:\n\n```c++ []\nclass Solution {\npublic:\n    int minDifference(vector<int>& nums) {\n        if(nums.size() <= 4) {\n            return 0;\n        }\n        \n        vector<int> min4, max4;\n        \n        for(int i = 0; i < nums.size(); i++) {\n            bool add = false;\n            for(int j = 0; j < min4.size(); j++) {\n               if(nums[i] < min4[j]) {\n                   shift(min4, j);\n                   min4[j] = nums[i];\n                   add = true;\n                   break;\n               }\n            } \n            if(!add && min4.size() < 4) {\n                min4.push_back(nums[i]);\n            }\n        }\n        \n        for(int i = 0; i < nums.size(); i++) {\n            bool add = false;\n            for(int j = 0; j < max4.size(); j++) {\n               if(nums[i] > max4[j]) {\n                   shift(max4, j);\n                   max4[j] = nums[i];\n                   add = true;\n                   break;\n               }\n            } \n            if(!add && max4.size() < 4) {\n                max4.push_back(nums[i]);\n            }\n        }\n        \n        int ans = max4[0] - min4[0];\n        for(int i = 0; i <= 3; i++) {\n            ans = min(ans, max4[3 - i] - min4[i]);\n        }\n        return ans;\n    }\n    \n    void shift(vector<int>& a, int start) { //[1 2  3]   \n        int last = a.back();\n        for(int j = a.size() - 1; j > start; j--) {\n            a[j] = a[j - 1];\n        }\n        if(a.size() < 4) a.push_back(last);\n    }\n};\n```\n```java []\nclass Solution {\n    public int minDifference(int[] nums) {\n        if (nums.length <= 4) {\n            return 0;\n        }\n        \n        int[] min4 = new int[4];\n        int[] max4 = new int[4];\n        \n        Arrays.fill(min4, Integer.MAX_VALUE);\n        Arrays.fill(max4, Integer.MIN_VALUE);\n        \n        for (int num : nums) {\n            boolean added = false;\n            for (int j = 0; j < min4.length; j++) {\n                if (num < min4[j]) {\n                    shift(min4, j);\n                    min4[j] = num;\n                    added = true;\n                    break;\n                }\n            }\n            if (!added && min4[min4.length - 1] == Integer.MAX_VALUE) {\n                min4[min4.length - 1] = num;\n            }\n        }\n        \n        for (int num : nums) {\n            boolean added = false;\n            for (int j = 0; j < max4.length; j++) {\n                if (num > max4[j]) {\n                    shift(max4, j);\n                    max4[j] = num;\n                    added = true;\n                    break;\n                }\n            }\n            if (!added && max4[max4.length - 1] == Integer.MIN_VALUE) {\n                max4[max4.length - 1] = num;\n            }\n        }\n        \n        int ans = max4[0] - min4[0];\n        for (int i = 0; i <= 3; i++) {\n            ans = Math.min(ans, max4[3 - i] - min4[i]);\n        }\n        return ans;\n    }\n    private void shift(int[] a, int start) {\n        int last = a[a.length - 1];\n        for (int j = a.length - 1; j > start; j--) {\n            a[j] = a[j - 1];\n        }\n        if (a.length < 4) {\n            a[a.length - 1] = last;\n        }\n    }\n}\n```\n```python []\nclass Solution:\n    def shift(self, a: List[int], start: int) -> None:\n        last = a[-1]\n        for j in range(len(a) - 1, start, -1):\n            a[j] = a[j - 1]\n        if len(a) < 4:\n            a.append(last)\n    \n    def minDifference(self, nums: List[int]) -> int:\n        if len(nums) <= 4:\n            return 0\n        \n        min4 = [float(\'inf\')] * 4\n        max4 = [float(\'-inf\')] * 4\n        \n        for num in nums:\n            added = False\n            for j in range(4):\n                if num < min4[j]:\n                    self.shift(min4, j)\n                    min4[j] = num\n                    added = True\n                    break\n            if not added and min4[-1] == float(\'inf\'):\n                min4[-1] = num\n        \n        for num in nums:\n            added = False\n            for j in range(4):\n                if num > max4[j]:\n                    self.shift(max4, j)\n                    max4[j] = num\n                    added = True\n                    break\n            if not added and max4[-1] == float(\'-inf\'):\n                max4[-1] = num\n        \n        ans = max4[0] - min4[0]\n        for i in range(4):\n            ans = min(ans, max4[3 - i] - min4[i])\n        \n        return ans\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param Integer[] $nums\n     * @return Integer\n     */\n    function minDifference($nums) {\n        if (count($nums) <= 4) {\n            return 0;\n        }\n        \n        $min4 = array_fill(0, 4, PHP_INT_MAX);\n        $max4 = array_fill(0, 4, PHP_INT_MIN);\n        \n        foreach ($nums as $num) {\n            $added = false;\n            for ($j = 0; $j < 4; $j++) {\n                if ($num < $min4[$j]) {\n                    $this->shift($min4, $j);\n                    $min4[$j] = $num;\n                    $added = true;\n                    break;\n                }\n            }\n            if (!$added && end($min4) == PHP_INT_MAX) {\n                $min4[3] = $num;\n            }\n        }\n        \n        foreach ($nums as $num) {\n            $added = false;\n            for ($j = 0; $j < 4; $j++) {\n                if ($num > $max4[$j]) {\n                    $this->shift($max4, $j);\n                    $max4[$j] = $num;\n                    $added = true;\n                    break;\n                }\n            }\n            if (!$added && end($max4) == PHP_INT_MIN) {\n                $max4[3] = $num;\n            }\n        }\n        \n        $ans = $max4[0] - $min4[0];\n        for ($i = 0; $i < 4; $i++) {\n            $ans = min($ans, $max4[3 - $i] - $min4[$i]);\n        }\n        \n        return $ans;\n    }\n    \n    function shift(&$a, $start) {\n        $last = end($a);\n        for ($j = count($a) - 1; $j > $start; $j--) {\n            $a[$j] = $a[$j - 1];\n        }\n        if (count($a) < 4) {\n            $a[] = $last;\n        }\n    }\n}\n```\n```Go []\nfunc shift(a []int, start int) {\n\tlast := a[len(a)-1]\n\tfor j := len(a)-1; j > start; j-- {\n\t\ta[j] = a[j-1]\n\t}\n\tif len(a) < 4 {\n\t\ta = append(a, last)\n\t}\n}\n\nfunc minDifference(nums []int) int {\n    if len(nums) <= 4 {\n\t\treturn 0\n\t}\n\t\n\tmin4 := make([]int, 4)\n\tmax4 := make([]int, 4)\n\t\n\tfor i := 0; i < 4; i++ {\n\t\tmin4[i] = math.MaxInt32\n\t\tmax4[i] = math.MinInt32\n\t}\n\t\n\tfor _, num := range nums {\n\t\tadded := false\n\t\tfor j := 0; j < 4; j++ {\n\t\t\tif num < min4[j] {\n\t\t\t\tshift(min4, j)\n\t\t\t\tmin4[j] = num\n\t\t\t\tadded = true\n\t\t\t\tbreak\n\t\t\t}\n\t\t}\n\t\tif !added && min4[3] == math.MaxInt32 {\n\t\t\tmin4[3] = num\n\t\t}\n\t}\n\t\n\tfor _, num := range nums {\n\t\tadded := false\n\t\tfor j := 0; j < 4; j++ {\n\t\t\tif num > max4[j] {\n\t\t\t\tshift(max4, j)\n\t\t\t\tmax4[j] = num\n\t\t\t\tadded = true\n\t\t\t\tbreak\n\t\t\t}\n\t\t}\n\t\tif !added && max4[3] == math.MinInt32 {\n\t\t\tmax4[3] = num\n\t\t}\n\t}\n\t\n\tans := max4[0] - min4[0]\n\tfor i := 0; i < 4; i++ {\n\t\tans = min(ans, max4[3-i] - min4[i])\n\t}\n\t\n\treturn ans\n}\n```\n```javascript []\n/**\n * @param {number[]} nums\n * @return {number}\n */\nvar minDifference = function(nums) {\n    function shift(a, start) {\n        let last = a[a.length - 1];\n        for (let j = a.length - 1; j > start; j--) {\n            a[j] = a[j - 1];\n        }\n        if (a.length < 4) {\n            a[a.length] = last;\n        }\n    }\n    if (nums.length <= 4) {\n        return 0;\n    }\n        \n    let min4 = Array(4).fill(Number.MAX_SAFE_INTEGER);\n    let max4 = Array(4).fill(Number.MIN_SAFE_INTEGER);\n        \n    for (let num of nums) {\n        let added = false;\n        for (let j = 0; j < 4; j++) {\n            if (num < min4[j]) {\n                shift(min4, j);\n                min4[j] = num;\n                added = true;\n                break;\n            }\n        }\n        if (!added && min4[3] === Number.MAX_SAFE_INTEGER) {\n            min4[3] = num;\n        }\n    }\n        \n    for (let num of nums) {\n        let added = false;\n        for (let j = 0; j < 4; j++) {\n            if (num > max4[j]) {\n                shift(max4, j);\n                max4[j] = num;\n                added = true;\n                break;\n            }\n        }\n        if (!added && max4[3] === Number.MIN_SAFE_INTEGER) {\n            max4[3] = num;\n        }\n    }\n        \n    let ans = max4[0] - min4[0];\n    for (let i = 0; i < 4; i++) {\n        ans = Math.min(ans, max4[3 - i] - min4[i]);\n    }\n        \n    return ans;\n};\n```\n\nIllustration of the above logic : \n\n```\nSuppose we want to find the top4 minimum numbers (the logic is the same for maximum) and we have the following array : [1, 3, 5, 4, 6, 2]\n\nSteps:\n* Inialized an array with size 4 [INF, INF, INF, INF] with max int value.\n* Add 1 to min4 : [1, INF, INF, INF]\n* Add 3 to min4 : [1, 3, INF, INF]\n* Add 5 to min4 : [1, 3, 5, INF]\n* Add 4 to min4:\n\t* First, find the position where we need to insert 4 and shift all elements after it one place to the right. [1, 3, 5, 5] \n\t* Insert 4 => [1, 3, 4, 5]\n* Add 6 to min4 : [1, 3, 4, 5]\n* Add 2 to min4:\n\t* First, find the position where we need to insert 2 and shift all elements after it one place to the right. [1, 3, 3, 4]\n\t* Insert 2 => [1, 2, 3, 4]\n\n```\n\n\n\n**Complexity**:\n* Time Complexity : `O(n)`\n* Space Complexity : `O(1)`\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['C', 'PHP', 'Python', 'Java', 'Go', 'JavaScript']