Count Customers Who Did Not Get A Computer

Problem Statement

Count Customers Who Did Not Get A Computer - Coding Ninjas Codestudio

Strings version : Function to find Number of customers who could not get a computer - GeeksforGeeks

Pattern:

---

Solution

public static int countCustomers(ArrayList<Integer> arr, int k) 
{
	// Write your code here
	int occupied = 0, result = 0 ;
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	
	for (int cus : arr) {
		// first time
		if(!map.containsKey(cus)) {
			map.put(cus, 0); 
			// if vacancy - mark vacancy
			if (occupied < k) {
				map.put(cus, 1);
				occupied++;
			}
		}
		// second time
		else {
			// if holding - mark vacant
			if (map.get(cus) == 1) {
				map.remove(cus);
				occupied--;
			}
			// else increment result
			else result++;
		}
	}
	return result;
}

TC : $O(n)$ SC : $O(n)$