Assign Cookies – Leetcode #455

Problem Statement

This problem is from Leetcode – Assign Cookies. The problem statement in short is as below:

Given two arrays g (children’s greed factors) and s (cookie sizes), assign each child at most one cookie such that s[j] >= g[i] to satisfy the child. Return the maximum number of content children.

Solution

1. Sort both the given arrays.
2. Iterate the arrays while checking the given condition is satisfied. If condition is satisfied then increment counter and move to the next child.

 public int findContentChildren(int[] g, int[] s) {
		 
		 int match = 0;
		 
		 Arrays.sort(g);
		 Arrays.sort(s);
		 
		 int i=0, j=0;
		 
		 while(i<g.length &&  j<s.length) {
			 
			 if(s[j] >= g[i]) {
				 
				 match++;
				 
				 // move to next child
				 i++;
			 }
			 
			// move to next cookie
			 j++;
		 }
		 
		 return match;
	 }

You can checkout the code from Github here: Assign Cookies. See the performance of this approach below:

PERFORMANCE ANALYSIS

RUNTIME	9 ms | Beats 98.90 %
MEMORY	48.32 MB | Beats 84.70 %
TIME COMPLEXITY	O N Log n