Given an array of positive numbers arr[] and integer K. You have to choose the maximum number possible from left to right such that each of them should fit in one of the K sections, where each section contains only one kind of number. You can start from any index of your choice. Once, you reach an index where you can’t fit your number in any of the K sections, STOP there.
Examples:
Input: N = 3, K = 2, arr[] = { 2, 1, 2 }
Output: 3
Explanation: We can pick all of themInput: N = 6, K = 1, arr[] = { 0, 1, 2, 2, 2, 2 }
Output: 4
Explanation: It’s optimal to pick from index 2(0-indexed) [2, 3, 4, 5].
Approach: This can be solved by the following idea:
Maintaining a window of numbers in which only k distinct numbers are present and maximizing the length of the window.
Steps involved in the implementation of the code:
- Maintain a map to check the number of distinct elements present in the window.
- Start iterating the array.
- If, the count of distinct elements is more than K, start removing elements from starting until it becomes less than K.
- If at any point occurrence of the element becomes 0, remove it from the map.
- Keep on updating the maximum length until it is less than K.
Below is the code for the above approach:
C++
// C++ Implementation of the above code #include <bits/stdc++.h> using namespace std; // Function to find the maximum number // of element we can choose int totalNumbers( int n, int arr[], int K) { int i = 0; int start = 0; int len = 0; // Map to maintain size of sections unordered_map< int , int > m; int maxx = 0; while (i < n) { m[arr[i]]++; len++; // If count of number is more than // K while (m.size() > K) { m[arr[start]]--; len--; // If all occurrence of number // is erased if (m[arr[start]] == 0) { m.erase(arr[start]); } start++; } // Update the maximum numbers if (m.size() <= K) { maxx = max(maxx, len); } i++; } // Return the output return maxx; } // Driver code int main() { int n = 3; int K = 2; int arr[] = { 1, 2, 1 }; // Function call cout << totalNumbers(n, arr, K); return 0; } |
Java
// Java Implementation of the above code import java.io.*; import java.util.*; class GFG { // Function to find the maximum number of elements we // can choose static int totalNumbers( int n, int [] arr, int K) { int i = 0 ; int start = 0 ; int len = 0 ; // Map to maintain size of sections Map<Integer, Integer> m = new HashMap<>(); int maxx = 0 ; while (i < n) { m.put(arr[i], m.getOrDefault(arr[i], 0 ) + 1 ); len++; // If count of number is more than K while (m.size() > K) { m.put(arr[start], m.get(arr[start]) - 1 ); len--; // If all occurrences of number is erased if (m.get(arr[start]) == 0 ) { m.remove(arr[start]); } start++; } // Update the maximum numbers if (m.size() <= K) { maxx = Math.max(maxx, len); } i++; } // Return the output return maxx; } public static void main(String[] args) { int n = 3 ; int K = 2 ; int [] arr = { 1 , 2 , 1 }; // Function call System.out.println(totalNumbers(n, arr, K)); } } // This code is contributed by karthik. |
Python3
# Python implementation of the above code def totalNumbers(n, arr, K): i = 0 start = 0 length = 0 # Map to maintain size of sections m = {} maxx = 0 while i < n: m[arr[i]] = m.get(arr[i], 0 ) + 1 length + = 1 # If count of number is more than K while len (m) > K: m[arr[start]] - = 1 length - = 1 # If all occurrences of number is erased if m[arr[start]] = = 0 : del m[arr[start]] start + = 1 # Update the maximum numbers if len (m) < = K: maxx = max (maxx, length) i + = 1 # Return the output return maxx n = 3 K = 2 arr = [ 1 , 2 , 1 ] # Function call print (totalNumbers(n, arr, K)) |
C#
using System; using System.Collections.Generic; class Program { static int TotalNumbers( int n, int [] arr, int K) { int i = 0; int start = 0; int len = 0; // Dictionary to maintain size of sections Dictionary< int , int > dict = new Dictionary< int , int >(); int maxx = 0; while (i < n) { if (dict.ContainsKey(arr[i])) dict[arr[i]]++; else dict.Add(arr[i], 1); len++; // If count of number is more than K while (dict.Count > K) { dict[arr[start]]--; len--; // If all occurrence of number is erased if (dict[arr[start]] == 0) dict.Remove(arr[start]); start++; } // Update the maximum numbers if (dict.Count <= K) maxx = Math.Max(maxx, len); i++; } // Return the output return maxx; } static void Main() { int n = 3; int K = 2; int [] arr = { 1, 2, 1 }; // Function call Console.WriteLine(TotalNumbers(n, arr, K)); } } |
Javascript
// JavaScript Implementation of the above code // Function to find the maximum number // of element we can choose function totalNumbers(n, arr, K) { let i = 0; let start = 0; let len = 0; // Map to maintain size of sections let m = new Map(); let maxx = 0; while (i < n) { m.set(arr[i], (m.get(arr[i]) || 0) + 1); len++; // If count of number is more than K while (m.size > K) { m.set(arr[start], m.get(arr[start]) - 1); len--; // If all occurrence of number is erased if (m.get(arr[start]) == 0) { m. delete (arr[start]); } start++; } // Update the maximum numbers if (m.size <= K) { maxx = Math.max(maxx, len); } i++; } // Return the output return maxx; } // Driver code let n = 3; let K = 2; let arr = [1, 2, 1]; // Function call console.log(totalNumbers(n, arr, K)); |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!