[Leetcode] 2094. Finding 3-Digit Even Numbers

https://leetcode.com/problems/finding-3-digit-even-numbers/description/?envType=daily-question&envId=2025-05-12

intial

i used dfs to recursively search all but actually it is not time optimal

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        Set<Integer> check = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        boolean[] visited= new boolean[digits.length];
        Arrays.sort(digits);
        dfs(digits,check,"",list,visited);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    public void dfs(int[] digits, Set<Integer> check, String tmp,List<Integer> lst, boolean[] visited){
        if(tmp!=""){
            int num = Integer.parseInt(tmp);
            if(tmp.length()==3){
                if(!check.contains(num) && num%2==0 && tmp.charAt(0)!='0') {
                    lst.add(num);
                    check.add(num);
                }
                return;
            }
        }

        for(int i=0; i<digits.length;i++){
            if(!visited[i]){
                visited[i]=true;
                dfs(digits,check,tmp+String.valueOf(digits[i]),lst,visited);
                visited[i]=false;
            }
            
        }
    }
}

sol

the correct way is to iter from 100 to 999 and see if we have the digits in our freq map of "digits". Like lets say we are at 169 and in our freq map, we dont have 6 or 9 then we cant form that number. But obviously 9 isnt even so we have to iter with step of 2

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        int [] map = new int[10]; // for freq of 0 to 9 (digits are fixed)
        
        for(int i = 0;i<digits.length;i++){ //make a frequency map of digits
            map[digits[i]]++;
        }
        
        List<Integer> arr = new ArrayList<>();
        
        for(int i = 100;i<=999;i = i + 2){ //will always runs from 100 to 999 
            int num = i;
            int [] freq = new int[10];
            while(num > 0){  // will always run 3 times
                int rem = num % 10;
                freq[rem]++;
                num = num/10;
            }
            
            boolean res = findans(freq,map);
            if(res) arr.add(i);
        }
        
        int [] ans = new int[arr.size()]; //logic for arraylist to array conversion
        for(int i = 0;i<arr.size();i++){ // at max we can have all num from 100 to 998 only
            ans[i] = arr.get(i);
        }
        
        return ans;
    }
    
    private boolean findans(int [] currentNum,int [] database){
        
        for(int i = 0;i<10;i++){  //it will always run for at max 10 times
            if(currentNum[i] > database[i]) return false;
        }
        return true;
    }
}

complexity

so sort is n log n but the main time villain is the permutation
for 3 digit perm, we go n(n-1)n(-2) which is n^3

space is n