For each Array index find the maximum value among all M operations
Given an array arr[] of size N initially filled with 0 and another array Positions[] of size M, the task is to return the maximum value for each index after performing the following M operations:
- Make the value at index Positions[i] equal to 0
- All the numbers to the right of Positions[i] will be one greater than their immediate left neighbour.
- All the numbers to the left of Positions[i] will be one greater than their immediate right neighbour.
Examples:
Input: N = 6, M = 2, Positions = {2, 3}
Output: {3, 2, 1, 1, 2, 3}
Explanation: Initial array: {0, 0, 0, 0, 0, 0}
After first operation: {2, 1, 0, 1, 2, 3}
where each element to the right of 2nd index and each element to its left follow the given condition
After second operation: {3, 2, 1, 0, 1, 2}
Thus, maximum value of each index among all the operations: {3, 2, 1, 1, 2, 3}Input: N = 4, M = 3, Positions = {3, 2, 1}
Output: {3, 2, 1, 2}
Explanation: Initial array: {0, 0, 0, 0}
After first operation: {3, 2, 1, 0}
After second operation: {2, 1, 0, 1}
After third operation: {1, 0, 1, 2}
Thus, Maximum: {3, 2, 1, 2}
Approach: The problem can be solved based on the following observation:
The value set at the indices for each operation denotes the distance from the index set to 0.
Therefore, the positions closest to the ends of the array which are set to 0 will set the values of other indices to be the maximum when given operation is performed.
Based on the above observation, the solution is to find the indices closest to the ends of the array (say x and y) which are set to 0 at any of the operations. The maximum value for each index will be the maximum distance from any of x and y.
Follow the steps to solve the problem:
- Generate an array with null values (say arr[]).
- Find the maximum and the minimum in the Positions[] array (say x and y).
- Traverse the array from i = 0 to N-1:
- Print the maximum of the absolute difference between the current index and x or y
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find the maximum values // for each array index among M operations vector< int > create(vector< int >& x, int n, int m) { int maxa = 0; int mini = INT_MAX; // Traversing the position array for ( int j = 0; j < m; j++) { maxa = max(maxa, x[j]); mini = min(mini, x[j]); } vector< int > arr; // Traversing the array for ( int k = 0; k < n; k++) { // Print maximum of absolute // difference between maximum // and minimum positions to // current position arr.push_back(max( abs (k - maxa), abs (k - mini))); } return arr; } // Driver code int main() { int N = 4; int M = 3; // Initializing a position array vector< int > Positions = { 3, 2, 1 }; vector< int > sol = create(Positions, N, M); for ( auto x : sol) cout << x << " " ; return 0; } // This code is contributed by rakeshsahni |
Java
// Java code for the above approach: import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to find the maximum values // for each array index among M operations public static List<Integer> create( int x[], int n, int m) { int maxa = 0 ; int mini = Integer.MAX_VALUE; // Traversing the position array for ( int j = 0 ; j < m; j++) { maxa = Math.max(maxa, x[j]); mini = Math.min(mini, x[j]); } List<Integer> arr = new ArrayList<Integer>(); // Traversing the array for ( int k = 0 ; k < n; k++) { // Print maximum of absolute // difference between maximum // and minimum positions to // current position arr.add(Math.max( Math.abs(k - maxa), Math.abs(k - mini))); } return arr; } // Driver code public static void main(String[] args) { int N = 4 ; int M = 3 ; // Initializing a position array int Positions[] = { 3 , 2 , 1 }; List<Integer> sol = create(Positions, N, M); for ( int x : sol) System.out.print(x + " " ); } } |
Python3
# Python3 code for the above approach: import sys # Function to find the maximum values # for each array index among M operations def create(x, n, m): maxa = 0 mini = sys.maxsize # Traversing the position array for j in range (m): maxa = max (maxa, x[j]) mini = min (mini, x[j]) arr = [] # Traversing the array for k in range (n): # Print maximum of absolute # difference between maximum # and minimum positions to # current position arr.append( max ( abs (k - maxa), abs (k - mini))) return arr # Driver Code N = 4 M = 3 # Initializing a position array Positions = [ 3 , 2 , 1 ] sol = create(Positions, N, M) print ( " " .join( list ( map ( str , sol)))) # This code is contributed by Phasing17 |
C#
// C# code for the above approach: using System; using System.Collections; public class GFG { // Function to find the maximum values // for each array index among M operations static public ArrayList create( int [] x, int n, int m) { int maxa = 0; int mini = int .MaxValue; // Traversing the position array for ( int j = 0; j < m; j++) { maxa = Math.Max(maxa, x[j]); mini = Math.Min(mini, x[j]); } ArrayList arr = new ArrayList(); // Traversing the array for ( int k = 0; k < n; k++) { // Print maximum of absolute // difference between maximum // and minimum positions to // current position arr.Add(Math.Max(Math.Abs(k - maxa), Math.Abs(k - mini))); } return arr; } // Driver code static public void Main() { int N = 4; int M = 3; // Initializing a position array int [] Positions = { 3, 2, 1 }; ArrayList sol = create(Positions, N, M); for ( int i = 0; i < sol.Count; i++) Console.Write(sol[i] + " " ); } } // This code is contributed by ninja_hattori. |
Javascript
<script> // JavaScript code for the above approach // Function to find the maximum values // for each array index among M operations function create(x, n, m) { let maxa = 0; let mini = Number.MAX_VALUE; // Traversing the position array for (let j = 0; j < m; j++) { maxa = Math.max(maxa, x[j]); mini = Math.min(mini, x[j]); } let arr = []; // Traversing the array for (let k = 0; k < n; k++) { // Print maximum of absolute // difference between maximum // and minimum positions to // current position arr.push(Math.max(Math.abs(k - maxa), Math.abs(k - mini))); } return arr; } // Driver code let N = 4; let M = 3; // Initializing a position array let Positions = [3, 2, 1]; let sol = create(Positions, N, M); for (let x of sol) document.write(x + " " ); // This code is contributed by Potta Lokesh </script> |
3 2 1 2
Time Complexity: O(N) + O(M), where N is the size of the array and M is the size of the position array
Auxiliary Space: O(M)
Contact Us