Given two sorted array of size N. The task is to find the maximum number of elements in the first array which are strictly greater than the elements of the second array such that an element can be considered only once.
Examples:
Input: arr1[] = { 20, 30, 50 }, arr2[] = { 25, 40, 60 }
Output: 2
Explanation:
Maximum 2 elements 30 (30 > 25) and 50 (50 > 40) of array arr1 is greater than arr2.Input: arr1[] = { 10, 15, 20, 25, 30, 35 }, arr2[] = { 12, 14, 26, 32, 34, 40 }
Output: 4
Explanation:
Maximum 4 elements 15 (15 > 12), 20 (20 > 14), 30 (30 > 26) and 35 (35 > 34) of arr1 is greater than arr2.
Approach:
- Compare the elements of both the arrays from index 0 one by one.
- If the element at the index of arr1 is greater than the element at the index of arr2 then increase the answer and the index of both arrays by 1.
- If the element at the index of arr1 is lesser or equal to the element at the index of arr2 then
increase the index of arr1. - Repeat the above steps until any array’s index reaches to the last element.
- Print 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 find greater elementsvoid findMaxElements( int arr1[], int arr2[], int n){ // Index counter for arr1 int cnt1 = 0; // Index counter for arr2 int cnt2 = 0; // To store the maximum elements int maxelements = 0; while (cnt1 < n && cnt2 < n) { // If element is greater, // update maxelements and counters // for both the arrays if (arr1[cnt1] > arr2[cnt2]) { maxelements++; cnt1++; cnt2++; } else { cnt1++; } } // Print the maximum elements cout << maxelements << endl;}int main(){ int arr1[] = { 10, 15, 20, 25, 30, 35 }; int arr2[] = { 12, 14, 26, 32, 34, 40 }; int n = sizeof(arr1) / sizeof(arr1[0]); findMaxElements(arr1, arr2, n); return 0;} |
Java
// Java program for the above approach class Main{ // Function to find greater elements static void findmaxelements(int arr1[], int arr2[], int n) { // Index counter for arr1 int cnt1 = 0; // Index counter for arr1 int cnt2 = 0; // To store the maximum elements int maxelements = 0; while(cnt1 < n && cnt2 < n) { // If element is greater, // update maxelements and counters // for both the arrays if(arr1[cnt1] > arr2[cnt2]) { maxelements++; cnt1++; cnt2++; } else { cnt1++; } } // Print the maximum elements System.out.println(maxelements); }// Driver Code public static void main(String[] args){ int arr1[] = { 10, 15, 20, 25, 30, 35 }; int arr2[] = { 12, 14, 26, 32, 34, 40 }; findmaxelements(arr1, arr2, arr1.length); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach# Function to find greater elements def findmaxelements(arr1, arr2, n): # Index counter for arr1 cnt1 = 0 # Index counter for arr2 cnt2 = 0 # To store the maximum elements maxelements = 0 # If element is greater, # update maxelements and counters # for both the arrays while cnt1 < n and cnt2 < n : if arr1[cnt1] > arr2[cnt2] : maxelements += 1 cnt1 += 1 cnt2 += 1 else : cnt1 += 1 # Print the maximum elements print(maxelements) # Driver Code arr1 = [ 10, 15, 20, 25, 30, 35 ] arr2 = [ 12, 14, 26, 32, 34, 40 ] findmaxelements(arr1, arr2, len(arr1))# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approach using System; class GFG{ // Function to find greater elements static void findmaxelements(int[] arr1, int[] arr2, int n) { // Index counter for arr1 int cnt1 = 0; // Index counter for arr1 int cnt2 = 0; // To store the maximum elements int maxelements = 0; while(cnt1 < n && cnt2 < n) { // If element is greater, update // maxelements and counters for // both the arrays if(arr1[cnt1] > arr2[cnt2]) { maxelements++; cnt1++; cnt2++; } else { cnt1++; } } // Print the maximum elements Console.Write(maxelements);} // Driver Code static public void Main(string[] args) { int[] arr1 = { 10, 15, 20, 25, 30, 35 }; int[] arr2 = { 12, 14, 26, 32, 34, 40 }; findmaxelements(arr1, arr2, arr1.Length); } } // This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program for the above approach// Function to find greater elementsfunction findMaxElements( arr1, arr2, n){ // Index counter for arr1 var cnt1 = 0; // Index counter for arr2 var cnt2 = 0; // To store the maximum elements var maxelements = 0; while (cnt1 < n && cnt2 < n) { // If element is greater, // update maxelements and counters // for both the arrays if (arr1[cnt1] > arr2[cnt2]) { maxelements++; cnt1++; cnt2++; } else { cnt1++; } } // Print the maximum elements document.write( maxelements );}var arr1 = [10, 15, 20, 25, 30, 35];var arr2 = [12, 14, 26, 32, 34, 40];var n = arr1.length;findMaxElements(arr1, arr2, n);// This code is contributed by rrrtnx.</script> |
Output:
4
Time Complexity: O(N), where N is the length of the array.
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!
