Arithmetic Subarrays

class Solution {
public:
    bool checkArithmetic(vector<int>& sequence) {
        int smallest = INT_MAX;
        int largest = INT_MIN;
        unordered_set<int> elements;
        
        for (int value : sequence) {
            smallest = min(smallest, value);
            largest = max(largest, value);
            elements.insert(value);
        }
        
        if ((largest - smallest) % (sequence.size() - 1) != 0) {
            return false;
        }
        
        int commonDifference = (largest - smallest) / (sequence.size() - 1);
        int nextTerm = smallest + commonDifference;
        
        while (nextTerm < largest) {
            if (elements.find(nextTerm) == elements.end()) {
                return false;
            }
            
            nextTerm += commonDifference;
        }
        
        return true;
    }
    
    vector<bool> evaluateSubarrays(vector<int>& data, vector<int>& starts, vector<int>& ends) {
        vector<bool> results;
        for (int j = 0; j < starts.size(); j++) {
            vector<int> subarray(begin(data) + starts[j], begin(data) + ends[j] + 1);
            results.push_back(checkArithmetic(subarray));
        }
        
        return results;
    }
};

This solution tackles the problem of determining if specific subarrays from a given array are arithmetic sequences. The solution is implemented in C++ and consists of two primary functions within the Solution class.

• In the checkArithmetic function:

  • You calculate the smallest and largest values in the subarray.
  • Determine the possible common difference for an arithmetic progression using these values.
  • Validate that each term of the constructed sequence exists in the original subarray.
  • Return true only if the subarray forms an arithmetic sequence; otherwise, false.

• In the evaluateSubarrays function:

  • Extract each subarray based on provided starting and ending indices.
  • Utilize the checkArithmetic function to evaluate each subarray.
  • Collect and return the results as a vector of boolean values indicating if the corresponding subarrays are arithmetic or not.

This approach ensures efficient checking by leveraging hash sets for quick look-up and arithmetic validations. The solution effectively handles multiple subarrays in a single function call, making it suitable for batch processing scenarios.

class Solution {
    public Boolean verifySequence(int[] sequence) {
        int smallest = Integer.MAX_VALUE;
        int largest = Integer.MIN_VALUE;
        Set<Integer> sequenceSet = new HashSet();
        
        for (int value : sequence) {
            smallest = Math.min(smallest, value);
            largest = Math.max(largest, value);
            sequenceSet.add(value);
        }
        
        if ((largest - smallest) % (sequence.length - 1) != 0) {
            return false;
        }
        
        int commonDifference = (largest - smallest) / (sequence.length - 1);
        int currentNum = smallest + commonDifference;
        
        while (currentNum < largest) {
            if (!sequenceSet.contains(currentNum)) {
                return false;
            }
            
            currentNum += commonDifference;
        }
        
        return true;
    }
    
    public List<Boolean> confirmArithmeticSubarrays(int[] numbers, int[] start, int[] end) {
        List<Boolean> results = new ArrayList();
        for (int i = 0; i < start.length; i++) {
            int[] subarray = new int[end[i] - start[i] + 1];
            for (int j = 0; j < subarray.length; j++) {
                subarray[j] = numbers[start[i] + j];
            }
            
            results.add(verifySequence(subarray));
        }

        return results;
    }
}

This solution in Java addresses the problem of determining if given subarrays are arithmetic sequences or not. The process involves two main methods: verifySequence and confirmArithmeticSubarrays.

• verifySequence Method:

  • This method checks if a single array sequence is an arithmetic series.
  • First, identify the smallest and largest elements in the sequence and also store all elements in a HashSet for fast access.
  • Evaluate if the range (largest - smallest) is evenly divisible by the length of the sequence minus one. If not, the function returns false.
  • Calculate the common difference. Move from the smallest to the largest expected value, checking presence of each expected element (using the common difference) in the set. If an expected element is missing, return false.
  • If all expected values are found in the set, return true.

• confirmArithmeticSubarrays Method:

  • Takes the full array numbers and arrays start and end defining the indices of subarrays.
  • Iterates through each indicated subarray. Constructs the subarray using the start and end indices.
  • For each subarray, leverages verifySequence to determine if it forms an arithmetic sequence, storing the result (true or false) in a list.
  • Returns a list of Boolean values representing if each subarray from the input is arithmetic or not.

This comprehensive approach ensures the solution efficiently evaluates multiple subarrays for arithmetic properties leveraging mathematical checks and optimal data structure usage for element lookup.

class Solution:
    def isArithmetic(self, numbers: List[int], starts: List[int], ends: List[int]) -> List[bool]:
        def isSequence(subarray):
            lowest = min(subarray)
            highest = max(subarray)

            if (highest - lowest) % (len(subarray) - 1) != 0:
                return False
            
            interval = (highest - lowest) / (len(subarray) - 1)
            visited = set(subarray)
            next_val = lowest + interval
            while next_val < highest:
                if next_val not in visited:
                    return False
                next_val += interval
            
            return True

        result = []
        for index in range(len(starts)):
            subset = numbers[starts[index] : ends[index] + 1]
            result.append(isSequence(subset))
        
        return result

The Python3 code provided defines a method to check if slices of an array are arithmetic sequences. Here's a structured summary of how the provided solution works:

• The function isArithmetic receives three parameters: numbers, starts, and ends. These correspond to the main list of integers and lists indicating the starting and ending indices of the subarrays whose arithmetic property needs to be verified.

• An inner function isSequence is defined to determine if a given subarray is an arithmetic sequence. To qualify as an arithmetic sequence:

  • Calculate the difference (interval) between the maximum and minimum value of the subarray divided by the length of the subarray minus one.
  • The range of values in the sequence, starting from the minimum value and adding the interval each time, should exactly match the values in the subarray without any values missing between them.

• The mechanism of checking involves:

  • Initializing an empty list result.
  • Iterating through the indices provided by starts and ends to slice the numbers list and get each subarray.
  • Each subarray is passed to the isSequence function to check if it is an arithmetic sequence.
  • The results (True or False) are collected into the result list.

• Finally, the result list, which contains the Boolean values indicating whether each respective subarray is an arithmetic sequence or not, is returned.

This approach ensures checking each requested subarray for the arithmetic sequence property by utilizing slicing and set operations, efficiently determining if the necessary conditions are met.