【Video】Give me 5 minutes - 2 solutions - How we think about a solution
Intuition\nKeep the largest number so far\n\n---\n\n# Solution Video\n\nhttps://youtu.be/JV5Kuinx-m0\n\n\u25A0 Timeline of the video\n\n0:05 Explain algorithm o
# Intuition\nKeep the largest number so far\n\n---\n\n# Solution Video\n\nhttps://youtu.be/JV5Kuinx-m0\n\n\u25A0 Timeline of the video\n\n`0:05` Explain algorithm of Solution 1\n`3:18` Coding of solution 1\n`4:18` Time Complexity and Space Complexity of solution 1\n`4:29` Step by step algorithm of solution 1\n`4:36` Explain key points of Solution 2\n`5:25` Coding of Solution 2\n`6:50` Time Complexity and Space Complexity of Solution 2\n`7:03` Step by step algorithm with my stack solution code\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 3,424\nMy first goal is 10,000 (It\'s far from done \uD83D\uDE05)\nThank you for your support!\n\n---\n\n# Approach\n\n## How we think about a solution\n\nSeems like all numbers are positive, so simply all we have to do is to find the two largest numbers in input array.\n\nThe key point of my first solution is\n\n---\n\n\u2B50\uFE0F Points\n\nKeep the largest number(= `cur_max` in the solution code) so far and compare \n\n```\nres vs (cur_max - 1) * (nums[i] - 1)\n```\n\n`res` is current max result so far\n`nums[i]` is current number\n\n---\n\nLet\'s see one by one.\n\n```\nInput: nums = [1,5,4,5]\n```\nWe keep the number at index 0 as a current max number.\n```\nres = 0\ncur_max = 1 (= nums[0])\n```\nStart iteration from index 1. \n```\nAt index 1, Compare\n\nmax(res, (cur_max - 1) * (nums[i] - 1))\n\u2192 max(0, (1 - 1) * (5 - 1))\n= 0\n\nres = 0\n```\n`res` is still `0` and we need to update `cur_max` if current number is greater than `cur_max`.\n```\ncur_max = max(cur_max, nums[i])\n= 1 vs 5\n\ncur_max = 5\n``` \nI\'ll speed up.\n```\nAt index 2, Compare\n\nmax(res, (cur_max - 1) * (nums[i] - 1))\n\u2192 max(0, (5 - 1) * (4 - 1))\n= 12\n\nres = 12\ncur_max = 5 (= max(5, 4))\n```\n\n```\nAt index 3, Compare\n\nmax(res, (cur_max - 1) * (nums[i] - 1))\n\u2192 max(12, (5 - 1) * (5 - 1))\n= 16\n\nres = 16\ncur_max = 5 (= max(5, 5))\n```\n```\nOutput: 16\n```\n\nEasy \uD83D\uDE06!\nLet\'s see a real algorithm!\n\n\n---\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```python []\nclass Solution:\n    def maxProduct(self, nums: List[int]) -> int:\n        res = 0\n        cur_max = nums[0]\n\n        for i in range(1, len(nums)):\n            res = max(res, (cur_max - 1) * (nums[i] - 1))\n            cur_max = max(cur_max, nums[i])\n\n        return res        \n```\n```javascript []\n/**\n * @param {number[]} nums\n * @return {number}\n */\nvar maxProduct = function(nums) {\n    let res = 0;\n    let curMax = nums[0];\n\n    for (let i = 1; i < nums.length; i++) {\n        res = Math.max(res, (curMax - 1) * (nums[i] - 1));\n        curMax = Math.max(curMax, nums[i]);\n    }\n\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public int maxProduct(int[] nums) {\n        int res = 0;\n        int curMax = nums[0];\n\n        for (int i = 1; i < nums.length; i++) {\n            res = Math.max(res, (curMax - 1) * (nums[i] - 1));\n            curMax = Math.max(curMax, nums[i]);\n        }\n\n        return res;        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maxProduct(vector<int>& nums) {\n        int res = 0;\n        int curMax = nums[0];\n\n        for (int i = 1; i < nums.size(); i++) {\n            res = max(res, (curMax - 1) * (nums[i] - 1));\n            curMax = max(curMax, nums[i]);\n        }\n\n        return res;        \n    }\n};\n```\n\n## Step by step algorithm\n\n**Initialization:**\n```python\nres = 0\ncur_max = nums[0]\n```\nIn this section, `res` is initialized to 0, and `cur_max` is initialized to the first element of the `nums` list. These variables will be used to keep track of the maximum product and the maximum value encountered during the iterations, respectively.\n\n**Iteration through the List:**\n```python\nfor i in range(1, len(nums)):\n    res = max(res, (cur_max - 1) * (nums[i] - 1))\n    cur_max = max(cur_max, nums[i])\n```\nIn this section, the code iterates through the list starting from the second element (index 1). For each element at index `i`:\n- `res` is updated to the maximum of its current value and the product of `(cur_max - 1) * (nums[i] - 1)`. This ensures that `res` always holds the maximum product found so far.\n- `cur_max` is updated to the maximum of its current value and the current element `nums[i]`. This ensures that `cur_max` always holds the maximum value encountered in the list up to the current index.\n\n**Return Result:**\n```python\nreturn res\n```\nAfter the loop completes, the final value of `res` represents the maximum product of two distinct elements in the list. The function returns this maximum product.\n\n\n---\n\n# Solution 2\n\nBasically, we try to find the first max and second max numbers.\n\n---\n\n\u2B50\uFE0F Points\n\nIf current number is greater than the first max number so far, then \n\n```\ncurrent number will be the first max number\ncurrent first max number will be second max number\n```\nIf current number is less than the first max number so far, then compare \n```\nsecond max number = max(second max number, current number)\n```\n\nBecause there is still possibility that current number will be the second max number.\n\n---\n\nAt last, we multiply the first and second max numbers.\n\nEasy!\uD83D\uDE04\nLet\'s see a real algorithm\n\n\n---\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```python []\nclass Solution:\n    def maxProduct(self, nums: List[int]) -> int:\n        first_max, second_max = 0, 0\n        for num in nums:\n            if num > first_max:\n                second_max, first_max = first_max, num\n            else:\n                second_max = max(second_max, num)\n\n        return (first_max - 1) * (second_max - 1)\n```\n```javascript []\nvar maxProduct = function(nums) {\n    let firstMax = 0;\n    let secondMax = 0;\n\n    for (let num of nums) {\n        if (num > firstMax) {\n            [secondMax, firstMax] = [firstMax, num];\n        } else {\n            secondMax = Math.max(secondMax, num);\n        }\n    }\n\n    return (firstMax - 1) * (secondMax - 1);    \n};\n```\n```java []\nclass Solution {\n    public int maxProduct(int[] nums) {\n        int firstMax = 0;\n        int secondMax = 0;\n\n        for (int num : nums) {\n            if (num > firstMax) {\n                secondMax = firstMax;\n                firstMax = num;\n            } else {\n                secondMax = Math.max(secondMax, num);\n            }\n        }\n\n        return (firstMax - 1) * (secondMax - 1);        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maxProduct(vector<int>& nums) {\n        int firstMax = 0;\n        int secondMax = 0;\n\n        for (int num : nums) {\n            if (num > firstMax) {\n                swap(secondMax, firstMax);\n                firstMax = num;\n            } else {\n                secondMax = max(secondMax, num);\n            }\n        }\n\n        return (firstMax - 1) * (secondMax - 1);        \n    }\n};\n```\n\n## Step by step algorithm\n\n1. **Initialization:**\n\n```\nfirst_max, second_max = 0, 0\n```\n   - `first_max` and `second_max` are initialized to 0. These variables will be used to keep track of the two largest elements in the list.\n\n2. **Iteration through the List:**\n\n```\nfor num in nums:\n    if num > first_max:\n        second_max, first_max = first_max, num\n    else:\n        second_max = max(second_max, num)\n```\n\n   - The code iterates through each element `num` in the `nums` list.\n   - For each `num`:\n     - If `num` is greater than `first_max`, it means `num` is the new maximum. Therefore, the values of `second_max` and `first_max` are updated accordingly. This is done using the simultaneous assignment technique in Python: `second_max, first_max = first_max, num`.\n     - If `num` is not greater than `first_max` but is greater than `second_max`, it means `num` is the new second maximum. Therefore, `second_max` is updated using `second_max = max(second_max, num)`.\n\n3. **Return Result:**\n\n```\nreturn (first_max - 1) * (second_max - 1)\n```\n\n   - After the loop completes, the function returns the product of `(first_max - 1)` and `(second_max - 1)`. This is because the task is to find the maximum product of two distinct elements, so we subtract 1 from each of the largest elements before multiplying.\n\nThe algorithm efficiently finds the two largest elements in the list and returns their product minus 1.\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u25A0 Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n\u25A0 Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n\n### My next daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/special-positions-in-a-binary-matrix/solutions/4397604/video-give-me-5-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/qTAh4HGfUHk\n\n\u25A0 Timeline of the video\n\n`0:05` Explain algorithm of the first step\n`1:06` Explain algorithm of the second step\n`2:36` Coding\n`4:17` Time Complexity and Space Complexity\n`4:55` Step by step algorithm of my solution code\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/solutions/4388310/video-give-me-5-minutes-2-solutions-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/bTm-6y7Ob0A\n\n\u25A0 Timeline of the video\n\n`0:07` Explain algorithm of Solution 1\n`2:46` Coding of solution 1\n`3:49` Time Complexity and Space Complexity of solution 1\n`4:02` Step by step algorithm of solution 1\n`4:09` Explain key points of Solution 2\n`4:47` Explain the first key point\n`6:06` Explain the second key point\n`7:40` Explain the third key point\n`9:33` Coding of Solution 2\n`14:20` Time Complexity and Space Complexity of Solution 2\n`14:48` Step by step algorithm with my stack solution code\n\n
['C++', 'Java', 'Python3', 'JavaScript']