Introduction

In this blog post, we will explore how to solve the LeetCode problem "2121" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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.

Explanation

Here's the breakdown of the solution:

• Group Indices: The core idea is to group indices by the value they hold in arr. We create a dictionary where keys are the unique values in arr, and values are lists of indices where those values appear.
• Prefix/Suffix Sums: For each group of indices, calculate the sum of intervals using prefix and suffix sums. For a given index i in the group, the sum of intervals to other indices j in the group can be calculated as (i * count_left - sum_left) + (sum_right - i * count_right), where count_left and count_right are the number of elements to the left and right of index i, and sum_left and sum_right are the sums of indices to the left and right of index i.

• Store Results: Store the calculated interval sums in the intervals array at the correct indices.

• Time and Space Complexity: O(n) time complexity, O(n) space complexity.

Code

    def sumOfIntervals(arr):
    n = len(arr)
    intervals = [0] * n
    index_map = {}

    for i in range(n):
        if arr[i] not in index_map:
            index_map[arr[i]] = []
        index_map[arr[i]].append(i)

    for value in index_map:
        indices = index_map[value]
        m = len(indices)
        prefix_sum = [0] * m
        prefix_sum[0] = indices[0]
        for i in range(1, m):
            prefix_sum[i] = prefix_sum[i - 1] + indices[i]

        for i in range(m):
            sum_left = 0 if i == 0 else prefix_sum[i - 1]
            count_left = i
            sum_right = prefix_sum[m - 1] - prefix_sum[i]
            count_right = m - 1 - i

            intervals[indices[i]] = (indices[i] * count_left - sum_left) + (sum_right - indices[i] * count_right)

    return intervals