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 ith 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 ith 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 codeint 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 elementfor (int i = 0; i < n; i++) {// to get the minimum value for current ith elementint 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 valueint val = arr[j] + Math.abs(i - j);if (val < minValue) {minValue = val;}}// print minimum valueSystem.out.print(minValue + " ");}return;}// Driver codepublic 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 codeif __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 arraylet arr = [1, 4, 2, 5, 3];// get the length of the arraylet n = arr.length;// call the minAtEachIndex function with the array and its lengthminAtEachIndex(n, arr); |
Output:
1 2 2 3 3
Time Complexity: O(N2)
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 indexvoid 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 codeint 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 indexstatic 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 codepublic 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 indexdef 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 codeif __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 indexstatic 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 codepublic 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 indexfunction 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 arrayvar N = arr.length;// Function CallminAtEachIndex(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
