Skip to main content
Talentd

Intervals Between Identical Elements - Solution & Explanation

MediumArrayHash TablePrefix Sum14 min readAsked at: TuSimple, Wayve
Practice this problem

Problem Statement

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. More formally, the interval between arr[i] and arr[j] is |i - j|.

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].

Note: |x| is the absolute value of x.

 

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

 

Constraints:

  • n == arr.length
  • 1 <= n <= 105
  • 1 <= arr[i] <= 105

 

Note: This question is the same as 2615: Sum of Distances.

Approach Overview

Problem Overview: Given an integer array arr, compute an output array where result[i] equals the sum of distances between index i and every other index j where arr[i] == arr[j]. Distance is the absolute difference |i - j|. The challenge is avoiding repeated work when the same value appears many times.

Approach 1: Naive Pair Comparison (O(n²) time, O(1) extra space)

Check every pair of indices using two nested loops. For each index i, iterate through the entire array and add |i - j| whenever arr[i] == arr[j]. This brute‑force method directly follows the definition of the problem and requires no additional data structures beyond the output array. However, it performs n × n comparisons, which becomes slow when the array grows large. This version is useful for verifying correctness or understanding the distance calculation before optimizing.

Approach 2: HashMap + Prefix Sum Optimization (O(n) time, O(n) space)

The key observation: identical values can be processed together instead of recomputing distances repeatedly. First, group indices by value using a hash table. For each unique number, you get a sorted list of positions where it appears. Distances from a position depend on how many identical elements are on the left and right.

Traverse the index list while maintaining running prefix sums. Suppose the current index in the group is pos[k]. The contribution from elements on the left equals k * pos[k] - prefixSumLeft. The contribution from elements on the right equals prefixSumRight - (m - k - 1) * pos[k], where m is the number of occurrences. These formulas compute total distances using arithmetic rather than iterating over neighbors.

Using this technique turns repeated distance calculations into simple constant‑time updates. Each index participates in exactly one group traversal, producing linear complexity. The method combines array traversal, hash map grouping, and prefix sum accumulation to eliminate redundant work.

Recommended for interviews: Interviewers typically expect the HashMap + prefix sum approach. The brute force version shows you understand the definition of the distance calculation, but it does not scale. The optimized solution demonstrates the ability to group data, reuse prefix sums, and reduce quadratic work to linear time.

Approach 1: Naive Approach

This approach involves iterating through the array and for each element, calculating the sum of intervals by iterating again to find all identical elements. This yields an O(n^2) time complexity, which is inefficient for larger inputs.

In this C program, we initialize an intervals array and iterate over each element. For each element, we run another loop to check for identical elements and calculate the intervals sum, adding it to the intervals array. Finally, we print and free the intervals array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the array.
Space Complexity: O(n) for the intervals array.

Try this approach in the editor →

Approach 2: Efficient Approach Using HashMap

To enhance efficiency, use a HashMap to map each unique value in the array to its indices. Then, for each unique value, calculate interval sums in a linear pass.

This C implementation utilizes an integer-array based hash mapping to track indices of each element value efficiently. Then, iteratively calculates interval sums using these indexed locations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), assuming amortized operations on reallocations are balanced.
Space Complexity: O(n) for storing indices in dynamic arrays.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Approach

Time Complexity: O(n^2), where n is the length of the array.
Space Complexity: O(n) for the intervals array.

Efficient Approach Using HashMap

Time Complexity: O(n), assuming amortized operations on reallocations are balanced.
Space Complexity: O(n) for storing indices in dynamic arrays.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Pair ComparisonO(n²)O(1)Useful for understanding the distance definition or verifying small inputs
HashMap + Prefix SumO(n)O(n)Best general solution when the array can contain many repeated values

Video Solution

Intervals Between Identical Elements | Leetcode 2121 | Contest 273 | Tricky Linear 🔥🔥🔥🔥 • Coding Decoded • 1,855 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Intervals Between Identical Elements easy or hard?
Intervals Between Identical Elements is generally classified as a Medium problem. The difficulty comes from recognizing that repeated distance calculations can be replaced with prefix sum math after grouping identical values.
Intervals Between Identical Elements Python/Java solution
Python and Java implementations typically build a HashMap from value to index list, then iterate through each list while maintaining prefix sums. The formulas for left and right contributions compute the total distance for each index in O(1) time.
How to solve Intervals Between Identical Elements in O(n)?
Store indices of each value in a hash map. For every group of indices, compute prefix sums of positions and use them to calculate left and right distance contributions in constant time per index. This avoids recomputing distances and processes the entire array in linear time.
What is the best approach for Intervals Between Identical Elements?
The most efficient approach groups identical values using a hash map and computes distances with prefix sums. Each group of indices is processed once, and distance contributions are calculated using arithmetic formulas. This reduces the complexity to O(n) time with O(n) space.
Is Intervals Between Identical Elements asked at Google/Amazon/Meta?
Problems involving prefix sums, index grouping, and distance calculations appear frequently in interviews at companies like Google, Amazon, and Meta. This specific pattern—grouping identical elements and using prefix sums—is a common medium-level interview concept.
What data structure is used in Intervals Between Identical Elements?
The main data structure is a hash table that maps each value to a list of indices where it appears. Prefix sums are then applied to those index lists to compute distance totals efficiently. Arrays store both the input and final result.
What is the time complexity of Intervals Between Identical Elements?
The optimal solution runs in O(n) time because each array element is processed a constant number of times while building the hash map and computing prefix sums. Space complexity is O(n) to store index groups and the result array. A naive nested-loop approach takes O(n²) time.

Ready to solve this problem?

Practice Intervals Between Identical Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Continuous Subarray Sum