Why binary search is not working in this problem

Binary search is a powerful tool to have a complexity of O(n)*something. However, sometimes, a binary search may fail. One important reason is that the searching space must be continuous. If not, we may get some error.

For example, if f(3) is True, then f(4), f(5).. will also be True. We can use binary search. However, if f(3) is True, f(4) is False, then f(5) is True again, we will get an error as the searching space is not continuous.

Problem

Contiguous array

Not working Binary search code

The below code can pass 500+ test cases, however, it is not correct. The reason is that the searching space is not continuous.

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        lo, hi =0, len(nums)
        dp = list(itertools.accumulate([0]+nums))
        
        def good(m):
            #if m%2 !=0:return False
            for i in range(len(nums)):
                if i+2*m>len(nums):
                    return False
                r = i+2*m-1
                if dp[r+1]-dp[i]==m:return True
        while lo < hi:
            m = (lo+hi+1)//2
            if good(m):
                lo = m
            else:
                hi = m - 1
        #print(lo)
        if good(lo):return 2*lo
        return 0

Hope this example can help the reader have a better understanding about the code.

A workable solution can be found here.

Binary search is networking for this problem either.

The reason is still we have a non-continuous search space. Specifically, the following case is possible, where the bolded number of length if good while the rest is not good.

1,2 ,3 ,4 ,5 ,6 ,7

For example

122 can be an awesome string, however, 1223 can not be. 12 can also not be, while 1 is good.

class Solution {
public:
    bool good(int m, vector<vector<int>>& dp)
    {
        //cout<<m<<"*****"<<endl;
        int odd = false;
        int ok = true;
        for (int i = m; i < dp.size(); ++i)
        {
            odd = false;
            ok = true;
            for (int j = 0; j < 10; ++j)
            {
                if((dp[i][j]-dp[i-m][j])%2==0) continue;
                else
                {
                    //cout<<i<<"i, j, "<<j<<odd<<" odd  "<<m<<endl;
                    if (odd) 
                    {
                        ok = false;
                        break;
                    }
                    else odd = true;
                }
                
            }
            if (ok) return  true; 
        }
       return false;
    }
    int longestAwesome(string s) {
        const int n = s.length();
        int l = 1, r = n;
        vector<vector<int>> dp(n+1, vector<int>(10, 0));
        dp[0][s[0]-'0'] = 1;
        for (int i = 0; i < n; ++i)
        {
            dp[i+1] = dp[i];
            dp[i+1][s[i]-'0'] += 1;
        }
        //for (int i = r; i>1;--i)
        //    if (good(i, dp)) return i;
        //return 1;
        while (l < r)
        {
            int mid = l + (r-l+1)/2;
            if (good(mid, dp))
            {
                cout<<"good "<<mid<<endl;
                l = mid;
            }
            else
            {
                r = mid -1;
            }
        }
        return l;
    }
};

For example, the above code fails at the following test case:

"213123"

As the middle value is 3, and 3 fails. However, 6 works.

Naive O(n²) solution get TLE

class Solution {
public:
    bool good(int m, vector<vector<int>>& dp)
    {
        //cout<<m<<"*****"<<endl;
        int odd = false;
        int ok = true;
        for (int i = m; i < dp.size(); ++i)
        {
            odd = false;
            ok = true;
            for (int j = 0; j < 10; ++j)
            {
                if((dp[i][j]-dp[i-m][j])%2==0) continue;
                else
                {
                    //cout<<i<<"i, j, "<<j<<odd<<" odd  "<<m<<endl;
                    if (odd) 
                    {
                        ok = false;
                        break;
                    }
                    else odd = true;
                }
                
            }
            if (ok) return  true; 
        }
       return false;
    }
    int longestAwesome(string s) {
        const int n = s.length();
        int l = 1, r = n;
        vector<vector<int>> dp(n+1, vector<int>(10, 0));
        dp[0][s[0]-'0'] = 1;
        for (int i = 0; i < n; ++i)
        {
            dp[i+1] = dp[i];
            dp[i+1][s[i]-'0'] += 1;
        }
        for (int i = r; i>1;--i)
            if (good(i, dp)) return i;
        return 1;
    }
};