c++ || 2 Approaches || Beats 97.84 % 🏆
Solution 1: Brute-Force Approach\n\nclass Solution {\npublic:\n    // Function to check if a subarray forms an arithmetic progression\n    bool isap(vector<int>
# **Solution 1: Brute-Force Approach**\n```\nclass Solution {\npublic:\n    // Function to check if a subarray forms an arithmetic progression\n    bool isap(vector<int> &nums,int l,int r)\n    {\n        vector<int> temp;\n        for(int i = l;i<=r;i++)\n        {\n            temp.push_back(nums[i]); // Adding elements to temporary vector\n        }\n        sort(temp.begin(),temp.end()); // Sorting to check for arithmetic progression\n\n        int k = temp[1]-temp[0]; // Difference between first two elements\n        for(int i = 2;i<nums.size();i++)\n        {\n            // Checking if difference is consistent across the array\n            if(temp[i]-temp[i-1] != k)\n                return false;\n        }\n        return true; // Returns true if it\'s an arithmetic progression\n    }\n    \n    // Function to check multiple subarrays\n    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) \n    {\n        vector<bool> ans;\n        for(int i = 0;i<l.size();i++)\n        {\n            // Checking each subarray defined by l[i] and r[i]\n            ans.push_back(isap(nums,l[i],r[i]));\n        }\n        return ans; // Returns a vector of boolean answers\n    }\n};\n\n```\n\n**Explanation of Approach 1: Brute-Force Method**\nThe brute-force approach involves directly checking each subarray to determine if it forms an arithmetic progression. Here\'s a step-by-step breakdown of how this is achieved:\n\n**Subarray Extraction:** For each pair of indices (l[i], r[i]), a subarray is extracted from the main array. This is done in the checkArithmeticSubarrays function. Each subarray is defined by its start (l[i]) and end (r[i]) indices.\n\n**Sorting and Checking:** In the isap function, each extracted subarray is first sorted. Sorting is essential because, in an arithmetic progression, each term (except the first) is obtained by adding a constant to the previous term. Sorting arranges the elements in ascending order, making it easier to check for this constant difference.\n\n**Consistent Difference Check:** After sorting, the function calculates the difference between the first two elements (temp[1] - temp[0]). This difference is expected to be consistent across the subarray for it to qualify as an arithmetic progression. The function iterates through the subarray, comparing the difference between consecutive elements. If any pair of consecutive elements has a different difference, the function returns false, indicating that the subarray does not form an arithmetic progression.\n\n**Results Aggregation:** Finally, the results for each subarray are aggregated into a vector of booleans, indicating whether each subarray is an arithmetic progression.\n\nThis brute-force method is straightforward but can be inefficient for large arrays due to repeated sorting and checking of each subarray.\n\n\n\n# **Solution 2: Optimized Approach**\n\n```\nclass Solution {\npublic:\n    // Function to check if an array is an arithmetic progression\n    bool check(vector<int>& arr) {\n        \n        int maxEl = INT_MIN; // Initialize maximum element\n        int minEl = INT_MAX; // Initialize minimum element\n        int n = arr.size();\n\n        unordered_set<int> s; // Using set for constant time look-up\n        for(auto el : arr){\n            // Finding minimum and maximum elements\n            minEl = min(minEl, el);\n            maxEl = max(maxEl, el);\n            s.insert(el); // Inserting elements in the set\n        }\n\n        // Checking if the difference is consistent\n        if( (maxEl - minEl)%(n-1) != 0) return false;\n        int d = (maxEl - minEl) / (n-1); // Difference between elements\n        int cur = minEl + d; // Starting from second element\n\n        while(cur < maxEl){\n            // Checking each element in the set\n            if(s.find(cur) == s.end()) return false;\n            cur += d;\n        }\n\n        return true; // Returns true if it\'s an arithmetic progression\n    }\n    \n    // Function to check multiple subarrays\n    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n        vector<bool> ans;\n        for (int i = 0; i < l.size(); i++) {\n            vector<int> arr(begin(nums) + l[i], begin(nums) + r[i] + 1);\n            // Checking each subarray\n            ans.push_back(check(arr));\n        }\n        \n        return ans; // Returns a vector of boolean answers\n    }\n};\n\n```\n\n**Explanation of Approach 2: Optimized Method**\nThe optimized solution improves efficiency by avoiding the sorting step and using a hash set for constant-time look-up. Here\'s how it works:\n\n**Preparation:** In the check function, the algorithm first finds the minimum (minEl) and maximum (maxEl) elements of the subarray. It also inserts all elements of the subarray into an unordered_set for efficient element look-up.\n\n**Arithmetic Progression Validation:** The function then checks if the difference between maxEl and minEl is evenly divisible by the size of the subarray minus one ((maxEl - minEl) % (n - 1)). This step is crucial because, in an arithmetic progression, the difference between the maximum and minimum elements should be a multiple of the constant difference multiplied by the number of elements between them.\n\n**Consistency Check Using Set:** After calculating the expected difference (d), the algorithm iterates from the minimum element to the maximum element in steps of d. At each step, it checks if the current element exists in the set. If any expected element is missing, the function returns false.\n\n**Results Aggregation:** Similar to the first approach, the results for each subarray check are collected into a boolean vector and returned.\n\nThis optimized approach is more efficient, especially for larger arrays, as it avoids sorting and leverages the constant-time look-up feature of hash sets.
['Array', 'C', 'Sorting']