Least Number of Unique Integers after K Removals

 Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

 

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

 

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length

My answer:

Basic logic: get count of each number, sort them ascending by count, reduce k by each count from the num with smallest quantity until k is negative. Reducing k by one number's count with remaining k>=0 meaning such number can be removed given k elements will be removed

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> numCountMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < arr.length; i ++) {
            Integer count = numCountMap.getOrDefault(arr[i], 0);
            count ++;
            numCountMap.put(arr[i], count);
        }
        List<Integer> list = new ArrayList<>(numCountMap.values());
        Collections.sort(list);
        int uniqNumCount= list.size();
        for (Integer element : list) {
            k -= element;
            if (k < 0) {
                break;
            } else {
                uniqNumCount --;
            }
            
        }
        return uniqNumCount;
 
    }
}

Largest Time for Given Digits

 Given an array of 4 digits, return the largest 24 hour time that can be made.

The smallest 24 hour time is 00:00, and the largest is 23:59.  Starting from 00:00, a time is larger if more time has elapsed since midnight.

Return the answer as a string of length 5.  If no valid time can be made, return an empty string.

 

Example 1:

Input: [1,2,3,4]
Output: "23:41"

Example 2:

Input: [5,5,5,5]
Output: ""

 

Note:

1. A.length == 4
2. 0 <= A[i] <= 9

My Answer:

Basic Logic: since number of input array is fixed, 4, number of all 4 digits combination is fixed as well, 4*3*2. We can sort all the combinations first in descending order, and then find the 1st valid combination

class Solution {
    public String largestTimeFromDigits(int[] A) {
        
        if (A == null || A.length != 4) {
            return "";
        }
        Arrays.sort(A);
        if (A[0] < 0 || A[0] > 2 || (A[0] == 2 && A[1] > 3) || (A[0] == 2 && A[1] <= 3 && A[2] >=6)) {
            return "";
        }
        List<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
        List<String> allResults = getAllCombinations(A, 0).stream().map(s -> {
            StringBuilder sb = new StringBuilder(s);
            sb.insert(2, ":");
            return sb.toString();
        }).collect(Collectors.toList());
        Collections.sort(allResults, Collections.reverseOrder());
        for (String result : allResults) {
            if (isResultValid(result)) {
                return result;
            }
        }
        return "";
    }
    
    private boolean isResultValid(String result) {
        if (Integer.valueOf(result.substring(0,2)) >= 24 || Integer.valueOf(result.substring(3,5)) > 59) {
            return false;
        }
            return true;
    }
    
    private List<String> getAllCombinations(int A[], int index) {
        
        if (index >= A.length ) {
            return new ArrayList<String>(){
                {
                    add("");
                }
            };
        }
        List<String> currentResults = new ArrayList<String>();
        List<String> nextResults = getAllCombinations(A, index + 1);
        for (String nextResult : nextResults) {
            for (int i = 0; i <= nextResult.length(); i ++) {
                StringBuilder sb = new StringBuilder(nextResult);
                sb.insert(i, String.valueOf(A[index]));
                currentResults.add(sb.toString());
            }
        }
        return currentResults;
    }
}

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

 Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

 

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3

Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

 

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6

Accepted Answer:

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0] == target ? 1: 0;
        }
        // to check if subarray sum is Target
        // core logic is F(i) - F(y) == Target(i is current index, and y is index 
        // somewhere before it)
        // which means there exists 1 path from y to x,
        // F(i) is sum from index -1 to i, F(-1) = 0
        //
        // F(i-1) = F(i-2) + V(i-1)
        Set<Integer> set = new HashSet<>();
        set.add(0);
        int res = 0, cur = 0;
        for (int i = 0; i < nums.length; i++) {
            cur += nums[i];
            if (set.contains(cur - target)) {
                res++;
                cur = 0;
                set = new HashSet<>();
                set.add(0);
            } else {
                set.add(cur);
            }
        }
        return res;
}