SORTING IS A WASTE OF (RUN)TIME!!! Not one single sort and I have the fastest C# submission 134ms
Intuition\nSorting and comparing.... just seems like way too much work. Why bother with any of that when we can use a few properties of finite arithmetic sequen
# Intuition\nSorting and comparing.... just seems like way too much work. Why bother with any of that when we can use a few properties of finite arithmetic sequences to do the heavy lifting for us?\n\nThe main idea is to use a very quick check to eliminate a given subarray from consideration before we put any real computation into it.\n\nHere is what we need to know about finite arithmetic sequences.\ni) The average value of the sequence is (a_n + a_1) / 2.\nii) The difference between a_i and a_(i+1) is (a_n - a_1) / (n - 1).\n\n# Approach\nFirst we create an array of length nums.size() + 1, and we populate it with the partial sums of the array nums. This allows us to quickly calculate the sum of the elements of the ith subarray as SUM = (partialSums[r[i] + 1] - partialSums[l[i]]).\n\nNow we can compute the average value of the elements of the subarray and compare it to the average value of the arithmetic sequence that would be formed by rearranging the subarray. Iterate through the subarray to find its maximum value and its minimum value. We want to avoid integer division and the rounding associated with it, so instead of division we will use the old grade school trick of cross multiplication to eliminate the denominators when we calculate the the two averages. This gives us something to check:\n\nA) PartialSums[r[i] + 1] - partialSums[l[i]]) * 2 != (SUBARRAY_MIN + SUBARRAY_MAX) * (r[i] - l[i] + 1))\n\nIf the two are not equal then it is impossible to rearrange the subarray into an arithmetic sequence and we can mark it false. Note though if they are equal that does not immediately imply that the subarray can be rearranged into an arithmetic sequence, we will need to verify that. Again, copying and sorting and comparing seems so excessive.\n\nIf the subarray can be rearranged then the first term of the sequence would be the minimum value of the subarray and the final term would be the maximum value, both of which we have already found.\n\nCreate a HashSet<int> and insert every value of the subarray into it.\n\nUse the formula from above to calculate the difference between two adjacent values in the arithmetic sequence:\n\nDiff = (a_n - a_1) / 2 = (subarrayMax - subArrayMin) / 2.\n\nNow we will compute every value that should be in the arithmetic sequence and check if it is contained in the HashSet subArrayElements. If we find even one of our computed values is not in the set, then it is impossible to rearrange the subarray into an arithmetic sequence. SO if we find one, set results[i] = false and contradictionFound = true and break out of the loop.\n\n(The coputed values are subarray_min, subarray_min + Diff, subarray_min + 2*Diff, ..... , subarrayMin + (n-1)*Diff )\n\nIt is possible that the loop ended without us breaking out of it, so check. If contradictionFound == false then the subarray can be rearranged into an arithmetic sequence.\n\nMy RunTime is 134 ms, that is the absolute fastest runtime for C# there is, the next closest is 154 ms. That is an enourmous difference to have between first and second place!!!!\n\nThe same algorithm is also the absolute fastest when written in C++, there it has a Runtime of 15ms and the closest contender in second place is 18ms, a full 20% slower!!!\n\nThis solution beats 100% in Runtime and 96.67% in Memory.\n\nThe code is well commented. Anything that might be unclear here should be clear in the comments.\n\nSometime it pays to completely ignore the hints....\n\nThat\'s all folks....\n\nEDIT: I found another optimization which takes exactly one line of code to detect some but not all subarrays that cannot be rearranged into an arithmetic sequence. It can save even more work and shave the Runtime down even further. If anyone wants me to add it in or explain it give me some thumbs up or request it in the comments. \n\n# Complexity\n- Time complexity:\n$$O(n)$$ \n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\npublic class Solution\n{\n    public IList<bool> CheckArithmeticSubarrays(int[] nums, int[] l, int[] r)\n    {\n        // There are a few tests we can use before resorting to a brute force approach of sort and verify\n\n\n        ///**********************************************************************************************/\n        /// Create an array of the partial sums of nums with length nums.Length + 1. This allows us\n        /// to quickly find the sum of the terms in any subarray.\n        /// \n        /// EX: Given indices i less than j, then the sum of the elements [nums(i) ... nums(j)] is \n        ///     equal to partialSums(j + 1) - partialSums(i).\n        /// \n        /// We will use this array to compute the average value of the elements in the subarray and \n        /// compare them against the forumula for the average value of an arithmetic sequence which\n        /// is:\n        /// \n        /// AVG = (seq_min + seq_max) / 2\n        /// \n        /// If SUM(nums[i]..nums[j])/(j - i + 1) != AVG then we can immediately eliminate the array from consideration.\n        ///**********************************************************************************************/\n        int[] partialSums = new int[nums.Length + 1];\n        partialSums[0] = 0;\n        for(int i = 0; i < nums.Length; i++)\n        {\n            partialSums[i + 1] = partialSums[i] + nums[i];\n        }\n\n\n        bool[] results = new bool[l.Length];\n\n        HashSet<int> subArrayElements = new HashSet<int>();\n        int SUB_MIN = 0;                     // Minimum element in subarray\n        int SUB_MAX = 0;                     // Maximum element in subarray\n        int L_idx = 0;                       // Left index\n        int R_idx = 0;                       // Right index;\n        int n = 0;                           // Number of elements in subarray\n        int Diff = 0;                        // Difference between elements if the subarray is in fact an arithmetic sequence.\n                \n        bool contradictionFound = false;     // Flag used during the second test to detect a logical contradiction and \n                                             // determine a subarray cannot be rearranged into an arithmetic sequence.\n\n        for(int i = 0; i < l.Length; i++)\n        {\n\n            ///**********************************************************************************************/\n            /// Try to quickly identify cases were it is impossible based on the test at the top of the page\n            /// \n            /// NOTE: This WILL NOT CATCH EVERY FALSE! Any case that makes it past this test still needs\n            ///       to be verified before marking it true.\n            ///**********************************************************************************************/\n            SUB_MIN = Int32.MaxValue;\n            SUB_MAX = Int32.MinValue;\n            L_idx = l[i];\n            R_idx = r[i];\n            n = R_idx - L_idx + 1;\n            \n            // Find the minimum and maximum values in the subarray\n            for(int j = L_idx; j <= R_idx; j++)\n            {\n                if (nums[j] < SUB_MIN) SUB_MIN = nums[j];\n                if (nums[j] > SUB_MAX) SUB_MAX = nums[j];\n            }\n\n            // Begin testing the subarray\n            if ( (partialSums[R_idx + 1] - partialSums[L_idx]) * 2 != (SUB_MIN + SUB_MAX) * (R_idx - L_idx + 1) )\n            {\n                // We compare two different methods of calculating the average value of the elements of the subarray.\n                // If the two methods do not agree then clearly it cannot be rearranged into an arithmetic sequence.\n                results[i] = false;\n            }\n            else\n            {\n                contradictionFound = false;\n                ///**********************************************************************************************/\n                ///  We will add the elements of the subarray to a HashSet. Then we will compute each term in what\n                ///  would be the arithmetic sequence and add each to the HashSet. If the HashSet return true for\n                ///  any of the values in the second step that implies that the value was NOT in the subarray, and\n                ///  therefor the subarry cannot be rearranged into an arithmetic sequence.\n                ///  We will try with using a HashSet. First we compute d (the difference between the terms if \n                ///  the subarray can form a valid arithmetic sequence. \n                ///  \n                ///  The computed elements of the arithmetic sequence are:\n                ///  \n                ///  SUB_MIN + 0*d, SUB_MIN + 1*d, SUB_MIN + 2d, ... , SUB_MIN + (n - 1)*d\n                ///  \n                ///**********************************************************************************************/;\n                \n                // Add the terms to the subarray\n                subArrayElements.Clear();\n                for(int j = L_idx; j <= R_idx;j++)\n                {\n                    subArrayElements.Add(nums[j]);\n                }\n\n\n                Diff = (SUB_MAX - SUB_MIN) / ((R_idx - L_idx));      // In a finite arithmetic sequence the difference between adjacent\n                                                                     // terms is given by (Max - Min)/(n - 1)\n                for(int k = 0; k < n; k++)\n                {\n                    if(subArrayElements.Add(SUB_MIN))\n                    {\n                        results[i] = false;\n                        contradictionFound = true;\n                        break;\n                    }\n\n                    SUB_MIN += Diff;\n                }\n\n                if(!contradictionFound)\n                {\n                    results[i] = true;\n                }\n            }\n        }\n\n        return results;\n\n    }\n}\n\n//Constraints:\n\n// n == nums.length\n// m == l.length\n// m == r.length\n// 2 <= n <= 500\n// 1 <= m <= 500\n// 0 <= l[i] < r[i] < n\n// - 10^5 <= nums[i] <= 10^5\n```
['Hash Table', 'Math', 'Number Theory', 'C#']