Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem statement
1.1.
Example 1
1.1.1.
Input
1.1.2.
Output
1.1.3.
Explanation
2.
Approach
2.1.
Algorithm
2.2.
Code:
2.3.
Output:
3.

3.1.
Time Complexity
3.2.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Maximize the length of longest subarray consisting of same elements by at most X decrements

Apoorv
1 upvote

## Problem statement

Given an array ‘input[]’ of size ‘size’ with all the integer elements. We are also given a variable ‘X’.We can reduce the different elements of the array by one at most ‘X’ times. The final goal is to find the length of the longest subarray such that all the elements of the subarray are equal after performing the decrement operations.

### Example 1

#### Input

Input[] = { 3, 5, 6, 7, 3 }

Size = 5

K = 3

3

#### Explanation

There are a lot of possibilities to choose which element to reduce, but we have to choose optimally, so some of the optimal possibilities are

Case 1: reduce index 2 by 1 and reduce index 3 by 2 so total operations for decrement will be 3 and now after decrement array will be like this  = {3, 5, 5, 5, 3}. Hence the length of the longest subarray with the same elements is 3

Case 2: reduce index 2 by 2, so total operations for decrement will be 2, which is less than the given value of x that is 3 now after decrement array will be like this  = {3, 3, 6, 7, 3}. Hence the length of the longest subarray with the same elements is 2

.

.

Similarly, there are a lot of possibilities we have to find max length subarray, which is the case 1 that is 3.

## Approach

To Maximize the length of the longest subarray consisting of the same elements, The idea is to use segment trees and binary search to solve this problem. There is one observation which you will see after working on some test cases that is the Total number of decrements operations required to make all array elements of the subarray { input[start], …, input[end] } equal to (Σ(start, end)) – (end – start + 1) * (minimum value in the subarray). Where start is the starting index of the subarray and end is the ending index of the current subarray on which we are operating. Here we have to reach minimum value in the subarray to make all elements equal for eg if the array is [5,10,15] and we want to make all the elements equal we have to make all the elements as 5 so for that we have to reduce 10 by 5 and 15 by 10 so we took the entire sum which is 30 and subtract min value 5 * (3 - 0) so it will cost 15 operations. which is true we have to decrease 15 10 times and 10 5 times to make all the elements 5. Please try on some test cases and dry run you will get the logic.Below is the detailed algorithm and code for the approach.

Also read, Euclid GCD Algorithm

### Algorithm

• Create a segment tree to find the smallest element in a subarray of the array and a prefix sum array to find the sum of the subarray's members.
• Traverse the entire array and Perform the following operations on each element of the array
• Apply binary search throughout the range [start, end] to see if all the items of the subarray input[start],..., input[end] can be made equal or not by decrementing at most X operations from the above observations by setting start = I end = size – 1.
• Update start = (start + end) / 2 + 1 if all the elements of the subarray input[start],..., input[end] can be made equal by decrementing at most X operations.
• Update end = (start + end) / 2 – 1 if not already done.
• Finally, print the length of the longest subarray produced by the preceding procedures.

### Code:

``````// Maximize the length of longest subarray consisting of same elements by at most X decrements
#include <bits/stdc++.h>
using namespace std;

// Segment Tree formation which the minimum element in a range
int buildTree(int segTree[], int* input, int s,int e, int value)
{

// Base case
if (s == e) {

// Update the value in the segment tree from given array
segTree[value] = input[s];
return segTree[value];
}

// Division of left and right subtree
int mid = (s + e) / 2;

// Recursive construction of left sub tree
int leftMin = buildTree(segTree, input, s, mid,2 * value + 1);

// Recursive construction of right subtree
int rightMin = buildTree(segTree, input, mid + 1,e, 2 * value + 2);

// Stores the smallest element in the subarray
return segTree[value] = min(leftMin, rightMin);
}

// This function return smallest element in the sub array
int query(int segTree[], int s, int e,int l, int r, int value)
{

// If the elements are out of range
if (s > r || e < l)return INT_MAX;

/*
If all the elements of the
subarray are in the range [l, r]
*/
if (s >= l && e <= r)
return segTree[value];

// Division of left and right subtree
int mid = (s + e) / 2;

// Smallest element from left subtree
int leftMin = query(segTree, s, mid, l,r, 2 * value + 1);

// Smallest element from right subtree
int rightMin = query(segTree, mid + 1, e, l,r, 2 * value + 2);

return min(leftMin, rightMin);
}

