【Video】Give me 5 minutes - How we think about a solution
Intuition\r\nUse the two biggest numbers and the two smallest numbers\r\n\r\n---\r\n\r\n# Solution Video\r\n\r\nhttps://youtu.be/DMzedO_tGr8\r\n\r\n\u25A0 Timel
# Intuition\r\nUse the two biggest numbers and the two smallest numbers\r\n\r\n---\r\n\r\n# Solution Video\r\n\r\nhttps://youtu.be/DMzedO_tGr8\r\n\r\n\u25A0 Timeline of the video\r\n\r\n`0:05` Explain solution formula\r\n`0:47` Talk about the first smallest and the second smallest\r\n`3:32` Talk about the first biggest and the second biggest\r\n`5:11` coding\r\n`8:10` Time Complexity and Space Complexity\r\n`8:26` Step by step algorithm of my solution code\r\n\r\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\r\n\r\n**\u25A0 Subscribe URL**\r\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\r\n\r\nSubscribers: 3,518\r\nMy first goal is 10,000 (It\'s far from done \uD83D\uDE05)\r\nThank you for your support!\r\n\r\n---\r\n\r\n# Approach\r\n\r\n## How we think about a solution\r\n\r\nConstraints says `1 <= nums[i] <= 104`, so simply maximum product difference should be\r\n\r\n```\r\nfirst biggest * second biggest - first smallest * second smallest\r\n```\r\n\r\nIf we use `sort` and then take the first two numbers and the last two numbers, we can solve this question. But that is $$O(nlogn)$$. It\'s a boring answer. Let\'s think about $$O(n)$$ solution.\r\n\r\nLet\'s think about 4 cases.\r\n\r\n---\r\n\r\n- First smallest\r\n- Second smallest\r\n- First biggest\r\n- Second biggest\r\n\r\n---\r\nBasically we iterate through all numbers one by one. The numbers are compared in the order specified above.\r\n\r\n#### First smallest\r\n\r\nIf current number is smaller than the current smallest number,\r\n\r\n---\r\n\r\n\u2B50\uFE0F Points\r\n\r\nthe current number will be the first smallest number.\r\nthe current first smallest number will be the second smallest number.\r\n\r\n---\r\n\r\n#### Second smallest\r\n\r\nNext, we check the second smallest. If current number is smaller than the current second smallest number,\r\n\r\n---\r\n\r\n\u2B50\uFE0F Points\r\n\r\nWe can just update the second smallest number with current number, because we already compared current number with the first smallest number, so we are sure that the current number is \r\n\r\n```\r\nthe first smallest < current < the second smallest\r\n```\r\n\r\n---\r\n\r\nSo, current number will be the second smallest number.\r\n\r\nRegarding biggest numbers, we apply the same idea. Let me explain them quickly.\r\n\r\n#### First biggest\r\n\r\nIf current number is bigger than the current biggest number,\r\n\r\n---\r\n\r\n\u2B50\uFE0F Points\r\n\r\nthe current number will be the first biggest number.\r\nthe current first biggest number will be the second biggest number.\r\n\r\n---\r\n\r\n####  Second biggest\r\n\r\nIf current number is bigger than the current second bigger number,\r\n\r\n---\r\n\r\n\u2B50\uFE0F Points\r\n\r\nWe are sure\r\n\r\n```\r\nthe first biggest > current > the second biggest\r\n```\r\n\r\nBecause we already compared current number with the first biggest number.\r\n\r\n---\r\n\r\nSo, current number will be the second biggest number.\r\n\r\nEasy!\uD83D\uDE04\r\nLet\'s see a real algorithm!\r\n\r\n---\r\n\r\n# Complexity\r\n- Time complexity: $$O(n)$$\r\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\r\n\r\n- Space complexity: $$O(1)$$\r\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\r\n\r\n```python []\r\nclass Solution:\r\n    def maxProductDifference(self, nums: List[int]) -> int:\r\n        first_big = second_big = 0\r\n        first_small = second_small = float("inf")\r\n\r\n        for n in nums:\r\n            if n < first_small:\r\n                second_small, first_small = first_small, n                \r\n            elif n < second_small:                \r\n                second_small = n                \r\n\r\n            if n > first_big:\r\n                second_big, first_big = first_big, n\r\n            elif n > second_big:\r\n                second_big = n        \r\n\r\n        return first_big * second_big - first_small * second_small\r\n```\r\n```javascript []\r\n/**\r\n * @param {number[]} nums\r\n * @return {number}\r\n */\r\nvar maxProductDifference = function(nums) {\r\n    let firstBig = secondBig = 0;\r\n    let firstSmall = secondSmall = Infinity;\r\n\r\n    for (const n of nums) {\r\n        if (n < firstSmall) {\r\n            [secondSmall, firstSmall] = [firstSmall, n];\r\n        } else if (n < secondSmall) {\r\n            secondSmall = n;\r\n        }\r\n\r\n        if (n > firstBig) {\r\n            [secondBig, firstBig] = [firstBig, n];\r\n        } else if (n > secondBig) {\r\n            secondBig = n;\r\n        }\r\n    }\r\n\r\n    return firstBig * secondBig - firstSmall * secondSmall;    \r\n};\r\n```\r\n```java []\r\nclass Solution {\r\n    public int maxProductDifference(int[] nums) {\r\n        int firstBig = 0, secondBig = 0;\r\n        int firstSmall = Integer.MAX_VALUE, secondSmall = Integer.MAX_VALUE;\r\n\r\n        for (int n : nums) {\r\n            if (n < firstSmall) {\r\n                secondSmall = firstSmall;\r\n                firstSmall = n;\r\n            } else if (n < secondSmall) {\r\n                secondSmall = n;\r\n            }\r\n\r\n            if (n > firstBig) {\r\n                secondBig = firstBig;\r\n                firstBig = n;\r\n            } else if (n > secondBig) {\r\n                secondBig = n;\r\n            }\r\n        }\r\n\r\n        return firstBig * secondBig - firstSmall * secondSmall;        \r\n    }\r\n}\r\n```\r\n```C++ []\r\nclass Solution {\r\npublic:\r\n    int maxProductDifference(vector<int>& nums) {\r\n        int firstBig = 0, secondBig = 0;\r\n        int firstSmall = INT_MAX, secondSmall = INT_MAX;\r\n\r\n        for (int n : nums) {\r\n            if (n < firstSmall) {\r\n                secondSmall = firstSmall;\r\n                firstSmall = n;\r\n            } else if (n < secondSmall) {\r\n                secondSmall = n;\r\n            }\r\n\r\n            if (n > firstBig) {\r\n                secondBig = firstBig;\r\n                firstBig = n;\r\n            } else if (n > secondBig) {\r\n                secondBig = n;\r\n            }\r\n        }\r\n\r\n        return firstBig * secondBig - firstSmall * secondSmall;        \r\n    }\r\n};\r\n```\r\n\r\n## Step by step algorithm\r\n\r\n1. **Initialize Variables:**\r\n   ```python\r\n   first_big = second_big = 0\r\n   first_small = second_small = float("inf")\r\n   ```\r\n   - `first_big`, `second_big`: Initialize variables to keep track of the two largest numbers.\r\n   - `first_small`, `second_small`: Initialize variables to keep track of the two smallest numbers. `float("inf")` is used to represent positive infinity.\r\n\r\n2. **Iterate Through the Numbers:**\r\n   ```python\r\n   for n in nums:\r\n   ```\r\n   - Loop through each number in the input list `nums`.\r\n\r\n3. **Update Variables for Smallest Numbers:**\r\n   ```python\r\n   if n < first_small:\r\n       second_small, first_small = first_small, n\r\n   elif n < second_small:\r\n       second_small = n\r\n   ```\r\n   - If the current number `n` is smaller than the current smallest number (`first_small`), update both smallest numbers accordingly.\r\n   - If `n` is smaller than the second smallest number (`second_small`) but not the smallest, update only the second smallest.\r\n\r\n4. **Update Variables for Largest Numbers:**\r\n   ```python\r\n   if n > first_big:\r\n       second_big, first_big = first_big, n\r\n   elif n > second_big:\r\n       second_big = n\r\n   ```\r\n   - If the current number `n` is larger than the current largest number (`first_big`), update both largest numbers accordingly.\r\n   - If `n` is larger than the second largest number (`second_big`) but not the largest, update only the second largest.\r\n\r\n5. **Calculate and Return Result:**\r\n   ```python\r\n   return first_big * second_big - first_small * second_small\r\n   ```\r\n   - Calculate the product difference between the two largest and two smallest numbers.\r\n   - Return the result.\r\n\r\nThe algorithm efficiently finds the two largest and two smallest numbers in the list and computes their product difference.\r\n\r\n---\r\n\r\nThank you for reading my post.\r\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\r\n\r\n\u25A0 Subscribe URL\r\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\r\n\r\n\u25A0 Twitter\r\nhttps://twitter.com/CodingNinjaAZ\r\n\r\n### My next daily coding challenge post and video.\r\n\r\npost\r\nhttps://leetcode.com/problems/image-smoother/solutions/4423391/video-give-me-10-minutes-how-we-think-about-a-solution/\r\n\r\nvideo\r\nhttps://youtu.be/eCHajvYReSg\r\n\r\n\u25A0 Timeline of the video\r\n\r\n`0:03` Explain how we solve Image Smoother\r\n`1:13` Check Top side\r\n`2:18` Check Bottom side\r\n`4:11` Check left and right side\r\n`3:32` Talk about the first biggest and the second biggest\r\n`6:26` coding\r\n`9:24` Time Complexity and Space Complexity\r\n`9:45` Step by step algorithm of my solution code\r\n\r\n### My previous daily coding challenge post and video.\r\n\r\npost\r\nhttps://leetcode.com/problems/design-a-food-rating-system/solutions/4414691/video-give-me-5-minutes-how-we-think-about-a-solution/\r\n\r\nvideo\r\nhttps://youtu.be/F6RAuglUOSg\r\n\r\n\u25A0 Timeline of the video\r\n\r\n`0:04` Explain constructor\r\n`1:21` Why -rating instead of rating?\r\n`4:09` Talk about changeRating\r\n`5:19` Time Complexity and Space Complexity\r\n`6:36` Step by step algorithm of my solution code\r\n`6:39` Python Tips - SortedList\r\n
['C++', 'Java', 'Python3', 'JavaScript']