Modify array by replacing every array element with minimum possible value of arr[j] + |j – i|

Namachila October 13, 2025

0 0 9 minutes read

Given an array arr[] of size N, the task is to find a value for each index such that the value at index i is arr[j] + |j – i| where 1 ? j ? N, the task is to find the minimum value for each index from 1 to N.

Example:

Input: N = 5, arr[] = {1, 4, 2, 5, 3}
Output: {1, 2, 2, 3, 3}
Explanation:
arr[0] = arr[0] + |0-0| = 1
arr[1] = arr[0] + |0-1| = 2
arr[2] = arr[2] + |2-2| = 2
arr[3] = arr[2] + |2-3| = 3
arr[4] = arr[4] + |4-4| = 3
The output array will give minimum value at every i^th position.

Input: N = 4, arr[] = {1, 2, 3, 4}
Output: {1, 2, 3, 4}

Naive Approach: The idea is to use two nested for loops for traversing the array and for each i^th index, find and print the minimum value of arr[j] + |i-j|.

Implementation :

C++

#include <bits/stdc++.h>
using namespace std;
 
// function that prints the minimum possible 
// value of arr[j] + |j - i|
void minAtEachIndex(int n, int arr[]) {
    // loop to modify every element
    for(int i = 0; i < n; i++) {
        // to get the minimum value for current ith element
        int minValue = INT_MAX;
        // to find the minimum value in range [1,N-1]
        for(int j = 0; j < n; j++) {
            // compute value and update minimum value
            int val = arr[j] + abs(i-j);
            if(val < minValue) {
                minValue = val;
            }
        }
        // print minimum value
        cout << minValue << " ";
    }
    return;
}
 
