Given an array arr[] of N distinct integers, the task is to find the maximum element in an interval [L, R] such that the interval contains exactly one of the given N integers and 1 ? L ? R ? 105
Input: arr[] = {5, 10, 200}
Output: 99990
All possible intervals are [1, 9], [6, 199] and [11, 100000].
[11, 100000] has the maximum integers i.e. 99990.
Input: arr[] = {15000, 25000, 40000, 70000, 80000}
Output: 44999
Approach: The idea is to fix the element we want our interval to contain. Now we are interested in how much we can extend our interval to left and right without overlapping with other elements.
So, we first sort our array. Then for a fixed element, we determine its ends using the previous and next elements. We should also take care of corner cases that are when we fix our first and last intervals. This way for every element i, we find the maximum length of the interval.
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum// size of the required intervalint maxSize(vector<int>& v, int n){ // Insert the borders for array v.push_back(0); v.push_back(100001); n += 2; // Sort the elements in ascending order sort(v.begin(), v.end()); // To store the maximum size int mx = 0; for (int i = 1; i < n - 1; i++) { // To store the range [L, R] such that // only v[i] lies within the range int L = v[i - 1] + 1; int R = v[i + 1] - 1; // Total integers in the range int cnt = R - L + 1; mx = max(mx, cnt); } return mx;}// Driver codeint main(){ vector<int> v = { 200, 10, 5 }; int n = v.size(); cout << maxSize(v, n); return 0;} |
Java
// Java implementation of the approachimport static java.lang.Integer.max;import java.util.*;class GFG{ // Function to return the maximum // size of the required interval static int maxSize(Vector<Integer> v, int n) { // Insert the borders for array v.add(0); v.add(100001); n += 2; // Sort the elements in ascending order Collections.sort(v); // To store the maximum size int mx = 0; for (int i = 1; i < n - 1; i++) { // To store the range [L, R] such that // only v[i] lies within the range int L = v.get(i - 1) + 1; int R = v.get(i + 1) - 1; // Total integers in the range int cnt = R - L + 1; mx = max(mx, cnt); } return mx; } // Driver code public static void main(String[] args) { Integer arr[] = {200, 10, 5}; Vector v = new Vector(Arrays.asList(arr)); int n = v.size(); System.out.println(maxSize(v, n)); }}// This code is contributed by Princi Singh |
Python
# Python3 implementation of the approach# Function to return the maximum# size of the required intervaldef maxSize(v, n): # Insert the borders for array v.append(0) v.append(100001) n += 2 # Sort the elements in ascending order v = sorted(v) # To store the maximum size mx = 0 for i in range(1, n - 1): # To store the range [L, R] such that # only v[i] lies within the range L = v[i - 1] + 1 R = v[i + 1] - 1 # Total integers in the range cnt = R - L + 1 mx = max(mx, cnt) return mx# Driver codev = [ 200, 10, 5]n = len(v)print(maxSize(v, n))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG{ // Function to return the maximum // size of the required interval static int maxSize(List<int> v, int n) { // Insert the borders for array v.Add(0); v.Add(100001); n += 2; // Sort the elements in ascending order v.Sort(); // To store the maximum size int mx = 0; for (int i = 1; i < n - 1; i++) { // To store the range [L, R] such that // only v[i] lies within the range int L = v[i - 1] + 1; int R = v[i + 1] - 1; // Total integers in the range int cnt = R - L + 1; mx = Math.Max(mx, cnt); } return mx; } // Driver code public static void Main(String[] args) { int []arr = {200, 10, 5}; List<int> v = new List<int>(arr); int n = v.Count; Console.WriteLine(maxSize(v, n)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function to return the maximum// size of the required intervalfunction maxSize(v, n){ // Insert the borders for array v.push(0); v.push(100001); n += 2; // Sort the elements in ascending order v.sort((a, b) => a - b); // To store the maximum size let mx = 0; for (let i = 1; i < n - 1; i++) { // To store the range [L, R] such that // only v[i] lies within the range let L = v[i - 1] + 1; let R = v[i + 1] - 1; // Total integers in the range let cnt = R - L + 1; mx = Math.max(mx, cnt); } return mx;}// Driver code let v = [ 200, 10, 5 ]; let n = v.length; document.write(maxSize(v, n));</script> |
Output:
99990
Time Complexity: O(nlog(n))
Auxiliary Space: O(1)
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!
