LeetCode 2121 - Intervals Between Identical Elements

You are given a 0-indexed integer array arr. For every index i, you must compute the sum of distances between i and every other index j where arr[i] == arr[j].

leetcodemediumarrayhash-tableprefix-sum

LeetCode Problem 2121

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

LeetCode 2121 - Intervals Between Identical Elements

Problem Statement

You are given a 0-indexed integer array arr. For every index i, you must compute the sum of distances between i and every other index j where arr[i] == arr[j].

The distance between two indices is the absolute difference of their positions:

$$|i - j|$$

The result should be an array intervals where:

  • intervals[i] equals the sum of distances from index i to all other indices containing the same value.

If a value appears only once in the array, then its interval sum is 0 because there are no other matching indices.

The challenge is that the array size can be as large as 10^5, so an inefficient pairwise comparison solution will time out.

Problem Understanding

The input array represents values placed at specific indices. For each position, we are only interested in other positions containing the exact same value.

Suppose the array is:

[2,1,3,1,2,3,3]

For index 2, the value is 3. The other occurrences of 3 are at indices 5 and 6. The answer for index 2 is:

$$|2 - 5| + |2 - 6| = 3 + 4 = 7$$

This must be computed for every position.

The constraints are important:

  • n can be 100000
  • A naive nested loop over all pairs would require up to 10^10 comparisons in the worst case

That is far too slow, so we need a more efficient strategy.

Several edge cases are important:

  • Arrays where every element is unique
  • Arrays where all elements are identical
  • Large groups of repeated values
  • Values appearing only twice
  • Very large interval sums that require 64-bit integers in Go

The problem guarantees:

  • The array is non-empty
  • Values are positive integers
  • Array length fits within memory limits

Approaches

Brute Force Approach

The most direct solution is to compare every index with every other index.

For each position i:

  1. Iterate through all indices j
  2. If arr[i] == arr[j] and i != j
  3. Add |i - j| to the answer

This works because it explicitly computes every required interval.

However, the time complexity is extremely poor. For every index, we scan the entire array again, producing an O(n^2) solution.

With n = 100000, this becomes infeasible.

Optimal Approach

The key observation is that indices with the same value can be grouped together.

For example:

Value 3 appears at indices [2,5,6]

Instead of recomputing distances repeatedly, we can process the entire group efficiently using prefix sums.

Consider an index list:

positions = [p0, p1, p2, ..., pk]

For a position positions[i], we want:

sum of distances to all positions on the left
+
sum of distances to all positions on the right

Because the indices are naturally sorted, we can compute these sums using arithmetic and prefix sums in constant time per index.

This reduces the total complexity to linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compare every pair of indices
Optimal O(n) O(n) Group indices and use prefix sum math

Algorithm Walkthrough

Step 1: Group Indices by Value

Create a hash map where:

  • Key = array value
  • Value = list of indices where that value appears

Example:

arr = [2,1,3,1,2,3,3]

groups = {
    2: [0,4],
    1: [1,3],
    3: [2,5,6]
}

This lets us process each repeated value independently.

Step 2: Initialize the Result Array

Create a result array of length n initialized with zeros.

result = [0] * n

Each entry will eventually contain the interval sum for that index.

Step 3: Process Each Group

For each list of indices:

positions = [p0, p1, p2, ..., pk]

compute interval sums efficiently.

Step 4: Build Prefix Sums

Create a running prefix sum array over the positions.

For example:

positions = [2,5,6]

prefix = [2,7,13]

This allows fast range sum calculations.

Step 5: Compute Left Contribution

For index i:

left_distance =
positions[i] * i - sum(left positions)

Why this works:

If current position is x, and there are i positions before it:

(x - p0) + (x - p1) + ... + (x - p(i-1))
=
i*x - sum(previous positions)

Step 6: Compute Right Contribution

Similarly:

right_distance =
sum(right positions) - positions[i] * right_count

This computes:

(p(i+1) - x) + (p(i+2) - x) + ...

Step 7: Store Final Answer

Add both contributions:

result[positions[i]] = left_distance + right_distance

Repeat for every group.

Why it works

For every value, all matching indices are sorted naturally because we traverse the array from left to right.

For a fixed index, every distance can be separated into:

  • Distances to indices on the left
  • Distances to indices on the right

Prefix sums allow both quantities to be computed in constant time.

Since every index belongs to exactly one group and is processed once, the algorithm computes all interval sums correctly and efficiently.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def getDistances(self, arr: List[int]) -> List[int]:
        index_groups = defaultdict(list)

        for index, value in enumerate(arr):
            index_groups[value].append(index)

        result = [0] * len(arr)

        for positions in index_groups.values():
            size = len(positions)

            prefix = [0] * size
            prefix[0] = positions[0]

            for i in range(1, size):
                prefix[i] = prefix[i - 1] + positions[i]

            total_sum = prefix[-1]

            for i, position in enumerate(positions):
                left_sum = prefix[i - 1] if i > 0 else 0
                left_count = i

                right_sum = total_sum - prefix[i]
                right_count = size - i - 1

                left_distance = position * left_count - left_sum
                right_distance = right_sum - position * right_count

                result[position] = left_distance + right_distance

        return result

The implementation begins by grouping all indices according to their values using a defaultdict.

Each value maps to a sorted list of positions where it appears.

Next, for every group, we build a prefix sum array. The prefix sum enables constant time computation of sums over ranges of indices.

