Accepted greedy algorithm.


  • 2

    [UPDATE]:
    This is not a working solution as pointed out by @andhddn below.

    I have a greedy algorithm that is accepted. Can't prove the correctness though. Main idea is to use the shortest string first. We sort all the string based on the number of 1s it has once, and then based on the 0s second time. Each time we try to consume as much string as possible. Result is the bigger of the 2 iterations.

    Any counter example/ proof of correctness is appreciated

    public class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            int result = 0;
            if(strs.length == 0) return 0;
            PriorityQueue<Element> oneQueue = new PriorityQueue<Element>(new oneComparator());
            PriorityQueue<Element> zeroQueue = new PriorityQueue<Element>(new zeroComparator());
            
            for(String s : strs){
                int ones = 0;
                int zeros = 0;
                for(char c : s.toCharArray()){
                    if(c == '0') {
                        zeros++;
                    }else{
                        ones++;
                    }
                }
                Element e = new Element(ones, zeros);
                oneQueue.offer(e);
                zeroQueue.offer(e);
            }
            int numZero = m;
            int numOne = n;
            /*sort the string based on # of 0 each string has and try to consume as many string as possible*/
            while(!zeroQueue.isEmpty()){
                if(numZero >= zeroQueue.peek().zero && numOne >= zeroQueue.peek().one){
                    result++;
                    numZero -= zeroQueue.peek().zero;
                    numOne -= zeroQueue.peek().one;
                }
    
                zeroQueue.poll();
            }
            int secondResult = 0;
            numZero = m;
            numOne = n;
            /*sort the string based on # of 1 each string has and try to consume as many string as possible*/
            while(!oneQueue.isEmpty()){
                if(numOne >= oneQueue.peek().one && numZero >= oneQueue.peek().zero){
                    secondResult++;
                    numZero -= oneQueue.peek().zero;
                    numOne -= oneQueue.peek().one;
                }
    
                oneQueue.poll();
                
            }        
            return Math.max(result, secondResult);
            
        }
        
        class oneComparator implements Comparator<Element>{
            public int compare(Element e1, Element e2){
                if(e1.one == e2.one) return e1.zero - e2.zero;
                return e1.one - e2.one;
            }
        }
        
        class zeroComparator implements Comparator<Element>{
            public int compare(Element e1, Element e2){
                if(e1.zero == e2.zero) return e1.one - e2.one;
                return e1.zero - e2.zero;
            }
        }
        
        class Element{
            public int one;
            public int zero;
    
            public Element(int one, int zero){
                this.one = one;
                this.zero = zero;
            }
            
        }
    }```

  • 2
    A

    @DonaldTrump Does not work for this input:
    {
    "0000111",
    "0000111111",
    "01111111",
    "0001",
    "000111111",
    "0000001111111",
    "00011111",
    "000011111",
    "00000011",
    "0111111",
    "0000000001111111",
    "0011",
    "001111",
    "00000001111",
    "0011",
    "0000111111111",
    "0001111111",
    "011111111"
    };

    M = 4
    N = 6

    It returns 1, while there are 2 "0011" strings which satisfy M and N {4, 6}


  • 1

    @andhddn Yes you are right. I will update this post. I wonder how did you come up with the test case?


  • 0
    A

    @DonaldTrump I had similar thoughts at the beginning, but had significant doubts too. I.e. my brain was not strong enough to disprove it mathematically. So I took one of the correct versions and wrote a program which generates inputs, compares the two outputs and chooses the simplest repro case.


  • 1
    S

    @DonaldTrump

    Oh Yeah, I came up with similar greedy approach and got accepted beating 100% :P
    but it's wrong:

    public int findMaxForm(String[] strs, int m, int n) {
           Arrays.sort(strs, new Comparator<String>(){
            
            @Override
            public int compare(String s1, String s2){
                int[] cnt1 = count(s1);
                int[] cnt2 = count(s2);
                if(cnt1[1] == cnt2[1]){
                    return cnt1[0] - cnt2[0];
                }
                return cnt1[1] - cnt2[1];
                
             }
        });
         int i = 0;
         int count = 0;
         while((m > 0 || n > 0) && i < strs.length){
             int[] cnt = count(strs[i]);
             if(cnt[0] > m && cnt[1] > n) break;
             if(cnt[0] <= m && cnt[1] <= n){
                 m -= cnt[0];
                 n -= cnt[1];
                 count++;
             } 
             i++;
             
         }
        return count;
    }
    
    
    
    public int[] count(String s){
        int[] cnt = new int[2];
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '0') cnt[0]++;
            if(s.charAt(i) == '1') cnt[1]++;
        }
        return cnt;
    }
    

    It fails this simple test case which is missing from test cases:

    ["000","0111","0111","0111"]
    3
    9


  • 0

    Thanks, I have just added all your test cases.


Log in to reply
 

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