Maximize Element Fit Count — Problem Statement & Solution Guide
Problem Description
Given two integer arrays, elements and slots, where elements[i] represents the capacity demand of the i-th item and slots[j] represents the maximum allowable capacity of the j-th container.
An item i can be allocated to container j if and only if elements[i] <= slots[j]. Each container can hold at most one item, and each item can be placed into at most one container.
Return the maximum number of items that can be simultaneously assigned to valid containers.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximize Element Fit Count"
WHY DOES IT MATTER?
Resource allocation under constraints is a fundamental pattern tested in interviews to evaluate your grasp of Greedy Algorithms, Sorting, and Binary Search Trees.
OPTIMIZATION CHALLENGE
The challenge is ensuring each element takes the minimal sufficient capacity rather than an arbitrary viable slot, which requires fast dynamic lower-bound lookups or synchronized sorted array traversals.
REAL-WORLD CONNECTION
This pattern models Kubernetes pod scheduling onto cluster nodes, thread-pool job assignment, and warehouse inventory packing where items of varying sizes must fit into distinct container capacities.
When asked about constraint-matching problems, always clarify whether inputs are static or streaming. Mentioning both the sorted two-pointer approach and the balanced BST strategy signals strong architectural intuition.
COMPLEXITY AT A GLANCE
O(N log N + M log M)O(1)Core Theory — Why This Approach?
The 'Maximize Element Fit Count' problem is a classic greedy matching problem under inequality constraints. Given a set of element demands and slot capacities, the goal is to maximize the cardinality of the bipartite matching between elements and slots such that every matched element's demand does not exceed its corresponding slot's capacity. A naive brute-force search trying all permutations or checking all elements against all available slots runs in $O(N \times M)$ time, which becomes infeasible when dealing with hundreds of thousands of items.
Interview Questions on This Problem
Q1How would you modify your solution if the slot capacities are updated dynamically in a streaming environment?
If slots are inserted or removed continuously, a simple static array sort fails. We should maintain the available slots in a Self-Balancing Binary Search Tree (such as std::multiset in C++ or TreeMap/TreeSet in Java). For each incoming element, we perform an $O(\log M)$ lower_bound query to find the smallest slot with capacity >= element demand, extract it from the tree upon allocation, and maintain total dynamic flexibility.
Q2Why is assigning an element to the smallest viable slot strictly optimal compared to assigning it to the largest available slot?
This follows the Greedy Choice Property. Allocating a larger slot than necessary consumes capacity that could have accommodated a larger future element. By allocating the tightest fitting (smallest sufficient) slot, we leave larger slots open for larger elements, strictly maximizing or preserving future matching opportunities.
Q3What is the time complexity difference between a two-pointer sorting approach and a Self-Balancing BST approach for static inputs?
Sorting both arrays and using two pointers takes $O(N \log N + M \log M)$ time and $O(1)$ auxiliary space. Using a BST takes $O(M \log M)$ to build and $O(N \log M)$ to search, requiring $O(M)$ extra space. While asymptotically similar, the two-pointer approach has lower constant factors and requires less auxiliary memory.
Examples
Input
elements = [3, 1, 5, 2], slots = [2, 4, 1]
Output
3
Explanation: Sort elements ascendingly to get [1, 2, 3, 5] and slots to get [1, 2, 4]. We pair item 1 with slot 1, item 2 with slot 2, and item 3 with slot 4. Item 5 exceeds all available remaining slots. Thus, 3 items are successfully assigned.
Input
elements = [10, 20, 30], slots = [5, 15]
Output
1
Explanation: The smallest item demands 10 capacity, which can fit into the slot of capacity 15. The slot of capacity 5 cannot accommodate any remaining item. Hence, at most 1 item can fit.
Input
elements = [4, 4, 4], slots = [5, 2, 6, 4]
Output
3
Explanation: Three items of size 4 are assigned to slots of sizes 4, 5, and 6 respectively. The slot of size 2 is too small and left unused. Maximum fit count is 3.
Input
elements = [8, 9], slots = [2, 3, 4]
Output
0
Explanation: All available slot capacities are strictly less than the minimal required element size of 8. No items can be assigned.
Constraints
- 1 <= elements.length, slots.length <= 10^5
- 1 <= elements[i], slots[j] <= 10^9
Optimal Approach & Strategy
Sort both elements and slots arrays in non-decreasing order, then utilize a two-pointer approach to greedily match the smallest available element to the smallest capable slot. Alternatively, store slots in a self-balancing binary search tree (multiset) and use binary search to locate best-fit slots.
Brute Force Approach
For each element, scan through all slots to find the first unallocated slot with capacity greater than or equal to the element's demand. This requires O(N * M) time complexity and fails on large input arrays.
Verified Code Solutions
function maximizeFitCount(elements, slots) {
elements.sort((a, b) => a - b);
slots.sort((a, b) => a - b);
let i = 0, j = 0, cnt = 0;
while (i < elements.length && j < slots.length) {
if (elements[i] <= slots[j]) {
cnt++; i++; j++;
} else {
j++; // slot too small
}
}
return cnt;
}
function main() {
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) return;
let idx = 0;
const n = data[idx++];
const m = data[idx++];
const elements = data.slice(idx, idx + n);
idx += n;
const slots = data.slice(idx, idx + m);
console.log(maximizeFitCount(elements, slots));
}
main();#include <bits/stdc++.h>
using namespace std;
int maximizeFitCount(vector<int> elements, vector<int> slots) {
sort(elements.begin(), elements.end());
sort(slots.begin(), slots.end());
int i = 0, j = 0, cnt = 0;
while(i < (int)elements.size() && j < (int)slots.size()) {
if(elements[i] <= slots[j]) {
++cnt; ++i; ++j;
} else {
++j; // slot too small, try larger slot
}
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if(!(cin >> n >> m)) return 0;
vector<int> elements(n), slots(m);
for(int i=0;i<n;++i) cin>>elements[i];
for(int j=0;j<m;++j) cin>>slots[j];
cout << maximizeFitCount(elements, slots);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int maximizeFitCount(int[] elements, int[] slots) {
Arrays.sort(elements);
Arrays.sort(slots);
int i = 0, j = 0, cnt = 0;
while (i < elements.length && j < slots.length) {
if (elements[i] <= slots[j]) {
cnt++; i++; j++;
} else {
j++; // slot too small
}
}
return cnt;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] elements = new int[n];
int[] slots = new int[m];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) elements[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) slots[i] = Integer.parseInt(st.nextToken());
System.out.print(maximizeFitCount(elements, slots));
}
}def maximize_fit_count(elements, slots):
elements.sort()
slots.sort()
i = j = cnt = 0
while i < len(elements) and j < len(slots):
if elements[i] <= slots[j]:
cnt += 1
i += 1
j += 1
else:
j += 1
return cnt
def main():
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
return
it = iter(data)
n = next(it)
m = next(it)
elements = [next(it) for _ in range(n)]
slots = [next(it) for _ in range(m)]
print(maximize_fit_count(elements, slots))
if __name__ == "__main__":
main()function maximizeFitCount(elements, slots) {
elements.sort((a, b) => a - b);
slots.sort((a, b) => a - b);
let i = 0, j = 0, cnt = 0;
while (i < elements.length && j < slots.length) {
if (elements[i] <= slots[j]) {
cnt++; i++; j++;
} else {
j++; // slot too small
}
}
return cnt;
}
function main() {
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) return;
let idx = 0;
const n = data[idx++];
const m = data[idx++];
const elements = data.slice(idx, idx + n);
idx += n;
const slots = data.slice(idx, idx + m);
console.log(maximizeFitCount(elements, slots));
}
main();Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.