We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Intervals Between Identical Elements

Number: 2240

Difficulty: Medium

Paid? No

Companies: TuSimple, Wayve

Problem Description

Given a 0-indexed integer array arr, for every index i you must compute the sum of the absolute differences (intervals) between i and every other index where the value is equal to arr[i]. In other words, for each position, sum |i - j| for all indices j (j ≠ i) such that arr[j] == arr[i].

Key Insights

  • Group array indices by their corresponding value.
  • Use prefix sums to efficiently calculate the sum of intervals for indices in each group.
  • For each sorted group, for an index at position i in the group, the contribution from indices to its left and right can be computed in O(1) time using prefix sums.
  • The final answer for each index is computed by combining distances from left and right within its group.

Space and Time Complexity

Time Complexity: O(n) – Each element is processed once and each group’s intervals are computed in linear time. Space Complexity: O(n) – Additional space is used for storing groups and prefix sums over indices.

Solution

The solution groups indices by their array value using a hash table (or dictionary). For each group (which corresponds to a unique value), the indices are processed in sorted order. A prefix sum array is computed for the group. For each index at position i in the group, the sum of distances to the left is i * current_index - (sum of indices before i) and the sum of distances to the right is (sum of indices after i) - current_index * (number of indices to the right). The sum of these two values is the required output for that index. The computed intervals are stored in the result array.

Code Solutions

def getIntervalSums(arr):
    # Group indices by the corresponding array value.
    groups = {}
    for i, num in enumerate(arr):
        if num not in groups:
            groups[num] = []
        groups[num].append(i)
        
    result = [0] * len(arr)
    
    # Process each group independently.
    for indices in groups.values():
        size = len(indices)
        # Compute prefix sum for the current group's indices.
        prefixSum = [0] * size
        prefixSum[0] = indices[0]
        for i in range(1, size):
            prefixSum[i] = prefixSum[i - 1] + indices[i]
        total = prefixSum[-1]  # Total sum of indices in this group
        
        # Compute interval sums for each index in the group.
        for i, index in enumerate(indices):
            left_count = i
            right_count = size - i - 1
            left_sum = prefixSum[i - 1] if i > 0 else 0
            right_sum = total - prefixSum[i]
            # Calculate total intervals as difference contributions from left and right segments.
            result[index] = (index * left_count - left_sum) + (right_sum - index * right_count)
            
    return result

# Example usage:
arr = [2, 1, 3, 1, 2, 3, 3]
print(getIntervalSums(arr))  # Expected output: [4,2,7,2,4,4,5]
← Back to All Questions