Given a sorted array arr[] and a positive integer D, the task is to find the minimum and the maximum number of array elements that lie over the distance of D from an array element arr[i] in either direction i.e., over the range [arr[i] – D, arr[i]] or [arr[i], arr[i] + D].
Examples:
Input arr[] = {2, 4, 7, 11, 13, 14}, D = 4
Output: 1 3
Explanation:
The minimum number of array elements is included is 1 from arr[0](= 2) as the there exists only 1 element that lies over the range [-2, 2].
The minimum number of array elements is included is 3 from arr[3](= 11) as the there exists only 3 elements that lies over the range [11, 15].
Therefore, print 1, 3.Input: arr[] = {1, 3, 5, 9, 14}, D = 5
Output: 1 3
Approach: The given problem can be solved using the Greedy Technique by using the Binary Search to the left and right of every point to check how many points can be included in the range of distance D. Follow the steps below to solve the problem:
- Initialize two variables, say min and max to store minimum and maximum elements included in a range of distance D.
- Iterate the array arr[] and for each element perform the following:
- Initialize a variable dist to calculate the number of points included in a range of distance D.
- Perform the binary search on the left of arr[i] and find a number array elements over the range [arr[i] – D, arr[i]] using the following steps:
- Initialize left = 0, right = i – 1 and at every iteration:
- Find the value of mid = (left + right) / 2.
- If arr[mid] < arr[i] – D, then update the value of left to mid + 1. Otherwise, update the value of dist to mid and update the value of right to mid – 1.
- Initialize left = 0, right = i – 1 and at every iteration:
- Update the value of min and max according to the value of dist.
- Perform the binary search on the left of arr[i] and find the number of array elements over the range [arr[i], arr[i] + D] using the following steps:
- Initialize left = i + 1, right = N – i and at every iteration:
- Find the value of mid = (left + right) / 2.
- If arr[mid] > arr[i] + D, then update the value of right to mid – 1. Otherwise, update the value of dist to mid and update the value of left to mid + 1.
- Initialize left = i + 1, right = N – i and at every iteration:
- Update the value of min and max according to the value of dist.
- After completing the above steps, print the value of min and max as the resultant minimum and the maximum number of points covered.
Below is the implementation of the above approach:
C++
// c++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to perform the Binary// Search to the left of arr[i]// over the given rangeint leftSearch(int arr[], int val, int i){ // Base Case if (i == 0) return 1; int left = 0, right = i - 1; int ind = -1; // Binary Search for index to left while (left <= right) { int mid = (left + right) / 2; if (arr[mid] < val) { left = mid + 1; } else { right = mid - 1; // update index ind = mid; } } // Return the number of elements // by subtracting indices return ind != -1 ? i - ind + 1 : 1;}// Function to perform the Binary// Search to the right of arr[i]// over the given rangeint rightSearch(int arr[], int val, int i, int N){ // Base Case if (i == (N - 1)) return 1; int left = i + 1; int right = N - 1; int ind = -1; // Binary Search for index to right while (left <= right) { int mid = (left + right) / 2; if (arr[mid] > val) { right = mid - 1; } else { left = mid + 1; // Update the index ind = mid; } } // Return the number of elements // by subtracting indices return ind != -1 ? ind - i + 1 : 1;}vector<int> minMaxRange(int arr[], int D, int N){ // Stores the minimum and maximum // number of points that lies // over the distance of D int mx = 1, mn = N; // Iterate the array for (int i = 0; i < N; i++) { // Count of elements included // to left of point at index i int dist = leftSearch(arr, arr[i] - D, i); // Update the minimum number // of points mn = min(mn, dist); // Update the maximum number // of points mx = max(mx, dist); // Count of elements included // to right of point at index i dist = rightSearch(arr, arr[i] + D, i, N); // Update the minimum number // of points mn = min(mn, dist); // Update the maximum number // of points mx = max(mx, dist); } // Return the array vector<int> v; v.push_back(mn); v.push_back(mx); return v;}// Driver Codeint main(){ int arr[] = { 1, 3, 5, 9, 14 }; int N = 5; int D = 4; vector<int> minMax = minMaxRange(arr, D, N); cout << minMax[0] << " " << minMax[1] << endl; return 0;}// This code is contributed by dwivediyash |
Java
// Java program for the above approachimport java.io.*;import java.lang.Math;import java.util.*;class GFG { // Function to find the minimum and // maximum number of points included // in a range of distance D public static int[] minMaxRange( int[] arr, int D, int N) { // Stores the minimum and maximum // number of points that lies // over the distance of D int max = 1, min = N; // Iterate the array for (int i = 0; i < N; i++) { // Count of elements included // to left of point at index i int dist = leftSearch( arr, arr[i] - D, i); // Update the minimum number // of points min = Math.min(min, dist); // Update the maximum number // of points max = Math.max(max, dist); // Count of elements included // to right of point at index i dist = rightSearch( arr, arr[i] + D, i); // Update the minimum number // of points min = Math.min(min, dist); // Update the maximum number // of points max = Math.max(max, dist); } // Return the array return new int[] { min, max }; } // Function to perform the Binary // Search to the left of arr[i] // over the given range public static int leftSearch( int[] arr, int val, int i) { // Base Case if (i == 0) return 1; int left = 0, right = i - 1; int ind = -1; // Binary Search for index to left while (left <= right) { int mid = (left + right) / 2; if (arr[mid] < val) { left = mid + 1; } else { right = mid - 1; // update index ind = mid; } } // Return the number of elements // by subtracting indices return ind != -1 ? i - ind + 1 : 1; } // Function to perform the Binary // Search to the right of arr[i] // over the given range public static int rightSearch( int[] arr, int val, int i) { // Base Case if (i == arr.length - 1) return 1; int left = i + 1; int right = arr.length - 1; int ind = -1; // Binary Search for index to right while (left <= right) { int mid = (left + right) / 2; if (arr[mid] > val) { right = mid - 1; } else { left = mid + 1; // Update the index ind = mid; } } // Return the number of elements // by subtracting indices return ind != -1 ? ind - i + 1 : 1; } // Driver Code public static void main(String[] args) { int[] arr = { 1, 3, 5, 9, 14 }; int N = arr.length; int D = 4; int[] minMax = minMaxRange(arr, D, N); // Function Call System.out.print( minMax[0] + " " + minMax[1]); }} |
Python3
# Python Program to implement# the above approach# Function to find the minimum and# maximum number of points included# in a range of distance Ddef minMaxRange(arr, D, N): # Stores the minimum and maximum # number of points that lies # over the distance of D Max = 1 Min = N # Iterate the array for i in range(N): # Count of elements included # to left of point at index i dist = leftSearch(arr, arr[i] - D, i) # Update the minimum number # of points Min = min(Min, dist) # Update the maximum number # of points Max = max(Max, dist) # Count of elements included # to right of point at index i dist = rightSearch(arr, arr[i] + D, i) # Update the minimum number # of points Min = min(Min, dist) # Update the maximum number # of points Max = max(Max, dist) # Return the array return [Min, Max]# Function to perform the Binary# Search to the left of arr[i]# over the given rangedef leftSearch(arr, val, i): # Base Case if (i == 0): return 1 left = 0 right = i - 1 ind = -1 # Binary Search for index to left while (left <= right): mid = (left + right) // 2 if (arr[mid] < val): left = mid + 1 else: right = mid - 1 # update index ind = mid # Return the number of elements # by subtracting indices return i - ind + 1 if ind != -1 else 1# Function to perform the Binary# Search to the right of arr[i]# over the given rangedef rightSearch(arr, val, i): # Base Case if (i == len(arr) - 1): return 1 left = i + 1 right = len(arr) - 1 ind = -1 # Binary Search for index to right while (left <= right): mid = (left + right) // 2 if (arr[mid] > val): right = mid - 1 else: left = mid + 1 # Update the index ind = mid # Return the number of elements # by subtracting indices return ind - i + 1 if ind != -1 else 1# Driver Codearr = [1, 3, 5, 9, 14]N = len(arr)D = 4minMax = minMaxRange(arr, D, N)# Function Callprint(f"{minMax[0]} {minMax[1]}")# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the minimum and // maximum number of points included // in a range of distance D public static int[] minMaxRange(int[] arr, int D, int N) { // Stores the minimum and maximum // number of points that lies // over the distance of D int max = 1, min = N; // Iterate the array for (int i = 0; i < N; i++) { // Count of elements included // to left of point at index i int dist = leftSearch( arr, arr[i] - D, i); // Update the minimum number // of points min = Math.Min(min, dist); // Update the maximum number // of points max = Math.Max(max, dist); // Count of elements included // to right of point at index i dist = rightSearch( arr, arr[i] + D, i); // Update the minimum number // of points min = Math.Min(min, dist); // Update the maximum number // of points max = Math.Max(max, dist); } // Return the array return new int[] { min, max }; } // Function to perform the Binary // Search to the left of arr[i] // over the given range public static int leftSearch( int[] arr, int val, int i) { // Base Case if (i == 0) return 1; int left = 0, right = i - 1; int ind = -1; // Binary Search for index to left while (left <= right) { int mid = (left + right) / 2; if (arr[mid] < val) { left = mid + 1; } else { right = mid - 1; // update index ind = mid; } } // Return the number of elements // by subtracting indices return ind != -1 ? i - ind + 1 : 1; } // Function to perform the Binary // Search to the right of arr[i] // over the given range public static int rightSearch( int[] arr, int val, int i) { // Base Case if (i == arr.Length - 1) return 1; int left = i + 1; int right = arr.Length - 1; int ind = -1; // Binary Search for index to right while (left <= right) { int mid = (left + right) / 2; if (arr[mid] > val) { right = mid - 1; } else { left = mid + 1; // Update the index ind = mid; } } // Return the number of elements // by subtracting indices return ind != -1 ? ind - i + 1 : 1; } // Driver Code public static void Main() { int[] arr = { 1, 3, 5, 9, 14 }; int N = arr.Length; int D = 4; int[] minMax = minMaxRange(arr, D, N); // Function Call Console.Write(minMax[0] + " " + minMax[1]); }}// This code is contributed by gfgking. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum and // maximum number of points included // in a range of distance D function minMaxRange( arr, D, N) { // Stores the minimum and maximum // number of points that lies // over the distance of D let max = 1, min = N; // Iterate the array for (let i = 0; i < N; i++) { // Count of elements included // to left of point at index i let dist = leftSearch( arr, arr[i] - D, i); // Update the minimum number // of points min = Math.min(min, dist); // Update the maximum number // of points max = Math.max(max, dist); // Count of elements included // to right of point at index i dist = rightSearch( arr, arr[i] + D, i); // Update the minimum number // of points min = Math.min(min, dist); // Update the maximum number // of points max = Math.max(max, dist); } // Return the array return [min, max]; } // Function to perform the Binary // Search to the left of arr[i] // over the given range function leftSearch( arr, val, i) { // Base Case if (i == 0) return 1; let left = 0, right = i - 1; let ind = -1; // Binary Search for index to left while (left <= right) { let mid = Math.floor((left + right) / 2); if (arr[mid] < val) { left = mid + 1; } else { right = mid - 1; // update index ind = mid; } } // Return the number of elements // by subtracting indices return ind != -1 ? i - ind + 1 : 1; } // Function to perform the Binary // Search to the right of arr[i] // over the given range function rightSearch( arr, val, i) { // Base Case if (i == arr.length - 1) return 1; let left = i + 1; let right = arr.length - 1; let ind = -1; // Binary Search for index to right while (left <= right) { let mid = Math.floor((left + right) / 2); if (arr[mid] > val) { right = mid - 1; } else { left = mid + 1; // Update the index ind = mid; } } // Return the number of elements // by subtracting indices return ind != -1 ? ind - i + 1 : 1; } // Driver Code let arr = [1, 3, 5, 9, 14]; let N = arr.length; let D = 4; let minMax = minMaxRange(arr, D, N); // Function Call document.write( minMax[0] + " " + minMax[1]);// This code is contributed by Potta Lokesh </script> |
Output:
1 3
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Share your thoughts in the comments
