Given an array arr[] of size N and an integer K, the task is to find the length of the longest subarray consisting of same elements that can be obtained by decrementing the array elements by 1 at most K times.
Example:
Input: arr[] = { 1, 2, 3 }, K = 1
Output: 2
Explanation:
Decrementing arr[0] by 1 modifies arr[] to { 1, 1, 3 }
The longest subarray with equal elements is { 1, 1 }.
Therefore, the required output is 2.Input: arr[] = { 1, 7, 3, 4, 5, 6 }, K = 6
Output: 4
Approach: The problem can be solved using Segment tree and Binary Search technique. The idea is to use the following observations:
Total number of decrements operations required to make all array elements of the subarray { arr[start], …, arr[end] } equal
= (?(start, end)) – (end – start + 1) * (min_value)where, start = index of the starting point of the subarray
end = index of end point of subarray
min_value = smallest value from index i to j
?(start, end) = sum of all elements from index i to j
Follow the steps below to solve the above problem:
- Initialize a segment tree to calculate the smallest element in a subarray of the array and a prefix sum array to calculate the sum elements of a subarray.
- Traverse the array, arr[]. For every ith element perform the following operations:
- Initialize two variables say, start = i, end = N – 1 and apply binary search over the range [start, end] to check if the all the elements of the subarray { arr[start], …, arr[end] } can be made equal or not by decrementing at most K operations from the above observations.
- If all the elements of the subarray { arr[start], …, arr[end] } can be made equal by decrementing at most K operations then update start = (start + end) / 2 + 1.
- Otherwise, update end = (start + end) / 2 – 1
- Finally, print the length of the longest subarray obtained from the above operations.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to construct Segment Tree // to return the minimum element in a range int build(int tree[], int* A, int start, int end, int node) { // If leaf nodes of // the tree are found if (start == end) { // Update the value in segment // tree from given array tree[node] = A[start]; return tree[node]; } // Divide left and right subtree int mid = (start + end) / 2; // Stores smallest element in // subarray { arr[start], arr[mid] } int X = build(tree, A, start, mid, 2 * node + 1); // Stores smallest element in // subarray { arr[mid + 1], arr[end] } int Y = build(tree, A, mid + 1, end, 2 * node + 2); // Stores smallest element in // subarray { arr[start], arr[end] } return tree[node] = min(X, Y); } // Function to find the smallest // element present in a subarray int query(int tree[], int start, int end, int l, int r, int node) { // If elements of the subarray // are not in the range [l, r] if (start > r || end < l) return INT_MAX; // If all the elements of the // subarray are in the range [l, r] if (start >= l && end <= r) return tree[node]; // Divide tree into left // and right subtree int mid = (start + end) / 2; // Stores smallest element // in left subtree int X = query(tree, start, mid, l, r, 2 * node + 1); // Stores smallest element in // right subtree int Y = query(tree, mid + 1, end, l, r, 2 * node + 2); return min(X, Y); } // Function that find length of longest // subarray with all equal elements in // atmost K decrements int longestSubArray(int* A, int N, int K) { // Stores length of longest subarray // with all equal elements in atmost // K decrements. int res = 1; // Store the prefix sum array int preSum[N + 1]; // Calculate the prefix sum array preSum[0] = A[0]; for (int i = 0; i < N; i++) preSum[i + 1] = preSum[i] + A[i]; int tree[4 * N + 5]; // Build the segment tree // for range min query build(tree, A, 0, N - 1, 0); // Traverse the array for (int i = 0; i < N; i++) { // Stores start index // of the subarray int start = i; // Stores end index // of the subarray int end = N - 1; int mid; // Stores end index of // the longest subarray int max_index = i; // Performing the binary search // to find the endpoint // for the selected range while (start <= end) { // Find the mid for binary search mid = (start + end) / 2; // Find the smallest element in // range [i, mid] using Segment Tree int min_element = query(tree, 0, N - 1, i, mid, 0); // Stores total sum of subarray // after K decrements int expected_sum = (mid - i + 1) * min_element; // Stores sum of elements of // subarray before K decrements int actual_sum = preSum[mid + 1] - preSum[i]; // If subarray found with // all equal elements if (actual_sum - expected_sum <= K) { // Update start start = mid + 1; // Update max_index max_index = max(max_index, mid); } // If false, it means that // the selected range is invalid else { // Update end end = mid - 1; } } // Store the length of longest subarray res = max(res, max_index - i + 1); } // Return result return res; } // Driver Code int main() { int arr[] = { 1, 7, 3, 4, 5, 6 }; int k = 6; int n = 6; cout << longestSubArray(arr, n, k); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to construct Segment Tree // to return the minimum element in a range static int build(int tree[], int[] A, int start, int end, int node) { // If leaf nodes of // the tree are found if (start == end) { // Update the value in segment // tree from given array tree[node] = A[start]; return tree[node]; } // Divide left and right subtree int mid = (start + end) / 2; // Stores smallest element in // subarray { arr[start], arr[mid] } int X = build(tree, A, start, mid, 2 * node + 1); // Stores smallest element in // subarray { arr[mid + 1], arr[end] } int Y = build(tree, A, mid + 1, end, 2 * node + 2); // Stores smallest element in // subarray { arr[start], arr[end] } return (tree[node] = Math.min(X, Y)); } // Function to find the smallest // element present in a subarray static int query(int tree[], int start, int end, int l, int r, int node) { // If elements of the subarray // are not in the range [l, r] if (start > r || end < l) return Integer.MAX_VALUE; // If all the elements of the // subarray are in the range [l, r] if (start >= l && end <= r) return tree[node]; // Divide tree into left // and right subtree int mid = (start + end) / 2; // Stores smallest element // in left subtree int X = query(tree, start, mid, l, r, 2 * node + 1); // Stores smallest element in // right subtree int Y = query(tree, mid + 1, end, l, r, 2 * node + 2); return Math.min(X, Y); } // Function that find length of longest // subarray with all equal elements in // atmost K decrements static int longestSubArray(int[] A, int N, int K) { // Stores length of longest subarray // with all equal elements in atmost // K decrements. int res = 1; // Store the prefix sum array int preSum[] = new int[N + 1]; // Calculate the prefix sum array preSum[0] = A[0]; for(int i = 0; i < N; i++) preSum[i + 1] = preSum[i] + A[i]; int tree[] = new int[4 * N + 5]; // Build the segment tree // for range min query build(tree, A, 0, N - 1, 0); // Traverse the array for(int i = 0; i < N; i++) { // Stores start index // of the subarray int start = i; // Stores end index // of the subarray int end = N - 1; int mid; // Stores end index of // the longest subarray int max_index = i; // Performing the binary search // to find the endpoint // for the selected range while (start <= end) { // Find the mid for binary search mid = (start + end) / 2; // Find the smallest element in // range [i, mid] using Segment Tree int min_element = query(tree, 0, N - 1, i, mid, 0); // Stores total sum of subarray // after K decrements int expected_sum = (mid - i + 1) * min_element; // Stores sum of elements of // subarray before K decrements int actual_sum = preSum[mid + 1] - preSum[i]; // If subarray found with // all equal elements if (actual_sum - expected_sum <= K) { // Update start start = mid + 1; // Update max_index max_index = Math.max(max_index, mid); } // If false, it means that // the selected range is invalid else { // Update end end = mid - 1; } } // Store the length of longest subarray res = Math.max(res, max_index - i + 1); } // Return result return res; } // Driver Code static public void main(String args[]) { int arr[] = { 1, 7, 3, 4, 5, 6 }; int k = 6; int n = 6; System.out.print(longestSubArray(arr, n, k)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program to implement # the above approach import sys # Function to construct Segment Tree # to return the minimum element in a range def build(tree, A, start, end, node): # If leaf nodes of # the tree are found if (start == end): # Update the value in segment # tree from given array tree[node] = A[start] return tree[node] # Divide left and right subtree mid = (int)((start + end) / 2) # Stores smallest element in # subarray : arr[start], arr[mid] X = build(tree, A, start, mid, 2 * node + 1) # Stores smallest element in # subarray : arr[mid + 1], arr[end] Y = build(tree, A, mid + 1, end, 2 * node + 2) # Stores smallest element in # subarray : arr[start], arr[end] return (tree[node] == min(X, Y)) # Function to find the smallest # element present in a subarray def query(tree, start, end, l, r, node): # If elements of the subarray # are not in the range [l, r] if (start > r or end < l) : return sys.maxsize # If all the elements of the # subarray are in the range [l, r] if (start >= l and end <= r): return tree[node] # Divide tree into left # and right subtree mid = (int)((start + end) / 2) # Stores smallest element # in left subtree X = query(tree, start, mid, l, r, 2 * node + 1) # Stores smallest element in # right subtree Y = query(tree, mid + 1, end, l, r, 2 * node + 2) return min(X, Y) # Function that find length of longest # subarray with all equal elements in # atmost K decrements def longestSubArray(A, N, K): # Stores length of longest subarray # with all equal elements in atmost # K decrements. res = 1 # Store the prefix sum array preSum = [0] * (N + 1) # Calculate the prefix sum array preSum[0] = A[0] for i in range(N): preSum[i + 1] = preSum[i] + A[i] tree = [0] * (4 * N + 5) # Build the segment tree # for range min query build(tree, A, 0, N - 1, 0) # Traverse the array for i in range(N): # Stores start index # of the subarray start = i # Stores end index # of the subarray end = N - 1 # Stores end index of # the longest subarray max_index = i # Performing the binary search # to find the endpoint # for the selected range while (start <= end): # Find the mid for binary search mid = (int)((start + end) / 2) # Find the smallest element in # range [i, mid] using Segment Tree min_element = query(tree, 0, N - 1, i, mid, 0) # Stores total sum of subarray # after K decrements expected_sum = (mid - i + 1) * min_element # Stores sum of elements of # subarray before K decrements actual_sum = preSum[mid + 1] - preSum[i] # If subarray found with # all equal elements if (actual_sum - expected_sum <= K): # Update start start = mid + 1 # Update max_index max_index = max(max_index, mid) # If false, it means that # the selected range is invalid else: # Update end end = mid - 1 # Store the length of longest subarray res = max(res, max_index - i + 2) # Return result return res # Driver Code arr = [ 1, 7, 3, 4, 5, 6 ] k = 6n = 6 print(longestSubArray(arr, n, k)) # This code is contributed by splevel62 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to construct Segment Tree // to return the minimum element in a range static int build(int[] tree, int[] A, int start, int end, int node) { // If leaf nodes of // the tree are found if (start == end) { // Update the value in segment // tree from given array tree[node] = A[start]; return tree[node]; } // Divide left and right subtree int mid = (start + end) / 2; // Stores smallest element in // subarray { arr[start], arr[mid] } int X = build(tree, A, start, mid, 2 * node + 1); // Stores smallest element in // subarray { arr[mid + 1], arr[end] } int Y = build(tree, A, mid + 1, end, 2 * node + 2); // Stores smallest element in // subarray { arr[start], arr[end] } return (tree[node] = Math.Min(X, Y)); } // Function to find the smallest // element present in a subarray static int query(int[] tree, int start, int end, int l, int r, int node) { // If elements of the subarray // are not in the range [l, r] if (start > r || end < l) return Int32.MaxValue; // If all the elements of the // subarray are in the range [l, r] if (start >= l && end <= r) return tree[node]; // Divide tree into left // and right subtree int mid = (start + end) / 2; // Stores smallest element // in left subtree int X = query(tree, start, mid, l, r, 2 * node + 1); // Stores smallest element in // right subtree int Y = query(tree, mid + 1, end, l, r, 2 * node + 2); return Math.Min(X, Y); } // Function that find length of longest // subarray with all equal elements in // atmost K decrements static int longestSubArray(int[] A, int N, int K) { // Stores length of longest subarray // with all equal elements in atmost // K decrements. int res = 1; // Store the prefix sum array int[] preSum = new int[N + 1]; // Calculate the prefix sum array preSum[0] = A[0]; for(int i = 0; i < N; i++) preSum[i + 1] = preSum[i] + A[i]; int[] tree = new int[4 * N + 5]; // Build the segment tree // for range min query build(tree, A, 0, N - 1, 0); // Traverse the array for(int i = 0; i < N; i++) { // Stores start index // of the subarray int start = i; // Stores end index // of the subarray int end = N - 1; int mid; // Stores end index of // the longest subarray int max_index = i; // Performing the binary search // to find the endpoint // for the selected range while (start <= end) { // Find the mid for binary search mid = (start + end) / 2; // Find the smallest element in // range [i, mid] using Segment Tree int min_element = query(tree, 0, N - 1, i, mid, 0); // Stores total sum of subarray // after K decrements int expected_sum = (mid - i + 1) * min_element; // Stores sum of elements of // subarray before K decrements int actual_sum = preSum[mid + 1] - preSum[i]; // If subarray found with // all equal elements if (actual_sum - expected_sum <= K) { // Update start start = mid + 1; // Update max_index max_index = Math.Max(max_index, mid); } // If false, it means that // the selected range is invalid else { // Update end end = mid - 1; } } // Store the length of longest subarray res = Math.Max(res, max_index - i + 1); } // Return result return res; } // Driver Code static void Main() { int[] arr = { 1, 7, 3, 4, 5, 6 }; int k = 6; int n = 6; Console.WriteLine(longestSubArray(arr, n, k)); } } // This code is contributed by susmitakundugoaldanga |
Javascript
<script> // JavaScript program to implement // the above approach // Function to construct Segment Tree // to return the minimum element in a range function build(tree,A, start,end, node) { // If leaf nodes of // the tree are found if (start == end) { // Update the value in segment // tree from given array tree[node] = A[start]; return tree[node]; } // Divide left and right subtree let mid = Math.floor((start + end) / 2); // Stores smallest element in // subarray { arr[start], arr[mid] } let X = build(tree, A, start, mid, 2 * node + 1); // Stores smallest element in // subarray { arr[mid + 1], arr[end] } let Y = build(tree, A, mid + 1, end, 2 * node + 2); // Stores smallest element in // subarray { arr[start], arr[end] } return tree[node] = Math.min(X, Y); } // Function to find the smallest // element present in a subarray function query(tree,start, end,l, r, node) { // If elements of the subarray // are not in the range [l, r] if (start > r || end < l) return Number.MAX_VALUE; // If all the elements of the // subarray are in the range [l, r] if (start >= l && end <= r) return tree[node]; // Divide tree into left // and right subtree let mid = Math.floor((start + end) / 2); // Stores smallest element // in left subtree let X = query(tree, start, mid, l, r, 2 * node + 1); // Stores smallest element in // right subtree let Y = query(tree, mid + 1, end, l, r, 2 * node + 2); return Math.min(X, Y); } // Function that find length of longest // subarray with all equal elements in // atmost K decrements function longestSubArray(A,N,K) { // Stores length of longest subarray // with all equal elements in atmost // K decrements. let res = 1; // Store the prefix sum array let preSum = new Array(N + 1); // Calculate the prefix sum array preSum[0] = A[0]; for (let i = 0; i < N; i++) preSum[i + 1] = preSum[i] + A[i]; let tree = new Array(4 * N + 5); // Build the segment tree // for range min query build(tree, A, 0, N - 1, 0); // Traverse the array for (let i = 0; i < N; i++) { // Stores start index // of the subarray let start = i; // Stores end index // of the subarray let end = N - 1; let mid; // Stores end index of // the longest subarray let max_index = i; // Performing the binary search // to find the endpoint // for the selected range while (start <= end) { // Find the mid for binary search mid = Math.floor((start + end) / 2); // Find the smallest element in // range [i, mid] using Segment Tree let min_element = query(tree, 0, N - 1, i, mid, 0); // Stores total sum of subarray // after K decrements let expected_sum = (mid - i + 1) * min_element; // Stores sum of elements of // subarray before K decrements let actual_sum = preSum[mid + 1] - preSum[i]; // If subarray found with // all equal elements if (actual_sum - expected_sum <= K) { // Update start start = mid + 1; // Update max_index max_index = Math.max(max_index, mid); } // If false, it means that // the selected range is invalid else { // Update end end = mid - 1; } } // Store the length of longest subarray res = Math.max(res, max_index - i + 1); } // Return result return res; } // Driver Code let arr = [ 1, 7, 3, 4, 5, 6 ]; let k = 6; let n = 6; document.write(longestSubArray(arr, n, k),"</br>"); // This code is contributed by shinjanpatra </script> |
Output:
4
Time Complexity: O(N * (log(N))2)
Auxiliary Space: O(N)
Related Topic: Segment Tree
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!
