# Maximum number of elements from an array B[] that are present in ranges [A[i] + K, A[i] – K]

Given two arrays **A[] **of size** N **and** B[] **of size **M** and an integer **K**, the task is to select at most one element from array** B[]** for every element **A[i] **such that the element lies in the range **[A[i] – K, A[i] + K]** *( for 0 <= i <= N – 1 )*. Print the maximum number of elements that can be selected from the array

**B[].**

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 4, A[] = {60, 45, 80, 60}, M = 3, B[] = {30, 60, 75}, K= 5Output:2Explanation :

B[0] (= 30): Not present in any of the ranges [A[i] + K, A[i] – K].

B[1] (= 60):B[1] lies in the range [A[0] – K, A[0] + K], i.e. [55, 65].

B[2] (= 75): B[2] lies in the range [A[2] – K, A[2] + K], i.e. [75, 85].

Input:N = 3 A[] = {10, 20, 30}, M = 3, B[] = {5, 10, 15}, K = 10Output:2

**Naive Approach:** The simplest approach to solve the problem is to traverse the array **A[]**, search linearly in the array **B[] **and mark visited if the value of the array **B[] **is selected. Finally, print the maximum number of elements from the array** B[] **that can be selected.

**Time Complexity: **O(N * M)**Auxiliary Space: **O(M)

**Efficient Approach: **Sort both the arrays **A[] **and **B[] **and try to assign the element of **B[]** that is in a range **[A[i] – K, A[i] + K].** Follow the steps below to solve the problem:

- Sort the arrays
**A[]**and**B[].** - Initialize a variable, say
**j**as**0,**to keep track in the array**B[]**and**count**as**0**to store the answer. - Iterate in a range
**[0, N – 1]**and perform the following steps:- Iterate in a while loop till
**j < M**and**B[j]< A[i] – K,**then increase the value of**j**by**1.** - If the value of
**j**is less than**M**and**B[j]**is greater than equal to**A[i] – K**and**B[j]**is less than equal to**A[i] + K**then increase the value of**count**and**j**by**1.**

- Iterate in a while loop till
- After completing the above steps, print the value of
**count**as the final value of the answer.

Below is the implementation of the above approach.

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count the maximum number of` `// elements that can be selected from array` `// B[] lying in the range [A[i] - K, A[i] + K]` `int` `selectMaximumEle(` `int` `n, ` `int` `m, ` `int` `k,` ` ` `int` `A[], ` `int` `B[])` `{` ` ` `// Sort both arrays` ` ` `sort(A, A + n);` ` ` `sort(B, B + m);` ` ` `int` `j = 0, count = 0;` ` ` `// Iterate in the range[0, N-1]` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` ` ` `// Increase the value of j till` ` ` `// B[j] is smaller than A[i]` ` ` `while` `(j < m && B[j] < A[i] - k) {` ` ` `j++;` ` ` `}` ` ` `// Increasing count variable when B[j]` ` ` `// lies in the range [A[i]-K, A[i]+K]` ` ` `if` `(j < m && B[j] >= A[i] - k` ` ` `&& B[j] <= A[i] + k) {` ` ` ` ` `count++;` ` ` `j++;` ` ` `}` ` ` `}` ` ` ` ` `// Finally, return the answer` ` ` `return` `count;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given Input` ` ` `int` `N = 3, M = 3, K = 10;` ` ` `int` `A[] = { 10, 20, 30 };` ` ` `int` `B[] = { 5, 10, 15 };` ` ` ` ` `// Function Call` ` ` `cout << selectMaximumEle(N, M, K, A, B) << endl;` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `import` `java.util.Arrays;` `class` `GFG` `{` ` ` ` ` `// Function to count the maximum number of` ` ` `// elements that can be selected from array` ` ` `// B[] lying in the range [A[i] - K, A[i] + K]` ` ` `static` `int` `selectMaximumEle(` `int` `n, ` `int` `m, ` `int` `k,` ` ` `int` `A[], ` `int` `B[])` ` ` `{` ` ` `// Sort both arrays` ` ` `Arrays.sort(A);` ` ` `Arrays.sort(B);` ` ` `int` `j = ` `0` `, count = ` `0` `;` ` ` `// Iterate in the range[0, N-1]` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `// Increase the value of j till` ` ` `// B[j] is smaller than A[i]` ` ` `while` `(j < m && B[j] < A[i] - k) {` ` ` `j++;` ` ` `}` ` ` `// Increasing count variable when B[j]` ` ` `// lies in the range [A[i]-K, A[i]+K]` ` ` `if` `(j < m && B[j] >= A[i] - k` ` ` `&& B[j] <= A[i] + k) {` ` ` `count++;` ` ` `j++;` ` ` `}` ` ` `}` ` ` `// Finally, return the answer` ` ` `return` `count;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `// Given Input` ` ` `int` `N = ` `3` `, M = ` `3` `, K = ` `10` `;` ` ` `int` `A[] = { ` `10` `, ` `20` `, ` `30` `};` ` ` `int` `B[] = { ` `5` `, ` `10` `, ` `15` `};` ` ` `// Function Call` ` ` `System.out.println(selectMaximumEle(N, M, K, A, B));` ` ` `}` `}` `// This code is contributed by Potta Lokesh` |