// Maximize the length of longest subarray consisting of same elements by at most X decrements
int solve(int* input, int size, int x)
{

/*
Stores the length of longest subarray with
all the elements equal in atmost x decrements
*/
int ans = 1;

// Store the prefix sum array
int prefixSum[size + 1];

prefixSum[0] = input[0];
for (int i = 0; i < size; i++)
prefixSum[i + 1] = prefixSum[i] + input[i];

int segTree[4 * size + 5];

// Segment tree formation
buildTree(segTree, input, 0, size - 1, 0);

// Iterating the array
for (int i = 0; i < size; i++) {

// start index of the current subarray
int startSub = i;

// end index of the current subarray
int endSub = size - 1;

int mid;

// Stores end index of the longest subarray
int maxSub = i;

// Performing the binary search
while (startSub <= endSub) {

// Find the mid for binary search
mid = (startSub + endSub) / 2;

// Finding the smallest element in range [i, mid] using Segment Tree
int minElement = query(segTree, 0, size - 1, i, mid, 0);

// Stores total sum of subarray after x decrements
int expected_sum = (mid - i + 1) * minElement;

// Stores sum of elements of subarray before x decrements
int actual_sum = prefixSum[mid + 1] - prefixSum[i];

// If subarray found with all equal elements
if (actual_sum - expected_sum <= x) {

// Update start
startSub = mid + 1;

// Update max_index
maxSub = max(maxSub, mid);
}

// This means the selected range is invalid
else {

// Update end
endSub = mid - 1;
}
}

// Store the length of longest subarray
ans = max(ans, maxSub - i + 1);
}

// Return result
return ans;
}

int main()
{
int input[] = { 3,5,6,7,3 };
int x = 3;
int size = 5;

// Maximize the length of longest subarray with at most x decrements
cout << solve(input, size, x);

return 0;
}``````

### Time Complexity

O(N * (log(N)) ^ 2)

The time complexity for the solution of "Maximize the length of longest subarray consisting of same elements by at most X decrements" is O(N * (log(N)) ^ 2), where 'N' is the size of the input Array. Since we are iterating on all the input array elements in every iteration, we are applying binary search. Time complexity to do a binary search will cost log(N) time complexity. In every binary search, we are also doing the query in the segment tree, which will cost log(N) time complexity again. So the total time complexity of the nested loops will be O(N * (log(N)) ^ 2).

### Space Complexity

O(N)

The space complexity for the solution of “Maximize the length of longest subarray consisting of same elements by at most X decrements” is  O(N), where N is the size of the input Array since we are creating an extra array to store the elements in the form of a segment tree.

Check out this problem - Subarray With 0 Sum

## FAQs

1. What are segment trees?
A Segment Tree is a data structure that can successfully answer range queries over an array while also allowing the Array to be modified.

2. Where are segment trees used?
When there are several range queries on an array and changes to the same Array's elements, a Segment Tree is employed. A segment tree can solve the problem in less time compared to the brute force approach.

3. Why is the segment tree helping in making the solution efficient?
If we use a basic array then finding minimum will cost linear time complexity and updating will be done in constant time complexity. A Segment Tree is a data structure that effectively answers range queries over an array while remaining flexible enough to allow the array to be modified. This can involve things like calculating the sum of consecutive array elements or determining the smallest element in a time span using a segment tree. We can perform the operations in logarithmic time complexity. The segment tree stores the element in the array but in the form of a tree hence iterating on it only cost the logarithmic time complexity.

## Key Takeaways

In this blog, we discussed the solution of “Maximize the length of longest subarray consisting of same elements by at most X decrements”, the article also focused on the time and space complexity of the solution.

If you want to learn more about segment trees and want to practice some quality questions which require you to excel your preparation a notch higher, then you can visit our Guided Path for segment trees on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, all the best for your future endeavors, and Keep Coding.

Live masterclass