Solution by rohitnandi12


  • 0
    R

    From the question it is clear that there will be 1 to 1 Mapping between elements Cookie s and Greed Factor g

    Tip:1 In problems where you need to compare one element with rest of the elements be it in same or different arrays, think of brute force approach and later try to optimize it.

    Test Cases

    Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.

    Test Input 1: T1
    [1,1,2]
    [1,2,3]
    
    Test Input 2: T2
    [1,3,3]
    [4,1,2,5]
    

    Approach #1 Brute Force [Wrong Solution]

    Intuition

    Let for the ith Child the Greed Factor be gi, and compare it with each Cookie size sj, until it satisfies the condition sj >= gi. Change sj to -1 to denote it has been selected for a child.

    Java

    public class Solution {
        public int findContentChildren(int[] g, int[] s) {
            int noOfContentChild = 0;
            for(int i=0; i<g.length; i++){
                for(int j=0; j<s.length; j++){
                    if(s[j]==-1)continue;
    
                    if(s[j]>=g[i]){
                        ++noOfContentChild;
                        s[j] = -1;
                        break;
                    }
                }
            }
            return noOfContentChild;
        }
    }
    

    Testing

    T1 = Passed
    T2 = Failed

    Testing Inference

    T2 fails because our current algorithm assigns the first cookie size greater than the greed factor in hand, irrespective how big it is, which is not so frugal.


    Approach #2 Sort Method [Accepted]

    Intuition

    If we sort the arrays, then we can start with the smallest greed Factor and move to next Greed Factor only if a cookie size is greater than it.

    Algorithm

    • Sort array g
    • Sort array s
    • Loop until end of g or s (whichever is shorter)
      • move to next Greed Factor only when sj >= gi
      • move to next cookie size
    • Return the last greed factor index

    Java

    public class Solution {
        public int findContentChildren(int[] g, int[] s) {
            Arrays.sort(g);
            Arrays.sort(s);
            int gi=0, si=0;   //gIndex and sIndex
            while(gi<g.length && si<s.length){
                if(s[si]>=g[gi]){
                    gi++;
                }
                si++;
            }
            return gi;
        }
    }
    

    Testing

    T1 = Passed
    T2 = Passed

    Complexity Analysis

    • Time complexity : O(Min(n,m)). Where n is size of array g and m is size of array s. Ignoring O(n log n) and O(m log m) to sort the arrays.

    • Space complexity : O(1)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.