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