Intervals Between Identical Elements solution and explanation
9 more videos on this problem
Intervals Between Identical Elements | Leetcode 2121 | Contest 273 | Tricky Linear 🔥🔥🔥🔥Coding Decoded · 19:32 · 1K views
Intervals Between Identical Elements | LeetCode Weekly Contest 273 | Hitesh TripathiCode Era · 14:20 · 1K views
2121. Intervals Between Identical Elements (Leetcode Medium)Programming Live with Larry · 12:21 · 1K views
Intervals between identical elements - Leetcode 2121 - coding interview questionInterview Ready · 13:16 · 847 views
Leetcode Weekly Contest 273 | Problem 2119 , 2120 , 2121 | CONSTRUCTIVE ALGO | CODE EXPLAINERcode Explainer · 21:08 · 516 views
Intervals Between Identical Elements | LeetCode | Weekly Contest 273 | SolutionsWe are Coders · 3:16 · 430 views
【每日一题】LeetCode 2121. Intervals Between Identical ElementsHuifeng Guan · 21:32 · 407 views
Intervals Between Identical Elements (Leetcode Weekly 273)Soumya Bhattacharjee · 4:46 · 351 views
Leetcode 2121 Intervals Between Identical ElementsMath Geeks · 9:55 · 273 views
Leetcode 2121. Intervals Between Identical Elements (Python)Myron yoo · 7:27 · 63 views
The problem
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.length1 <= n <= 1051 <= 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.
def get_intervals(arr):
n = len(arr)
intervals = [0] * n
for i in range(n):
for j in range(n):
if arr[i] == arr[j]:
intervals[i] += abs(i - j)
return intervals
if __name__ == "__main__":
arr = [2, 1, 3, 1, 2, 3, 3]
intervals = get_intervals(arr)
print(intervals)import java.util.Arrays;
public class Intervals {
public static int[] getIntervals(int[] arr) {
int n = arr.length;
int[] intervals = new int[n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (arr[i] == arr[j]) {
intervals[i] += Math.abs(i - j);
}
}
}
return intervals;
}
public static void main(String[] args) {
int[] arr = {2, 1, 3, 1, 2, 3, 3};
int[] intervals = getIntervals(arr);
System.out.println(Arrays.toString(intervals));
}
}#include <iostream>
#include <vector>
#include <cmath>
std::vector<int> getIntervals(const std::vector<int>& arr) {
int n = arr.size();
std::vector<int> intervals(n, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (arr[i] == arr[j]) {
intervals[i] += std::abs(i - j);
}
}
}
return intervals;
}
int main() {
std::vector<int> arr = {2, 1, 3, 1, 2, 3, 3};
std::vector<int> intervals = getIntervals(arr);
for (int val : intervals) {
std::cout << val << " ";
}
return 0;
}function getIntervals(arr) {
let n = arr.length;
let intervals = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (arr[i] === arr[j]) {
intervals[i] += Math.abs(i - j);
}
}
}
return intervals;
}
let arr = [2, 1, 3, 1, 2, 3, 3];
console.log(getIntervals(arr));#include <stdio.h>
#include <stdlib.h>
int* getIntervals(int* arr, int n) {
int* intervals = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
intervals[i] = 0;
for (int j = 0; j < n; ++j) {
if (arr[i] == arr[j]) {
intervals[i] += abs(i - j);
}
}
}
return intervals;
}
int main() {
int arr[] = {2, 1, 3, 1, 2, 3, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int* intervals = getIntervals(arr, n);
for (int i = 0; i < n; ++i) {
printf("%d ", intervals[i]);
}
free(intervals);
return 0;
}using System;
class Program {
static int[] GetIntervals(int[] arr) {
int n = arr.Length;
int[] intervals = new int[n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (arr[i] == arr[j]) {
intervals[i] += Math.Abs(i - j);
}
}
}
return intervals;
}
static void Main() {
int[] arr = {2, 1, 3, 1, 2, 3, 3};
int[] intervals = GetIntervals(arr);
Console.WriteLine(string.Join(" ", intervals));
}
}The naive approach in Python utilizes two nested loops to accumulate interval distances. For each position in the array, it sums up the absolute index differences with all positions having the same value.
Time Complexity: O(n^2), where n is the length of the array.
Space Complexity: O(n) for the intervals list.
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.
def get_intervals(arr):
from collections import defaultdict
n = len(arr)
intervals = [0] * n
index_map = defaultdict(list)
for i, value in enumerate(arr):
index_map[value].append(i)
for i in range(n):
indices = index_map[arr[i]]
for index in indices:
intervals[i] += abs(i - index)
return intervals
arr = [2, 1, 3, 1, 2, 3, 3]
intervals = get_intervals(arr)
print(intervals)import java.util.*;
public class Intervals {
public static int[] getIntervals(int[] arr) {
int n = arr.length;
int[] intervals = new int[n];
Map<Integer, List<Integer>> indexMap = new HashMap<>();
for (int i = 0; i < n; ++i) {
indexMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
for (int i = 0; i < n; ++i) {
List<Integer> indices = indexMap.get(arr[i]);
for (int index : indices) {
intervals[i] += Math.abs(i - index);
}
}
return intervals;
}
public static void main(String[] args) {
int[] arr = {2, 1, 3, 1, 2, 3, 3};
int[] intervals = getIntervals(arr);
System.out.println(Arrays.toString(intervals));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
std::vector<int> getIntervals(const std::vector<int>& arr) {
int n = arr.size();
std::vector<int> intervals(n, 0);
std::unordered_map<int, std::vector<int>> valueIndices;
for (int i = 0; i < n; ++i) {
valueIndices[arr[i]].push_back(i);
}
for (int i = 0; i < n; ++i) {
const std::vector<int>& indices = valueIndices[arr[i]];
for (int idx : indices) {
intervals[i] += std::abs(i - idx);
}
}
return intervals;
}
int main() {
std::vector<int> arr = {2, 1, 3, 1, 2, 3, 3};
std::vector<int> intervals = getIntervals(arr);
for (int val : intervals) {
std::cout << val << " ";
}
return 0;
}function getIntervals(arr) {
let n = arr.length;
let intervals = new Array(n).fill(0);
let indexMap = new Map();
for (let i = 0; i < n; ++i) {
if (!indexMap.has(arr[i])) {
indexMap.set(arr[i], []);
}
indexMap.get(arr[i]).push(i);
}
for (let i = 0; i < n; ++i) {
let indices = indexMap.get(arr[i]);
for (let index of indices) {
intervals[i] += Math.abs(i - index);
}
}
return intervals;
}
let arr = [2, 1, 3, 1, 2, 3, 3];
console.log(getIntervals(arr));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VAL 100000
void fillIntervals(int* arr, int n, int* intervals) {
int* indices[MAX_VAL+1];
int sizes[MAX_VAL+1] = {0};
int capacities[MAX_VAL+1] = {0};
for (int i = 0; i <= MAX_VAL; ++i) indices[i] = NULL;
for (int i = 0; i < n; ++i) {
int val = arr[i];
if (sizes[val] == capacities[val]) {
capacities[val] = capacities[val] == 0 ? 1 : capacities[val] * 2;
indices[val] = realloc(indices[val], capacities[val] * sizeof(int));
}
indices[val][sizes[val]++] = i;
}
for (int i = 0; i < n; ++i) {
int curr = arr[i];
for (int j = 0; j < sizes[curr]; ++j) {
intervals[i] += abs(indices[curr][j] - i);
}
}
for (int i = 0; i <= MAX_VAL; ++i) {
if (indices[i]) free(indices[i]);
}
}
int main() {
int arr[] = {2, 1, 3, 1, 2, 3, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int intervals[n];
for (int i = 0; i < n; ++i) intervals[i] = 0;
fillIntervals(arr, n, intervals);
for (int i = 0; i < n; ++i) {
printf("%d ", intervals[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int[] GetIntervals(int[] arr) {
int n = arr.Length;
int[] intervals = new int[n];
Dictionary<int, List<int>> indexMap = new Dictionary<int, List<int>>();
for (int i = 0; i < n; ++i) {
if (!indexMap.ContainsKey(arr[i])) {
indexMap[arr[i]] = new List<int>();
}
indexMap[arr[i]].Add(i);
}
for (int i = 0; i < n; ++i) {
List<int> indices = indexMap[arr[i]];
foreach (int index in indices) {
intervals[i] += Math.Abs(i - index);
}
}
return intervals;
}
static void Main() {
int[] arr = {2, 1, 3, 1, 2, 3, 3};
int[] intervals = GetIntervals(arr);
Console.WriteLine(string.Join(" ", intervals));
}
}In Python, we utilize a defaultdict to store indices of each unique value, leveraging hash-based grouping for efficient index management and interval calculations in linear time.
Time Complexity: O(n), from list iterations and map operations.
Space Complexity: O(n), for map storage of indices.
Approach 3: Default Approach
func getDistances(arr []int) []int64 {
d := make(map[int][]int)
n := len(arr)
for i, v := range arr {
d[v] = append(d[v], i)
}
ans := make([]int64, n)
for _, v := range d {
m := len(v)
val := 0
for _, e := range v {
val += e
}
val -= m * v[0]
for i, p := range v {
delta := 0
if i >= 1 {
delta = v[i] - v[i-1]
}
val += i*delta - (m-i)*delta
ans[p] = int64(val)
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: O(n^2), where n is the length of the array. |
| Efficient Approach Using HashMap | Time Complexity: O(n), from list iterations and map operations. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Pair Comparison | O(n²) | O(1) | Useful for understanding the distance definition or verifying small inputs |
| HashMap + Prefix Sum | O(n) | O(n) | Best general solution when the array can contain many repeated values |
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.