【Video】Give me 6 minutes - How we think about a solution
Intuition\nSort each subarray.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/bE6YT9q16K8\n\n\u25A0 Timeline of the video\n0:04 What does the formula mean?\n1:4
# Intuition\nSort each subarray.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/bE6YT9q16K8\n\n\u25A0 Timeline of the video\n`0:04` What does the formula mean?\n`1:46` Demonstrate how it works\n`3:39` Coding\n`5:40` Time Complexity and Space Complexity\n`6:06` Summary of the algorithm with my 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,193\nMy first goal is 10,000 (It\'s far from done \uD83D\uDE05)\nThank you for your support!\n\n**My channel reached 3,000 subscribers these days. Thank you so much for your support!**\n\n---\n\n# Approach\n\n## How we think about a solution\n\nWe have this formula.\n\n```\ns[i+1] - s[i] == s[1] - s[0]\n```\nThis means all two adjacent numbers are the same difference.\n\nLet\'s say we have these two numbers.\n\n```\n[3,5]\n```\nWhat is the next number if we get `true`? It\'s `7`. It\'s impossible to put smaller than `5`, becuase\n```\ns[1] - s[0]\n= 5 - 3\n= 2\n```\nWe need to add `2` to `5`. What is the next number of `7`. It\'s `9`.\n```\n[3,5,7,9]\n```\nThe next number should be `11`.\n\nI think we have a solution pattern.\n\n---\n\n\u2B50\uFE0F Points\n\nSort subarray then check difference between all two adjacent numbers. We don\'t have to sort it with descending order, because if ascending order is true, descending order is also true.\n\n`[3,5,7,9]` is `true`. The difference between all two adjacent numbers are `2`.\n`[9,7,5,3]` is `true`. The difference between all two adjacent numbers are `-2`.\n\nBoth cases meet `s[i+1] - s[i] == s[1] - s[0]`.\n\nThat\'s why we sort each subarray with ascending order.\n\n---\n\nLet\'s see one by one.\n\n```\nInput: nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]\n```\nThe first subarray is `[4,6,5]`. Sort it and check all two adjacent numbers.\n```\n[4,5,6]\n\u2192 True\nBecause the difference between all two adjacent numbers are 1\n```\nThe next subarray is `[4,6,5,9]`. Sort it and check all two adjacent numbers.\n```\n[4,5,6,9]\n\u2192 False \nBecause the difference between 6 and 9 are 3, others are 1.\n```\nThe next subarray is `[3,5,7,9]`. Sort it and check all two adjacent numbers.\n```\n[3,5,7,9]\n\u2192 True\nBecause the difference between all two adjacent numbers are 2.\n```\n```\nOutput: [True, False, True]\n```\n\nEasy!\uD83D\uDE04\nLet\'s see a real algorithm!\n\n\n---\n### Algorithm Overview\n1. Take each subarray one by one\n2. sort them and check all two adjacent numbers.\n\n### Detailed Explanation\n\n1. **Nested Function Definition:**\n    ```python\n    def is_arithmetic(sub):\n    ```\n   This is a nested function named `is_arithmetic` that takes a list of integers (`sub`) and returns a boolean.\n\n2. **Sort the Subarray:**\n    ```python\n    sub.sort()\n    ```\n   The function sorts the input subarray in ascending order.\n\n3. **Calculate Difference:**\n    ```python\n    diff = sub[1] - sub[0]\n    ```\n   It calculates the difference between the second and first elements in the sorted subarray.\n\n4. **Check Arithmetic Sequence:**\n    ```python\n    for i in range(2, len(sub)):\n        if sub[i] - sub[i - 1] != diff:\n            return False\n    ```\n   It iterates through the sorted subarray starting from the third element. If the difference between consecutive elements is not equal to the calculated difference, it returns `False`, indicating that the subarray is not an arithmetic sequence.\n\n5. **Return True for Arithmetic Sequence:**\n    ```python\n    return True\n    ```\n   If the loop completes without returning `False`, it means that the subarray is an arithmetic sequence, so the function returns `True`.\n\n6. **Iterate Through Queries:**\n    ```python\n    res = []\n    for q in range(len(l)):\n        res.append(is_arithmetic(nums[l[q]:r[q]+1]))\n    ```\n   The main function iterates through the queries specified by the lists `l` and `r`. For each query, it extracts the subarray from the original `nums` array using slicing and calls the `is_arithmetic` function. The result (True or False) is appended to the `res` list.\n\n7. **Return the Results:**\n    ```python\n    return res\n    ```\n   The main function returns the list of boolean results for each query.\n\nIn summary, the algorithm checks whether each specified subarray in the `nums` array is an arithmetic sequence and returns a list of booleans indicating the result for each subarray.\n\n\n---\n\n\n\n# Complexity\n- Time complexity: $$O(q * n log n)$$\n`q` is number of query\n`n log n` is for sorting each subarray every time \n\n- Space complexity: $$O(q)$$\nWe have to return true or false length of query times.\n\n```python []\nclass Solution:\n    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:\n\n        def is_arithmetic(sub):\n            sub.sort()\n            diff = sub[1] - sub[0]\n            for i in range(2, len(sub)):\n                if sub[i] - sub[i - 1] != diff:\n                    return False\n            return True\n\n        res = []\n        for q in range(len(l)):\n            res.append(is_arithmetic(nums[l[q]:r[q]+1]))\n        return res\n```\n```javascript []\nvar checkArithmeticSubarrays = function(nums, l, r) {\n    function isArithmetic(sub) {\n        sub.sort((a, b) => a - b);\n        const diff = sub[1] - sub[0];\n        for (let i = 2; i < sub.length; i++) {\n            if (sub[i] - sub[i - 1] !== diff) {\n                return false;\n            }\n        }\n        return true;\n    }\n\n    const res = [];\n    for (let q = 0; q < l.length; q++) {\n        res.push(isArithmetic(nums.slice(l[q], r[q] + 1)));\n    }\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {\n        List<Boolean> res = new ArrayList<>();\n\n        for (int q = 0; q < l.length; q++) {\n            res.add(isArithmetic(Arrays.copyOfRange(nums, l[q], r[q] + 1)));\n        }\n\n        return res;        \n    }\n\n    private boolean isArithmetic(int[] sub) {\n        Arrays.sort(sub);\n        int diff = sub[1] - sub[0];\n        for (int i = 2; i < sub.length; i++) {\n            if (sub[i] - sub[i - 1] != diff) {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n        vector<bool> res;\n\n        for (int q = 0; q < l.size(); q++) {\n            res.push_back(isArithmetic(vector<int>(nums.begin() + l[q], nums.begin() + r[q] + 1)));\n        }\n\n        return res;\n    }\n\nprivate:\n    bool isArithmetic(const vector<int>& sub) {\n        vector<int> sortedSub(sub);\n        sort(sortedSub.begin(), sortedSub.end());\n        int diff = sortedSub[1] - sortedSub[0];\n        for (int i = 2; i < sortedSub.size(); i++) {\n            if (sortedSub[i] - sortedSub[i - 1] != diff) {\n                return false;\n            }\n        }\n        return true;\n    }\n};\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### My next daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/maximum-number-of-coins-you-can-get/solutions/4322538/video-give-me-4-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/HPzfCHfWPlY\n\n\u25A0 Timeline\u3000of the video\n`0:04` Two key points to solve this question\n`1:46` Demonstrate how it works\n`3:17` Coding\n`4:14` Time Complexity and Space Complexity\n`4:33` Summary of the algorithm with my solution code\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/diagonal-traverse-ii/solutions/4316572/video-give-me-9-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/4wkt4kGip64\n\n\u25A0 Timeline of the video\n`0:04` How we think about a solution\n`1:08` How can you put numbers into queue with right order?\n`2:34` Demonstrate how it works\n`6:24` Summary of main idea\n`6:47` Coding\n`8:40` Time Complexity and Space Complexity\n`8:57` Summary of the algorithm with my solution code\n\n
['C++', 'Java', 'Python3', 'JavaScript']