Given an array arr, the task is to replace each array element by the maximum of K next and K previous elements.
Example:
Input: arr[] = {12, 5, 3, 9, 21, 36, 17}, K=2
Output: 5 12 21 36 36 21 36Input: arr[] = { 13, 21, 19}, K=1
Output: 21, 19, 21
Naive Approach: Follow the below steps to solve this problem:
- Traverse the array from i=0 to i<N and for each element:
- Run another loop from j=i-K to j<=i+K, and change arr[i] to the maximum of K next and K previous elements.
- Print the array after the above loop ends.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>#include <limits.h>#include <math.h>using namespace std;// Function to update the array// arr[i] = maximum of prev K and next K elements.void updateArray(int arr[], int N, int K){ int start, end; for (int i = 0; i < N; i++) { int mx = INT_MIN; // Start limit is max(i-K, 0) start = max(i - K, 0); // End limit in min(i+K, N-1) end = min(i + K, N - 1); for (int j = start; j <= end; j++) { // Skipping the current element if (j == i) { continue; } mx = max(arr[j], mx); } cout << mx << ' '; }}// Driver Codeint main(){ int arr[] = { 12, 5, 3, 9, 21, 36, 17 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; updateArray(arr, N, K);} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to update the array arr[i] = maximum// of prev K and next K elements.static void updateArray(int arr[], int N, int K){ int start, end; for(int i = 0; i < N; i++) { int mx = Integer.MIN_VALUE; // Start limit is max(i-K, 0) start = Math.max(i - K, 0); // End limit in min(i+K, N-1) end = Math.min(i + K, N - 1); for(int j = start; j <= end; j++) { // Skipping the current element if (j == i) { continue; } mx = Math.max(arr[j], mx); } System.out.print(mx + " "); }}// Driver Codepublic static void main(String args[]){ int arr[] = { 12, 5, 3, 9, 21, 36, 17 }; int N = arr.length; int K = 2; updateArray(arr, N, K);}}// This code is contributed by Samim Hossain Mondal. |
Python3
# python3 program for the above approachINT_MIN = -2147483648# Function to update the array# arr[i] = maximum of prev K and next K elements.def updateArray(arr, N, K): for i in range(0, N): mx = INT_MIN # Start limit is max(i-K, 0) start = max(i - K, 0) # End limit in min(i+K, N-1) end = min(i + K, N - 1) for j in range(start, end + 1): # Skipping the current element if (j == i): continue mx = max(arr[j], mx) print(mx, end=" ")# Driver Codeif __name__ == "__main__": arr = [12, 5, 3, 9, 21, 36, 17] N = len(arr) K = 2 updateArray(arr, N, K)# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG{ // Function to update the array arr[i] = maximum // of prev K and next K elements. static void updateArray(int[] arr, int N, int K) { int start, end; for (int i = 0; i < N; i++) { int mx = int.MinValue; // Start limit is max(i-K, 0) start = Math.Max(i - K, 0); // End limit in min(i+K, N-1) end = Math.Min(i + K, N - 1); for (int j = start; j <= end; j++) { // Skipping the current element if (j == i) { continue; } mx = Math.Max(arr[j], mx); } Console.Write(mx + " "); } } // Driver Code public static void Main() { int[] arr = { 12, 5, 3, 9, 21, 36, 17 }; int N = arr.Length; int K = 2; updateArray(arr, N, K); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript code for the above approach // Function to update the array // arr[i] = maximum of prev K and next K elements. function updateArray(arr, N, K) { let start, end; for (let i = 0; i < N; i++) { let mx = Number.MIN_VALUE; // Start limit is max(i-K, 0) start = Math.max(i - K, 0); // End limit in min(i+K, N-1) end = Math.min(i + K, N - 1); for (let j = start; j <= end; j++) { // Skipping the current element if (j == i) { continue; } mx = Math.max(arr[j], mx); } document.write(mx + ' ') } } // Driver Code let arr = [12, 5, 3, 9, 21, 36, 17]; let N = arr.length; let K = 2; updateArray(arr, N, K); // This code is contributed by Potta Lokesh </script> |
Output
5 12 21 36 36 21 36
Time Complexity: O(N*N)
Auxiliary Space: O(1)
Efficient Approach: A segment tree can be used to solve this problem. So, construct a range max segment tree, where:
- Leaf Nodes are the elements of the input array.
- Each internal node represents the maximum of all of its children.
Now, after building the segment tree, find the maximum from (i-K) to (i-1), say left and the maximum of (i+1) to (i+K), say right using query on this segment tree. Replace arr[i] with the maximum of left and right.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#define MAXN 500001#include <bits/stdc++.h>using namespace std;// Function to build the treevoid buildTree(vector<int>& arr, vector<int>& tree, int s, int e, int index){ // Leaf Node if (s == e) { tree[index] = arr[s]; return; } // Finding mid int mid = (s + e) / 2; buildTree(arr, tree, s, mid, 2 * index + 1); buildTree(arr, tree, mid + 1, e, 2 * index + 2); // Updating current node // by the maximum of its children tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);}// Function to find the maximum// element in a given rangeint query(vector<int>& tree, int s, int e, int index, int l, int r){ if (l > e or r < s) { return INT_MIN; } if (l <= s and r >= e) { return tree[index]; } int mid = (s + e) / 2; int left = query(tree, s, mid, 2 * index + 1, l, r); int right = query(tree, mid + 1, e, 2 * index + 2, l, r); return max(left, right);}// Function to replace each array element by// the maximum of K next and K previous elementsvoid updateArray(vector<int>& arr, int K){ // To store the segment tree vector<int> tree(MAXN); int N = arr.size(); buildTree(arr, tree, 0, N - 1, 0); for (int i = 0; i < N; ++i) { // For 0th index only find // the maximum out of 1 to i+K if (i == 0) { cout << query(tree, 0, N - 1, 0, 1, min(i + K, N - 1)) << ' '; continue; } // For (N-1)th index only find // the maximum out of 0 to (N-2) if (i == N - 1) { cout << query(tree, 0, N - 1, 0, max(0, i - K), N - 2); continue; } // Maximum from (i-K) to (i-1) int left = query(tree, 0, N - 1, 0, max(i - K, 0), i - 1); // Maximum from (i+1) to (i+K) int right = query(tree, 0, N - 1, 0, i + 1, min(i + K, N - 1)); cout << max(left, right) << ' '; }}// Driver Codeint main(){ vector<int> arr = { 12, 5, 3, 9, 21, 36, 17 }; int K = 2; updateArray(arr, K);} |
Java
// Java code for the above approachimport java.io.*;class GFG { static int MAXN = 500001; // Function to build the tree static void buildTree(int[] arr, int[] tree, int s, int e, int index) { // Leaf Node if (s == e) { tree[index] = arr[s]; return; } // Finding mid int mid = (s + e) / 2; buildTree(arr, tree, s, mid, 2 * index + 1); buildTree(arr, tree, mid + 1, e, 2 * index + 2); // Updating current node // by the maximum of its children tree[index] = Math.max(tree[2 * index + 1], tree[2 * index + 2]); } // Function to find the maximum // element in a given range static int query(int[] tree, int s, int e, int index, int l, int r) { if (l > e || r < s) { return Integer.MIN_VALUE; } if (l <= s && r >= e) { return tree[index]; } int mid = (s + e) / 2; int left = query(tree, s, mid, 2 * index + 1, l, r); int right = query(tree, mid + 1, e, 2 * index + 2, l, r); return Math.max(left, right); } // Function to replace each array element by // the maximum of K next and K previous elements static void updateArray(int[] arr, int K) { // To store the segment tree int[] tree = new int[MAXN]; int N = arr.length; buildTree(arr, tree, 0, N - 1, 0); for (int i = 0; i < N; ++i) { // For 0th index only find // the maximum out of 1 to i+K if (i == 0) { System.out.print(query(tree, 0, N - 1, 0, 1, Math.min(i + K, N - 1)) + " "); continue; } // For (N-1)th index only find // the maximum out of 0 to (N-2) if (i == N - 1) { System.out.println(query(tree, 0, N - 1, 0, Math.max(0, i - K), N - 2)); continue; } // Maximum from (i-K) to (i-1) int left = query(tree, 0, N - 1, 0, Math.max(i - K, 0), i - 1); // Maximum from (i+1) to (i+K) int right = query(tree, 0, N - 1, 0, i + 1, Math.min(i + K, N - 1)); System.out.print(Math.max(left, right) + " "); } } // Driver Code public static void main (String[] args) { int[] arr = { 12, 5, 3, 9, 21, 36, 17 }; int K = 2; updateArray(arr, K); }}// This code is contributed by Shubham Singh. |
Python3
# Python code for the above approachimport sysMAXN = 500001# Function to build the treedef buildTree(arr, tree, s, e, index): # Leaf Node if (s == e): tree[index] = arr[s] return # Finding mid mid = (s + e) // 2 buildTree(arr, tree, s, mid, 2 * index + 1) buildTree(arr, tree, mid + 1, e, 2 * index + 2) # Updating current node # by the maximum of its children tree[index] = max(tree[2 * index + 1], tree[2 * index + 2])# Function to find the maximum# element in a given rangedef query(tree, s, e, index, l, r): if (l > e or r < s): return -sys.maxsize -1 if (l <= s and r >= e): return tree[index] mid = (s + e) // 2 left = query(tree, s, mid,2 * index + 1, l, r) right = query(tree, mid + 1, e, 2 * index + 2, l, r) return max(left, right)# Function to replace each array element by# the maximum of K next and K previous elementsdef updateArray(arr, K): global MAXN # To store the segment tree tree = [0 for i in range(MAXN)] N = len(arr) buildTree(arr, tree, 0, N - 1, 0) for i in range(N): # For 0th index only find # the maximum out of 1 to i+K if (i == 0): print(query(tree, 0, N - 1, 0, 1, min(i + K, N - 1)),end = ' ') continue # For (N-1)th index only find # the maximum out of 0 to (N-2) if (i == N - 1): print(query(tree, 0, N - 1, 0, max(0, i - K), N - 2)) continue # Maximum from (i-K) to (i-1) left = query(tree, 0, N - 1, 0, max(i - K, 0), i - 1) # Maximum from (i+1) to (i+K) right = query(tree, 0, N - 1, 0, i + 1, min(i + K, N - 1)) print(max(left, right),end = ' ')# Driver Codearr = [12, 5, 3, 9, 21, 36, 17]K = 2updateArray(arr, K)# This code is contributed by shinjanpatra |
C#
// C# code for the above approachusing System;class GFG { static int MAXN = 500001; // Function to build the tree static void buildTree(int[] arr, int[] tree, int s, int e, int index) { // Leaf Node if (s == e) { tree[index] = arr[s]; return; } // Finding mid int mid = (s + e) / 2; buildTree(arr, tree, s, mid, 2 * index + 1); buildTree(arr, tree, mid + 1, e, 2 * index + 2); // Updating current node // by the maximum of its children tree[index] = Math.Max(tree[2 * index + 1], tree[2 * index + 2]); } // Function to find the maximum // element in a given range static int query(int[] tree, int s, int e, int index, int l, int r) { if (l > e || r < s) { return Int32.MinValue; } if (l <= s && r >= e) { return tree[index]; } int mid = (s + e) / 2; int left = query(tree, s, mid, 2 * index + 1, l, r); int right = query(tree, mid + 1, e, 2 * index + 2, l, r); return Math.Max(left, right); } // Function to replace each array element by // the maximum of K next and K previous elements static void updateArray(int[] arr, int K) { // To store the segment tree int[] tree = new int[MAXN]; int N = arr.Length; buildTree(arr, tree, 0, N - 1, 0); for (int i = 0; i < N; ++i) { // For 0th index only find // the maximum out of 1 to i+K if (i == 0) { Console.Write(query(tree, 0, N - 1, 0, 1, Math.Min(i + K, N - 1)) + " "); continue; } // For (N-1)th index only find // the maximum out of 0 to (N-2) if (i == N - 1) { Console.Write(query(tree, 0, N - 1, 0, Math.Max(0, i - K), N - 2)); continue; } // Maximum from (i-K) to (i-1) int left = query(tree, 0, N - 1, 0, Math.Max(i - K, 0), i - 1); // Maximum from (i+1) to (i+K) int right = query(tree, 0, N - 1, 0, i + 1, Math.Min(i + K, N - 1)); Console.Write(Math.Max(left, right) + " "); } } // Driver Code public static void Main() { int[] arr = { 12, 5, 3, 9, 21, 36, 17 }; int K = 2; updateArray(arr, K); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript code for the above approachlet MAXN = 500001// Function to build the treefunction buildTree(arr, tree, s, e, index) { // Leaf Node if (s == e) { tree[index] = arr[s]; return; } // Finding mid let mid = Math.floor((s + e) / 2); buildTree(arr, tree, s, mid, 2 * index + 1); buildTree(arr, tree, mid + 1, e, 2 * index + 2); // Updating current node // by the maximum of its children tree[index] = Math.max(tree[2 * index + 1], tree[2 * index + 2]);}// Function to find the maximum// element in a given rangefunction query(tree, s, e, index, l, r) { if (l > e || r < s) { return Number.MIN_SAFE_INTEGER; } if (l <= s && r >= e) { return tree[index]; } let mid = Math.floor((s + e) / 2); let left = query(tree, s, mid, 2 * index + 1, l, r); let right = query(tree, mid + 1, e, 2 * index + 2, l, r); return Math.max(left, right);}// Function to replace each array element by// the maximum of K next and K previous elementsfunction updateArray(arr, K) { // To store the segment tree let tree = new Array(MAXN).fill(0); let N = arr.length; buildTree(arr, tree, 0, N - 1, 0); for (let i = 0; i < N; ++i) { // For 0th index only find // the maximum out of 1 to i+K if (i == 0) { document.write(query(tree, 0, N - 1, 0, 1, Math.min(i + K, N - 1)) + ' '); continue; } // For (N-1)th index only find // the maximum out of 0 to (N-2) if (i == N - 1) { document.write(query(tree, 0, N - 1, 0, Math.max(0, i - K), N - 2)); continue; } // Maximum from (i-K) to (i-1) let left = query(tree, 0, N - 1, 0, Math.max(i - K, 0), i - 1); // Maximum from (i+1) to (i+K) let right = query(tree, 0, N - 1, 0, i + 1, Math.min(i + K, N - 1)); document.write(Math.max(left, right) + ' '); }}// Driver Codelet arr = [12, 5, 3, 9, 21, 36, 17];let K = 2;updateArray(arr, K);// This code is contributed by saurabh_jaiswal.</script> |
Output
5 12 21 36 36 21 36
Time Complexity: O(NlogN)
Auxiliary Space: O(MAXN)
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!