## Python3

`# Python3 program for the above approach` `# Function to count the maximum number of` `# elements that can be selected from array` `# B[] lying in the range [A[i] - K, A[i] + K]` `def` `selectMaximumEle(n, m, k, A, B):` ` ` ` ` `# Sort both arrays` ` ` `A.sort()` ` ` `B.sort()` ` ` `j ` `=` `0` ` ` `count ` `=` `0` ` ` `# Iterate in the range[0, N-1]` ` ` `for` `i ` `in` `range` `(n):` ` ` `# Increase the value of j till` ` ` `# B[j] is smaller than A[i]` ` ` `while` `(j < m ` `and` `B[j] < A[i] ` `-` `k):` ` ` `j ` `+` `=` `1` ` ` `# Increasing count variable when B[j]` ` ` `# lies in the range [A[i]-K, A[i]+K]` ` ` `if` `(j < m ` `and` `B[j] >` `=` `A[i] ` `-` `k` ` ` `and` `B[j] <` `=` `A[i] ` `+` `k):` ` ` `count ` `+` `=` `1` ` ` `j ` `+` `=` `1` ` ` `# Finally, return the answer` ` ` `return` `count` `# Driver Code` `# Given Input` `N ` `=` `3` `M ` `=` `3` `K ` `=` `10` `A ` `=` `[ ` `10` `, ` `20` `, ` `30` `]` `B ` `=` `[ ` `5` `, ` `10` `, ` `15` `]` `# Function Call` `print` `(selectMaximumEle(N, M, K, A, B))` `# This code is contributed by gfgking` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` ` ` `// Function to count the maximum number of` `// elements that can be selected from array` `// B[] lying in the range [A[i] - K, A[i] + K]` `static` `int` `selectMaximumEle(` `int` `n, ` `int` `m, ` `int` `k,` ` ` `int` `[] A, ` `int` `[] B)` `{` ` ` ` ` `// Sort both arrays` ` ` `Array.Sort(A);` ` ` `Array.Sort(B);` ` ` `int` `j = 0, count = 0;` ` ` `// Iterate in the range[0, N-1]` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `{` ` ` ` ` `// Increase the value of j till` ` ` `// B[j] is smaller than A[i]` ` ` `while` `(j < m && B[j] < A[i] - k)` ` ` `{` ` ` `j++;` ` ` `}` ` ` `// Increasing count variable when B[j]` ` ` `// lies in the range [A[i]-K, A[i]+K]` ` ` `if` `(j < m && B[j] >= A[i] - k &&` ` ` `B[j] <= A[i] + k)` ` ` `{` ` ` `count++;` ` ` `j++;` ` ` `}` ` ` `}` ` ` `// Finally, return the answer` ` ` `return` `count;` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` ` ` `// Given Input` ` ` `int` `N = 3, M = 3, K = 10;` ` ` `int` `[] A = { 10, 20, 30 };` ` ` `int` `[] B = { 5, 10, 15 };` ` ` `// Function Call` ` ` `Console.WriteLine(selectMaximumEle(N, M, K, A, B));` `}` `}` `// This code is contributed by avijitmondal1998` |

## Javascript

`<script>` ` ` `// Javascript program for the above approach` `// Function to count the maximum number of` `// elements that can be selected from array` `// B[] lying in the range [A[i] - K, A[i] + K]` `function` `selectMaximumEle(n, m, k, A, B) {` ` ` `// Sort both arrays` ` ` `A.sort((a, b) => a - b);` ` ` `B.sort((a, b) => a - b);` ` ` `let j = 0, count = 0;` ` ` `// Iterate in the range[0, N-1]` ` ` `for` `(let i = 0; i < n; i++) {` ` ` `// Increase the value of j till` ` ` `// B[j] is smaller than A[i]` ` ` `while` `(j < m && B[j] < A[i] - k) {` ` ` `j++;` ` ` `}` ` ` `// Increasing count variable when B[j]` ` ` `// lies in the range [A[i]-K, A[i]+K]` ` ` `if` `(j < m && B[j] >= A[i] - k` ` ` `&& B[j] <= A[i] + k) {` ` ` `count++;` ` ` `j++;` ` ` `}` ` ` `}` ` ` `// Finally, return the answer` ` ` `return` `count;` `}` `// Driver Code` `// Given Input` `let N = 3, M = 3, K = 10;` `let A = [10, 20, 30];` `let B = [5, 10, 15];` `// Function Call` `document.write(selectMaximumEle(N, M, K, A, B) + ` `"<br>"` `);` `// This code is contributed by _saurabh_jaiswal.` `</script>` |

**Output:**

2

**Time Complexity: **O(N*log(N))**Auxiliary Space: **O(N)