For every position in the group:

  • The left contribution measures distances to earlier indices
  • The right contribution measures distances to later indices

These contributions are computed mathematically instead of iterating through all matching indices.

Finally, the computed interval sum is stored directly in the result array.

Go Solution

func getDistances(arr []int) []int64 {
	indexGroups := make(map[int][]int)

	for index, value := range arr {
		indexGroups[value] = append(indexGroups[value], index)
	}

	result := make([]int64, len(arr))

	for _, positions := range indexGroups {
		size := len(positions)

		prefix := make([]int64, size)
		prefix[0] = int64(positions[0])

		for i := 1; i < size; i++ {
			prefix[i] = prefix[i-1] + int64(positions[i])
		}

		totalSum := prefix[size-1]

		for i, position := range positions {
			var leftSum int64
			if i > 0 {
				leftSum = prefix[i-1]
			}

			leftCount := int64(i)

			rightSum := totalSum - prefix[i]
			rightCount := int64(size - i - 1)

			leftDistance := int64(position)*leftCount - leftSum
			rightDistance := rightSum - int64(position)*rightCount

			result[position] = leftDistance + rightDistance
		}
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version.

The main difference is integer handling. Since interval sums can exceed the range of a 32-bit integer, the result array and prefix sums use int64.

Slices are used for dynamic index grouping, and Go maps provide efficient value-to-index-list storage.

Worked Examples

Example 1

Input: [2,1,3,1,2,3,3]

Grouped Indices

Value Positions
2 [0,4]
1 [1,3]
3 [2,5,6]

Processing Value 2

positions = [0,4]
prefix = [0,4]
i position left_distance right_distance result
0 0 0 4 4
1 4 4 0 4

Processing Value 1

positions = [1,3]
prefix = [1,4]
i position left_distance right_distance result
0 1 0 2 2
1 3 2 0 2

Processing Value 3

positions = [2,5,6]
prefix = [2,7,13]
i position left_distance right_distance result
0 2 0 7 7
1 5 3 1 4
2 6 5 0 5

Final result:

[4,2,7,2,4,4,5]

Example 2

Input: [10,5,10,10]

Grouped Indices

Value Positions
10 [0,2,3]
5 [1]

Processing Value 10

positions = [0,2,3]
prefix = [0,2,5]
i position left_distance right_distance result
0 0 0 5 5
1 2 2 1 3
2 3 4 0 4

Processing Value 5

Only one occurrence exists, so:

result[1] = 0

Final result:

[5,0,3,4]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every index is processed a constant number of times
Space O(n) Hash map and prefix sums store up to n indices

The grouping step visits every array element once.

The prefix sum computation and interval calculations also process each index once across all groups.

No nested processing over the entire array occurs, which keeps the algorithm linear.

Test Cases

sol = Solution()

# Provided examples
assert sol.getDistances([2,1,3,1,2,3,3]) == [4,2,7,2,4,4,5]  # mixed duplicates
assert sol.getDistances([10,5,10,10]) == [5,0,3,4]  # single unique value

# Single element
assert sol.getDistances([1]) == [0]  # minimum size input

# All unique
assert sol.getDistances([1,2,3,4]) == [0,0,0,0]  # no duplicates

# All identical
assert sol.getDistances([5,5,5,5]) == [6,4,4,6]  # every index connected

# Two identical values
assert sol.getDistances([7,1,7]) == [2,0,2]  # simple pair

# Consecutive duplicates
assert sol.getDistances([1,1,1]) == [3,2,3]  # dense repeated group

# Large spacing
assert sol.getDistances([1,2,1,2,1]) == [6,2,4,2,6]  # alternating duplicates

# Multiple groups
assert sol.getDistances([4,4,2,2,4]) == [5,4,1,1,7]  # several repeated groups

# Large duplicate cluster
assert sol.getDistances([9,9,9,9,9]) == [10,7,6,7,10]  # symmetric distances

Test Case Summary

Test Why
[2,1,3,1,2,3,3] Standard mixed example
[10,5,10,10] Includes a value appearing once
[1] Minimum input size
[1,2,3,4] No duplicates anywhere
[5,5,5,5] Every element identical
[7,1,7] Small repeated pair
[1,1,1] Consecutive duplicates
[1,2,1,2,1] Alternating repeated values
[4,4,2,2,4] Multiple duplicate groups
[9,9,9,9,9] Large symmetric cluster

Edge Cases

Single Element Array

If the array contains only one element, there are no other matching indices. A naive implementation might accidentally attempt invalid prefix calculations or out-of-range access.

The implementation handles this naturally because the grouped positions list has size 1, producing both left and right contributions equal to 0.

All Elements Unique

When every value appears exactly once, every interval sum should be 0.

Some implementations mistakenly attempt unnecessary computations or assume at least two positions per group.

Here, each group contains exactly one index, so both left and right counts become zero automatically.

All Elements Identical

This is an important stress case because every index contributes to every other index.

A brute-force solution becomes extremely slow here since it computes all pairwise distances.

The optimized solution still runs in linear time because it processes the sorted index list once using prefix sums.

Large Interval Sums

For large arrays with many duplicates, interval totals can exceed 32-bit integer limits.

The Go implementation explicitly uses int64 for:

  • Prefix sums
  • Distance calculations
  • Final results

This prevents integer overflow and ensures correctness for maximum constraints.