//Driver code
int main() {
    int arr[] = {1, 4, 2, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    // function call
    minAtEachIndex(n, arr);
    return 0;
}
 
// this code is contributed by bhardwajji

Java

import java.util.*;
 
public class Main {
// function that prints the minimum possible
// value of arr[j] + |j - i|
public static void minAtEachIndex(int n, int[] arr) {
// loop to modify every element
for (int i = 0; i < n; i++) {
// to get the minimum value for current ith element
int minValue = Integer.MAX_VALUE;
// to find the minimum value in range [1,N-1]
for (int j = 0; j < n; j++) {
// compute value and update minimum value
int val = arr[j] + Math.abs(i - j);
if (val < minValue) {
minValue = val;
}
}
// print minimum value
System.out.print(minValue + " ");
}
return;
}
// Driver code
public static void main(String[] args) {
    int arr[] = {1, 4, 2, 5, 3};
    int n = arr.length;
    // function call
    minAtEachIndex(n, arr);
}
}

Python3

import sys
 
# function that prints the minimum possible 
# value of arr[j] + |j - i|
def minAtEachIndex(n, arr):
   
    # loop to modify every element
    for i in range(n):
       
        # to get the minimum value for current ith element
        minValue = sys.maxsize
         
        # to find the minimum value in range [1,N-1]
        for j in range(n):
           
            # compute value and update minimum value
            val = arr[j] + abs(i-j)
            if val < minValue:
                minValue = val
                 
        # print minimum value
        print(minValue, end=' ')
    return
 
# Driver code
if __name__ == '__main__':
    arr = [1, 4, 2, 5, 3]
    n = len(arr)
     
    # function call
    minAtEachIndex(n, arr)

C#

using System;
 
class Program {
    // function that prints the minimum possible 
    // value of arr[j] + |j - i|
    static void minAtEachIndex(int n, int[] arr) {
        // loop to modify every element
        for(int i = 0; i < n; i++) {
            // to get the minimum value for current ith element
            int minValue = int.MaxValue;
            // to find the minimum value in range [1,N-1]
            for(int j = 0; j < n; j++) {
                // compute value and update minimum value
                int val = arr[j] + Math.Abs(i-j);
                if(val < minValue) {
                    minValue = val;
                }
            }
            // print minimum value
            Console.Write(minValue + " ");
        }
    }
 
    //Driver code
    static void Main() {
        int[] arr = {1, 4, 2, 5, 3};
        int n = arr.Length;
        // function call
        minAtEachIndex(n, arr);
    }
}

Javascript

// function that prints the minimum possible value of arr[j] + |j - i|
function minAtEachIndex(n, arr) {
  // loop over every element in the array
  for (let i = 0; i < n; i++) {
    // set the minimum value to the maximum safe integer value
    let minValue = Number.MAX_SAFE_INTEGER;
    // loop over every element in the array to find the minimum value
    for (let j = 0; j < n; j++) {
      // compute the value of arr[j] + |j - i|
      let val = arr[j] + Math.abs(i - j);
      // update the minimum value if val is smaller than the current minimum
      if (val < minValue) {
        minValue = val;
      }
    }
    // print the minimum value
    document.write(minValue + " ");
  }
}
 
// example array
let arr = [1, 4, 2, 5, 3];
// get the length of the array
let n = arr.length;
// call the minAtEachIndex function with the array and its length
minAtEachIndex(n, arr);

Output:

1 2 2 3 3

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: The idea is to use prefix sum technique from both left and right array traversal and find the minimum for each index. Follow the steps below to solve the problem:

Take two auxiliary array dp1[] and dp2[] where dp1[] store the answer for the left to right traversal and dp2[] stores the answer for the right to left traversal.
Traverse the array arr[] from i = 2 to N-1 and calculate min(arr[i], dp1[i-1] + 1).
Traverse the array arr[] form i = N-1 to 1 and calculate min(arr[i], dp2[i+1] + 1).
Again traverse the array from 1 to N and print min(dp1[i], dp2[i]) at each iteration.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum value of
// arr[j] + |j - i| for every array index
void minAtEachIndex(int n, int arr[])
{
    // Stores minimum of a[j] + |i - j|
    // upto position i
    int dp1[n];
 
    // Stores minimum of a[j] + |i-j|
    // upto position i from the end
    int dp2[n];
 
    int i;
 
    dp1[0] = arr[0];
 
    // Traversing and storing minimum
    // of a[j]+|i-j| upto i
    for (i = 1; i < n; i++)
        dp1[i] = min(arr[i], dp1[i - 1] + 1);
 
    dp2[n - 1] = arr[n - 1];
 
    // Traversing and storing minimum
    // of a[j]+|i-j| upto i from the end
    for (i = n - 2; i >= 0; i--)
        dp2[i] = min(arr[i], dp2[i + 1] + 1);
 
    vector<int> v;
 
    // Traversing from [0, N] and storing minimum
    // of a[j] + |i - j| from starting and end
    for (i = 0; i < n; i++)
        v.push_back(min(dp1[i], dp2[i]));
 
    // Print the required array
    for (auto x : v)
        cout << x << " ";
}
 
// Driver code
int main()
{
 
    // Given array arr[]
    int arr[] = { 1, 4, 2, 5, 3 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    minAtEachIndex(N, arr);
 
    return 0;
}

Java

// Java program for the above approach 
import java.util.*;
import java.util.ArrayList; 
import java.util.List; 
   
class GFG{
       
// Function to find minimum value of
// arr[j] + |j - i| for every array index
static void minAtEachIndex(int n, int arr[])
{
     
    // Stores minimum of a[j] + |i - j|
    // upto position i
    int dp1[] = new int[n];
     
    // Stores minimum of a[j] + |i-j|
    // upto position i from the end
    int dp2[] = new int[n];
 
    int i;
 
    dp1[0] = arr[0];
 
    // Traversing and storing minimum
    // of a[j]+|i-j| upto i
    for(i = 1; i < n; i++)
        dp1[i] = Math.min(arr[i], dp1[i - 1] + 1);
 
    dp2[n - 1] = arr[n - 1];
 
    // Traversing and storing minimum
    // of a[j]+|i-j| upto i from the end
    for(i = n - 2; i >= 0; i--)
        dp2[i] = Math.min(arr[i], dp2[i + 1] + 1);
 
    ArrayList<Integer> v = new ArrayList<Integer>(); 
 
    // Traversing from [0, N] and storing minimum
    // of a[j] + |i - j| from starting and end
    for(i = 0; i < n; i++)
        v.add(Math.min(dp1[i], dp2[i]));
 
    // Print the required array
    for(int x : v)
        System.out.print(x + " ");
}
   
// Driver code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 1, 4, 2, 5, 3 };
 
    // Size of the array
    int N = arr.length;
 
    // Function Call
    minAtEachIndex(N, arr);
}
}
 
// This code is contributed by sanjoy_62

Python3

# Python3 program for the above approach
 
# Function to find minimum value of
# arr[j] + |j - i| for every array index
def minAtEachIndex(n, arr):
     
    # Stores minimum of a[j] + |i - j|
    # upto position i
    dp1 = [0] * n
     
    # Stores minimum of a[j] + |i-j|
    # upto position i from the end
    dp2 = [0] * n
     
    i = 0
 
    dp1[0] = arr[0]
     
    # Traversing and storing minimum
    # of a[j]+|i-j| upto i
    for i in range(1, n):
        dp1[i] = min(arr[i], dp1[i - 1] + 1)
 
    dp2[n - 1] = arr[n - 1]
 
    # Traversing and storing minimum
    # of a[j]+|i-j| upto i from the end
    for i in range(n - 2, -1, -1):
        dp2[i] = min(arr[i], dp2[i + 1] + 1)
 
    v = []
 
    # Traversing from [0, N] and storing minimum
    # of a[j] + |i - j| from starting and end
    for i in range(0, n):
        v.append(min(dp1[i], dp2[i]))
 
    # Print the required array
    for x in v:
        print(x, end = " ")
 
# Driver code
if __name__ == '__main__':
     
    # Given array arr
    arr = [ 1, 4, 2, 5, 3 ]
 
    # Size of the array
    N = len(arr)
 
    # Function Call
    minAtEachIndex(N, arr)
 
# This code is contributed by shikhasingrajput

C#

// C# program for the above approach 
using System;
using System.Collections.Generic;
 
class GFG{
       
// Function to find minimum value of
// arr[j] + |j - i| for every array index
static void minAtEachIndex(int n, int []arr)
{
     
    // Stores minimum of a[j] + |i - j|
    // upto position i
    int []dp1 = new int[n];
     
    // Stores minimum of a[j] + |i-j|
    // upto position i from the end
    int []dp2 = new int[n];
    int i;
    dp1[0] = arr[0];
 
    // Traversing and storing minimum
    // of a[j]+|i-j| upto i
    for(i = 1; i < n; i++)
        dp1[i] = Math.Min(arr[i], dp1[i - 1] + 1);
    dp2[n - 1] = arr[n - 1];
 
    // Traversing and storing minimum
    // of a[j]+|i-j| upto i from the end
    for(i = n - 2; i >= 0; i--)
        dp2[i] = Math.Min(arr[i], dp2[i + 1] + 1);
    List<int> v = new List<int>(); 
 
    // Traversing from [0, N] and storing minimum
    // of a[j] + |i - j| from starting and end
    for(i = 0; i < n; i++)
        v.Add(Math.Min(dp1[i], dp2[i]));
 
    // Print the required array
    foreach(int x in v)
        Console.Write(x + " ");
}
   
// Driver code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 1, 4, 2, 5, 3 };
 
    // Size of the array
    int N = arr.Length;
 
    // Function Call
    minAtEachIndex(N, arr);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find minimum value of
// arr[j] + |j - i| for every array index
function minAtEachIndex(n, arr)
{
    // Stores minimum of a[j] + |i - j|
    // upto position i
    var dp1 = Array(n);
 
    // Stores minimum of a[j] + |i-j|
    // upto position i from the end
    var dp2 = Array(n);
 
    var i;
 
    dp1[0] = arr[0];
 
    // Traversing and storing minimum
    // of a[j]+|i-j| upto i
    for (i = 1; i < n; i++)
        dp1[i] = Math.min(arr[i], dp1[i - 1] + 1);
 
    dp2[n - 1] = arr[n - 1];
 
    // Traversing and storing minimum
    // of a[j]+|i-j| upto i from the end
    for (i = n - 2; i >= 0; i--)
        dp2[i] = Math.min(arr[i], dp2[i + 1] + 1);
 
    var v = [];
 
    // Traversing from [0, N] and storing minimum
    // of a[j] + |i - j| from starting and end
    for (i = 0; i < n; i++)
        v.push(Math.min(dp1[i], dp2[i]));
 
    // Print the required array
    v.forEach(x => {
        document.write(x + " ");
    });
     
}
 
// Driver code
 
// Given array arr[]
var arr = [1, 4, 2, 5, 3];
 
// Size of the array
var N = arr.length;
 
// Function Call
minAtEachIndex(N, arr);
 
</script>

Output:

1 2 2 3 3

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!