Priyanka and Toys

  • + 0 comments

    My Java solution with o(n log n) time complexity and o(1) space complexity:

    public static int toys(List<Integer> w) {
            // goal: determine the min amt of subarrays that can be created based on the container rule
            if(w.size() == 1) return 1;
            
            //sort arr
            Collections.sort(w);
            
            //iterate over each val until it reaches the max container val and increment the container count
            int maxContainerVal = w.get(0) + 4;
            int containers = 1;
            for(int i = 0; i < w.size(); i++){
                if(w.get(i) > maxContainerVal){
                    maxContainerVal = w.get(i) + 4;
                    containers++;
                }
            }
            return containers;
        }