Find minimum value of arr[j] + abs(j – i) for all indices
Given an array arr[] of size N, the task is for each index i (1≤i≤n) find it’s minimum value, that can be calculated by the formula (arr[j] + abs(j−i)), for 0<=j<n and j != i.
Examples:
Input: arr = { 1, 3, 11, 2, 15, 7, 5 }
Output: 4 2 3 4 3 4 5
Explanation:
- For i = 0, the minimum value is for j = 1, arr[1] + abs(1 – 0) = 3 + 1 = 4
- For i = 1, the minimum value is for j = 0, arr[0] + abs(0 – 1) = 1 + 1 = 2
- For i = 2, the minimum value is for j = 3, arr[3] + abs(3 – 2) = 2 + 1 = 3
- For i = 3, the minimum value is for j = 1, arr[1] + abs(1 – 3) = 2 + 2 = 4
- For i = 4, the minimum value is for j = 3, arr[3] + abs(3 – 4) = 2 + 1 = 3
- For i = 5, the minimum value is for j = 3, arr[3] + abs(3 – 5) = 2 + 2 = 4
- For i = 6, the minimum value is for j = 3, arr[3] + abs(3 – 6) = 2 + 3 = 5.
Input: arr = { 1, 1}
Output: 2 2
Approach: To solve the problem, follow the below idea:
Let assume if jth element is on right of ith element then the equation would be (aj + j) – i, if the jth element is on left of ith element then the equation would be (aj – j) + i. So, to compute the minimum value of these two cases, we need to precompute the value in following way:
- for case j > i: we need to keep track of all the element which are on the right side in such a way that we can get minimum value of (aj + j) in O(1) time. So, we can use prefix sum technique to keep track of minimum value at each index.
- for case i > j: we need to keep track of all the element which are on the left side in such a way that we can get minimum value of (aj – j) in O(1) time. So, we can use prefix sum technique to keep track of minimum value at each index.
Finally, we would minimize the result of both cases and add into our result for each value of i.
Step-by-step algorithm:
- Initialize two vectors addSet and diffSet to store the minimum differences for each element based on the two possible rotations.
- Calculate the minimum differences for the addSet vector by traversing the array from the end.
- Calculate the minimum differences for the diffSet vector by traversing the array from the beginning.
- Create a result vector and add the minimum difference for the first element.
- Calculate the minimum difference for the remaining elements by taking the minimum of the difference between the current element and the previous element, and the difference between the next element and the current element.
- Add the minimum difference for the last element to the result vector.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// aj + (j - i) => (aj + j) - i
// aj - j + i => (aj - j) + i
// function to find the answer
vector<int> solve(vector<int>& arr)
{
int n = arr.size();
// Create two vectors to store the minimum differences
// for each element based on the two possible rotations
vector<int> addSet(n), diffSet(n);
// Initialize the last element of the addSet vector
addSet[n - 1] = arr[n - 1] + n - 1;
// Initialize the first element of the diffSet vector
diffSet[0] = arr[0] - 0;
// Calculate the minimum differences for the addSet
// vector
for (int i = n - 2; i >= 0; i--) {
addSet[i] = min(arr[i] + i, addSet[i + 1]);
}
// Calculate the minimum differences for the diffSet
// vector
for (int i = 1; i < n; i++) {
diffSet[i] = min(arr[i] - i, diffSet[i - 1]);
}
// Create a result vector to store the minimum
// differences for each element
vector<int> result;
// Add the minimum difference for the first element
result.push_back(addSet[1] - 0);
// Calculate the minimum differences for the remaining
// elements
for (int i = 1; i < n - 1; i++) {
int res
= min(diffSet[i - 1] + i, addSet[i + 1] - i);
result.push_back(res);
}
// Add the minimum difference for the last element
result.push_back(diffSet[n - 2] + n - 1);
// Return the result vector
return result;
}
int main()
{
// Example array
vector<int> arr = { 1, 3, 11, 2, 15, 7, 5 };
// Call the solve function to find the minimum
// differences
vector<int> result = solve(arr);
// Print the minimum differences
for (auto i : result) {
cout << i << " ";
}
return 0;
}
import java.util.*;
public class Solution {
// Function to find the answer
public static List<Integer> solve(List<Integer> arr)
{
int n = arr.size();
// Create two arrays to store the minimum
// differences for each element based on the two
// possible rotations
int[] addSet = new int[n];
int[] diffSet = new int[n];
// Initialize the last element of the addSet array
addSet[n - 1] = arr.get(n - 1) + n - 1;
// Initialize the first element of the diffSet array
diffSet[0] = arr.get(0) - 0;
// Calculate the minimum differences for the addSet
// array
for (int i = n - 2; i >= 0; i--) {
addSet[i]
= Math.min(arr.get(i) + i, addSet[i + 1]);
}
// Calculate the minimum differences for the diffSet
// array
for (int i = 1; i < n; i++) {
diffSet[i]
= Math.min(arr.get(i) - i, diffSet[i - 1]);
}
// Create a result list to store the minimum
// differences for each element
List<Integer> result = new ArrayList<>();
// Add the minimum difference for the first element
result.add(addSet[1] - 0);
// Calculate the minimum differences for the
// remaining elements
for (int i = 1; i < n - 1; i++) {
int res = Math.min(diffSet[i - 1] + i,
addSet[i + 1] - i);
result.add(res);
}
// Add the minimum difference for the last element
result.add(diffSet[n - 2] + n - 1);
// Return the result list
return result;
}
public static void main(String[] args)
{
// Example array
List<Integer> arr
= Arrays.asList(1, 3, 11, 2, 15, 7, 5);
// Call the solve function to find the minimum
// differences
List<Integer> result = solve(arr);
// Print the minimum differences
for (int i : result) {
System.out.print(i + " ");
}
}
}
// This code is contributed by Shivam Gupta
def solve(arr):
n = len(arr)
# Create two arrays to store the minimum
# differences for each element based on the two
# possible rotations
add_set = [0] * n
diff_set = [0] * n
# Initialize the last element of the addSet array
add_set[n - 1] = arr[-1] + n - 1
# Initialize the first element of the diffSet array
diff_set[0] = arr[0] - 0
# Calculate the minimum differences for the add_set array
for i in range(n - 2, -1, -1):
add_set[i] = min(arr[i] + i, add_set[i + 1])
# Calculate the minimum differences for the diff_set array
for i in range(1, n):
diff_set[i] = min(arr[i] - i, diff_set[i - 1])
# Create a result list to store the minimum
# differences for each element
result = []
# Add the minimum difference for the first element
result.append(add_set[1] - 0)
# Calculate the minimum differences for the remaining elements
for i in range(1, n - 1):
res = min(diff_set[i - 1] + i, add_set[i + 1] - i)
result.append(res)
# Add the minimum difference for the last element
result.append(diff_set[n - 2] + n - 1)
# Return the result list
return result
# Example array
arr = [1, 3, 11, 2, 15, 7, 5]
# Call the solve function to find the minimum differences
result = solve(arr)
# Print the minimum differences
for i in result:
print(i, end=" ")
// Function to find the minimum differences for each element in the array
function solve(arr) {
const n = arr.length;
// Create two arrays to store the minimum differences
// for each element based on the two possible rotations
const addSet = new Array(n), diffSet = new Array(n);
// Initialize the last element of the addSet array
addSet[n - 1] = arr[n - 1] + n - 1;
// Initialize the first element of the diffSet array
diffSet[0] = arr[0] - 0;
// Calculate the minimum differences for the addSet array
for (let i = n - 2; i >= 0; i--) {
addSet[i] = Math.min(arr[i] + i, addSet[i + 1]);
}
// Calculate the minimum differences for the diffSet array
for (let i = 1; i < n; i++) {
diffSet[i] = Math.min(arr[i] - i, diffSet[i - 1]);
}
// Create a result array to store the minimum differences for each element
const result = [];
// Add the minimum difference for the first element
result.push(addSet[1] - 0);
// Calculate the minimum differences for the remaining elements
for (let i = 1; i < n - 1; i++) {
const res = Math.min(diffSet[i - 1] + i, addSet[i + 1] - i);
result.push(res);
}
// Add the minimum difference for the last element
result.push(diffSet[n - 2] + n - 1);
// Return the result array
return result;
}
// Main function
function main() {
// Example array
const arr = [1, 3, 11, 2, 15, 7, 5];
// Call the solve function to find the minimum differences
const result = solve(arr);
// Print the minimum differences
console.log(result.join(" "));
}
// Call the main function to execute the example usage
main();
Output
4 2 3 4 3 4 5
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us