Given a 2D array A[][] of size N x 2 where:
- Every element lies between [1, N].
- A[i][0] signifies that there must be at most A[i][0] elements strictly lesser than i+1 and at most A[i][1] elements strictly greater than i+1.
The task is to find the maximum number of elements that can come together abiding by the above condition.
Examples:
Input: N = 3, A[][] = {{1, 2}, {2, 1}, {1, 1]}
Output: 2
Explanation: If 1, 2, 3 all come together, then there is 0 (at most 1) element less than 1 and 2(at most 2) are greater.
1(at most 2) element less than 2 and 1(at most 1) greater 2.
For 3 there are 2 elements less than 3 but as per the condition there can be at most 1 element smaller than 3.
So cannot include 3. Therefore maximum 2 elements can be selected together.Input: N = 5, A[][] = {{2, 3}, {4, 2}, {3, 1}, {3, 1}, {1, 1}};
Output: 4
Naive Approach: The idea is based on the concept that a minimum of 1 element can be kept in a set and at max, all the elements can be kept together, i.e., N
- Initially, for the value of K where 1 <= K <= N, check if K elements can be grouped together abiding by the conditions.
- Select K elements out of N elements and check the below condition for all K from 1 to N.
- Check for every candidate i from 1 to N:
- If C candidates already belong to the set of K elements then for the ith element to belong in a set of K numbers, i must have exactly C elements smaller and K-C-1 elements greater than i.
- In this way, count the valid candidates and check if it is possible to keep K elements together in a set.
- Check for every candidate i from 1 to N:
- At the end, the maximum K is the answer.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The better approach is to solve using Binary Search.
- Instead of checking for every possible value of K use Binary Search there.
- As if it is possible to keep K elements together, this means it is also possible to keep any lower value of K elements together.
- So check for the higher values and if it is not possible to keep K elements together means higher values of K cannot be grouped together.
- When both lower and higher value becomes that is the answer.
Below is the implementation of the above-mentioned approach :
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to keep k elements togetherbool isPossible(vector<vector<int> >& a, int n, int k){ // Initially the set is empty, so // candidates present is 0 int candidatePresent = 0; // Loop through all the candidates for (int i = 0; i < n; i++) { // For i to be a part of the set // i's condition must allow to keep // Atleast candidatePresent number of // Elements smaller than i // And k-candidatePresent-1 // Number of elements larger than i // If so then add i // To the set of k numbers if (a[i][0] >= candidatePresent && a[i][1] >= k - candidatePresent - 1) candidatePresent++; } // If possible to keep at least k // elements together return true if (candidatePresent >= k) return true; // Else return false return false;}int maxElementsinSet(vector<vector<int> >& a, int n){ int left = 1, right = n; int ans = 1; while (left <= right) { int mid = (left + right) / 2; // If it is possible to keep mid // elements together them mid // is a possible answer and also // check for higher values of mid if (isPossible(a, n, mid)) { ans = mid; left = mid + 1; } // Else check for lower values of mid else right = mid - 1; } return ans;}// Driver Codeint main(){ int N = 5; vector<vector<int> > A = { { 2, 3 }, { 4, 2 }, { 3, 1 }, { 3, 1 }, { 1, 1 } }; cout << maxElementsinSet(A, N); return 0;} |
Java
// Java code to implement the approachimport java.util.*;public class GFG { // Function to check if it is possible // to keep k elements together static boolean isPossible(int a[][], int n, int k) { // Initially the set is empty, so // candidates present is 0 int candidatePresent = 0; // Loop through all the candidates for (int i = 0; i < n; i++) { // For i to be a part of the set // i's condition must allow to keep // Atleast candidatePresent number of // Elements smaller than i // And k-candidatePresent-1 // Number of elements larger than i // If so then add i // To the set of k numbers if (a[i][0] >= candidatePresent && a[i][1] >= k - candidatePresent - 1) candidatePresent++; } // If possible to keep at least k // elements together return true if (candidatePresent >= k) return true; // Else return false return false; } static int maxElementsinSet(int a[][], int n) { int left = 1, right = n; int ans = 1; while (left <= right) { int mid = (left + right) / 2; // If it is possible to keep mid // elements together them mid // is a possible answer and also // check for higher values of mid if (isPossible(a, n, mid) == true) { ans = mid; left = mid + 1; } // Else check for lower values of mid else right = mid - 1; } return ans; } // Driver Code public static void main(String arg[]) { int N = 5; int A[][] = { { 2, 3 }, { 4, 2 }, { 3, 1 }, { 3, 1 }, { 1, 1 } }; System.out.println(maxElementsinSet(A, N)); }}// This code is contributed by Samim Hossain Mondal. |
Python
# Python code to implement the approach# Function to check if it is possible# to keep k elements togetherdef isPossible(a, n, k): # Initially the set is empty, so # candidates present is 0 candidatePresent = 0 # Loop through all the candidates for i in range(n): # For i to be a part of the set # i's condition must allow to keep # Atleast candidatePresent number of # Elements smaller than i # And k-candidatePresent-1 # Number of elements larger than i # If so then add i # To the set of k numbers if (a[i][0] >= candidatePresent and a[i][1] >= k - candidatePresent - 1): candidatePresent += 1 # If possible to keep at least k # elements together return true if (candidatePresent >= k): return 1 # Else return false return 0def maxElementsinSet(a, n): left = 1 right = n ans = 1 while (left <= right): mid = (left + right) / 2 # If it is possible to keep mid # elements together them mid # is a possible answer and also # check for higher values of mid if (isPossible(a, n, mid)): ans = mid left = mid + 1 # Else check for lower values of mid else: right = mid - 1 print(ans)# Driver Codeif __name__ == "__main__": N = 5; A = [[ 2, 3 ], [ 4, 2 ], [ 3, 1 ], [ 3, 1 ], [ 1, 1 ]] maxElementsinSet(A, N) # This code is contributed by hrithikgarg03188. |
C#
// C# code to implement the approachusing System;public class GFG { // Function to check if it is possible // to keep k elements together static bool isPossible(int[, ] a, int n, int k) { // Initially the set is empty, so // candidates present is 0 int candidatePresent = 0; // Loop through all the candidates for (int i = 0; i < n; i++) { // For i to be a part of the set // i's condition must allow to keep // Atleast candidatePresent number of // Elements smaller than i // And k-candidatePresent-1 // Number of elements larger than i // If so then add i // To the set of k numbers if (a[i, 0] >= candidatePresent && a[i, 1] >= k - candidatePresent - 1) candidatePresent++; } // If possible to keep at least k // elements together return true if (candidatePresent >= k) return true; // Else return false return false; } static int maxElementsinSet(int[, ] a, int n) { int left = 1, right = n; int ans = 1; while (left <= right) { int mid = (left + right) / 2; // If it is possible to keep mid // elements together them mid // is a possible answer and also // check for higher values of mid if (isPossible(a, n, mid) == true) { ans = mid; left = mid + 1; } // Else check for lower values of mid else right = mid - 1; } return ans; } // Driver Code public static void Main(String[] arg) { int N = 5; int[, ] A = { { 2, 3 }, { 4, 2 }, { 3, 1 }, { 3, 1 }, { 1, 1 } }; Console.WriteLine(maxElementsinSet(A, N)); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code to implement the approach // Function to check if it is possible // to keep k elements together const isPossible = (a, n, k) => { // Initially the set is empty, so // candidates present is 0 let candidatePresent = 0; // Loop through all the candidates for (let i = 0; i < n; i++) { // For i to be a part of the set // i's condition must allow to keep // Atleast candidatePresent number of // Elements smaller than i // And k-candidatePresent-1 // Number of elements larger than i // If so then add i // To the set of k numbers if (a[i][0] >= candidatePresent && a[i][1] >= k - candidatePresent - 1) candidatePresent++; } // If possible to keep at least k // elements together return true if (candidatePresent >= k) return true; // Else return false return false; } const maxElementsinSet = (a, n) => { let left = 1, right = n; let ans = 1; while (left <= right) { let mid = parseInt((left + right) / 2); // If it is possible to keep mid // elements together them mid // is a possible answer and also // check for higher values of mid if (isPossible(a, n, mid)) { ans = mid; left = mid + 1; } // Else check for lower values of mid else right = mid - 1; } return ans; } // Driver Code let N = 5; let A = [ [2, 3], [4, 2], [3, 1], [3, 1], [1, 1] ]; document.write(maxElementsinSet(A, N));// This code is contributed by rakeshsahni</script> |
Output
4
Time Complexity: O(N*logN)
Auxiliary Space: O(1)
Share your thoughts in the comments
