Modifique la array reemplazando cada elemento de la array con el valor mínimo posible de arr[j] + |j ​​– i|

Dada una array arr[] de tamaño N , la tarea es encontrar un valor para cada índice tal que el valor en el índice i sea arr[j] + |j ​​– i| donde 1 ≤ j ≤ N , la tarea es encontrar el valor mínimo para cada índice de 1 a N .

Ejemplo:

Entrada: N = 5, arr[] = {1, 4, 2, 5, 3}
Salida: {1, 2, 2, 3, 3}
Explicación: 
arr[0] = arr[0] + |0-0 | = 1
array[1] = array[0] + |0-1| = 2
array[2] = array[2] + |2-2| = 2
array[3] = array[2] + |2-3| = 3
array[4] = array[4] + |4-4| = 3
La array de salida dará un valor mínimo en cada i ^-ésima posición.

Entrada: N = 4, arr[] = {1, 2, 3, 4}
Salida: {1, 2, 3, 4} 

Enfoque ingenuo: la idea es utilizar dos bucles for anidados para recorrer la array y, para cada i ^-ésimo índice, encontrar e imprimir el valor mínimo de arr[j] + |ij| . 

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es utilizar la técnica de suma de prefijos desde el recorrido de array izquierdo y derecho y encontrar el mínimo para cada índice. Siga los pasos a continuación para resolver el problema:

1. Tome dos arrays auxiliares dp1[] y dp2[] donde dp1[] almacena la respuesta para el recorrido de izquierda a derecha y dp2[] almacena la respuesta para el recorrido de derecha a izquierda.
2. Recorra la array arr[] de i = 2 a N-1 y calcule min(arr[i], dp1[i-1] + 1) .
3. Recorra la array arr[] de i = N-1 a 1 y calcule min(arr[i], dp2 [i+1] + 1) .
4. De nuevo, recorra la array de 1 a N e imprima min(dp1[i], dp2[i]) en cada iteración.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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

<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>

1 2 2 3 3

Complejidad temporal: O(N)
Espacio auxiliar: O(N)