Sum Of Distances

Problem statement

We are given a 0-indexed integer array nums. There exists an array arr of length nums. length, where arr[i] is the sum of |i - j| overall j such that nums[j] == nums[i] and j != i. If there is no such j, set arr[i] to be 0.

Return the array arr.

Java Implementation

Java Approach Using Brute Force

Output:

Code Explanation:

• The given Java code defines a Solution class with a distance method to calculate distances for each element in an array. It utilizes a map to store the indices of each array element, allowing efficient access to these indices during distance calculation. The main function prompts the user for the array's length and elements, then calls the distance method and outputs the calculated distances.
• For each array element, it checks if the element occurs more than once, and if so, it computes the distances from the current index to all other occurrences. The resulting distances are stored in the 'result' array, which is then printed.

Time Complexity:

• The time complexity of the given code is O(N^2), where N is the length of the input array 'nums.' This is because, for each element in the array, the code may iterate over all other occurrences of the same element to calculate distances.

Space complexity:

• The space complexity is O(N) due to the additional space required to store indices in the map. The map may have up to N entries in the worst case, where each entry is associated with a list of indices. The 'result' array, also of size N, contributes to the overall space complexity.

Java Approach Using Prefix Sum

Output:

Code Explanation:

• The code calculates the distances between occurrences of elements in an array. It uses a HashMap to store the indices for each unique element. For each element, it computes the distances based on a formula using the indices and updates the result array. If an element occurs only once, its distance is set to 0.
• The code efficiently handles multiple occurrences by precomputing the sum of indices. It iterates through the indices, updating left and right sums to calculate the distances.

Time complexity:

• The time complexity is O(N), where N is the length of the input array. The algorithm processes each element once, resulting in linear time complexity.

Space complexity:

• The space complexity is O(N) as it uses a HashMap to store indices, with additional space proportional to the length N of the input array.

Java Implementation Using Binary Search

Output:

Code Explanation:

• The above solution aims to calculate the distances between each element and its occurrences in an array. It uses two HashMaps: one to store the indices of each element and the other to store the prefix sums of indices for each element.
• It iterates through the array, performs a binary search to find the index of the current element in its occurrences, and then calculates the distances using the prefix sums and indices. The distances are stored in the result array.
• Special cases are considered, such as elements occurring only once, where the distance is set to 0.

Time Complexity:

• The solution iterates through the array once and performs binary searches, resulting in O(N log N), where N is the length of the array.

Space Complexity:

• The space complexity is O(N), where N is the length of the array due to the HashMaps used to store indices and prefix sums for each element.