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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Intervals Between Identical Elements

Difficulty: Medium

Problem Description

You are given a 0-indexed array of n integers arr. The interval between two elements in arr is defined as the absolute difference between their indices. Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Key Insights

  • The problem requires calculating the sum of absolute differences in indices for identical elements in the array.
  • We can efficiently track the indices of each unique value in arr using a hash map.
  • By iterating through the list of indices for each unique value, we can compute the sum of intervals in a single pass.
  • Prefix sums can be utilized to quickly compute the sum of intervals for each index based on previously calculated values.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a hash map to group indices of identical elements. For each unique value in the array, we will compute the sum of intervals using the formula for calculating distances based on the prefix sums of indices.

  1. Create a hash map to store indices of each unique value.
  2. For each unique value, calculate the total distance for each index using prefix sums.
  3. Store the results in the final output array.

Code Solutions

def get_intervals(arr):
    from collections import defaultdict
    
    index_map = defaultdict(list)
    
    # Step 1: Populate the index map
    for i, num in enumerate(arr):
        index_map[num].append(i)

    # Step 2: Initialize the result array
    n = len(arr)
    intervals = [0] * n

    # Step 3: Calculate intervals for each unique number
    for indices in index_map.values():
        prefix_sum = 0
        total_count = len(indices)
        
        for i in range(total_count):
            idx = indices[i]
            # Calculate the sum of intervals for arr[idx]
            intervals[idx] = (idx * i - prefix_sum) + ((total_count - i - 1) * idx - (prefix_sum - (total_count - i - 1) * idx))
            prefix_sum += idx

    return intervals
← Back to All Questions